Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Trie in JavaScript: The data structure behind autocomplete

stackfull.dev

Post reply on HN
Print view View original

11–20 of 59 posts

Re: Trie in JavaScript: The data structure behind autocomplete

#11

Post by aelzeiny »

trinovantes wrote: post #8

The basic trie only matches exact consecutive characters. Does anyone know the data structure/trie variant for matching partial sequential characters? e.g. ABD matches A Brown Dog ^ ^ ^

There's a searching concept known as edit (levenshtein) distance that is close but not exactly what you're talking about. To rephrase your question: is there a datastructure that can pre-compute the levenshtein distance for a set or results?

Yes, and it's crazy complicated. See Levenshtein Automata[1]. In reality, I would let the professionals handle this by either using Open/ElasticSearch or Apache Lucene.

[1]http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...

Re: Trie in JavaScript: The data structure behind autocomplete

#12

Post by euler2100 »

benrbray wrote: post #6
mgraczyk wrote: post #4

I wrote a little Trie in Javascript for practice a while back. It flattens the data into a single array for better locality. I think it ends up being pretty quick for lookups (but not insertions). https://github.com/mgraczyk/fast-trie-js/blob/master/index.j... I used it for this little demo: https://assets.opentoken.com/demos/search/index.html

Tries are also perfect for solving games of Boggle! I have a demo here: https://benrbray.com/projects/unboggler

Hey, that's a pretty cool demo, thanks for sharing!

Re: Trie in JavaScript: The data structure behind autocomplete

#13

Post by karterk »

There is another aspect of tries that make them really useful: you can do fast, fuzzy word searches on a trie.

In Typesense[1], I've implemented fuzzy search based on levenshtein damerau distance and it's incredibly fast. I've found this approach to be a much better (faster + more flexible) alternative to Peter Norvig's brute-force based spell-checker that is quite a popular post [2].

[1]: https://github.com/typesense/typesense [2]: https://norvig.com/spell-correct.html

Re: Trie in JavaScript: The data structure behind autocomplete

#14

Post by aleksiy123 »

Trie is probably my favourite ds. I really enjoy this python implementation I learned while studying leetcode because its so succint. Really useful for interviews.

    from collections import defaultdict
    
    END = object()

    def make_trie():
       return defaultdict(make_trie)
    
    def insert(trie, word):
        for c in word:
            trie = trie[c]
        trie[END] = True

Re: Trie in JavaScript: The data structure behind autocomplete

#15

Post by psadri »

Note that to save memory, instead of using every character in the word, you may want to cap the depth of your trie to the first N chars. The words with shared prefixes are kept in an array at the leafs. During lookups, you’d scan the leaf array to find matches. You’d be trading space (lots of nested objects) vs speed (negligible for scanning small arrays).

Re: Trie in JavaScript: The data structure behind autocomplete

#16

Post by bitexploder »

rockwotj wrote: post #2

Tries are fun structures! However, for autocomplete you often want a weighted Trie because you have extra information you want to weight nodes by. An example with contacts is that you often want recent and frequent contacts. My company has an open source trie implementation here for a client to do weighted contact auto complete: https://github.com/shortwave/trie

I first learned about Tries when I implemented a spell checker, almost 20 years ago now, with basic suggestions. It’s amazing how easy it is to get an efficient, 80% spell checker and recommendation engine implemented from scratch once you dig into it. Tries make for an efficient enough in memory lookup structure (space, storage, and compute), and are an obvious part of a suggestion engine as well. Coupled with a basic soundex and some word mangling + edit distance checking and you have a very functional system. Solving the last 20% takes an order of magnitude more work :)

Re: Trie in JavaScript: The data structure behind autocomplete

#17

Post by TYMorningCoffee »

trinovantes wrote: post #8

The basic trie only matches exact consecutive characters. Does anyone know the data structure/trie variant for matching partial sequential characters? e.g. ABD matches A Brown Dog ^ ^ ^

Not exactly what you want but a second trie with the key on the starting letters and the value the complete word might work for you. Your ABD example would work but something like ABrD would not.

Re: Trie in JavaScript: The data structure behind autocomplete

#18

Post by harry8 »

aelzeiny wrote: post #11
trinovantes wrote: post #8

The basic trie only matches exact consecutive characters. Does anyone know the data structure/trie variant for matching partial sequential characters? e.g. ABD matches A Brown Dog ^ ^ ^

There's a searching concept known as edit (levenshtein) distance that is close but not exactly what you're talking about. To rephrase your question: is there a datastructure that can pre-compute the levenshtein distance for a set or results? Yes, and it's crazy complicated. See Levenshtein Automata[1]. In reality, I would let the professionals handle this by either using Open/ElasticSearch or Apache Lucene. [1] http:…

>I would let the professionals handle this...

If this site doesn't contain "the professionals" then the phrase has zero meaning.

Re: Trie in JavaScript: The data structure behind autocomplete

#19

Post by ufo »

psadri wrote: post #15

Note that to save memory, instead of using every character in the word, you may want to cap the depth of your trie to the first N chars. The words with shared prefixes are kept in an array at the leafs. During lookups, you’d scan the leaf array to find matches. You’d be trading space (lots of nested objects) vs speed (negligible for scanning small arrays).

Another way to save space is to use a directed acyclic graph. Specially if there are common suffixes that show up all the time.
Post reply on HN