I learned about tries by leetcoding. This is exactly why I liked leetcoding. Because tries are awesome, and I was already imagining what one could build with it.
Trie in JavaScript: The data structure behind autocomplete
31–40 of 59 posts
Re: Trie in JavaScript: The data structure behind autocomplete
#32It's such a simple and elegant as data structure. If you only care about word lookup you can implement it in just 35 lines of modern JavaScript:
function trieBuilder(word_list) {
const root = {};
for (const word of words_list) {
let node = root;
for (const char of word) {
let nextNode = node[char];
if (!nextNode) node[char] = nextNode = {};
node = nextNode;
}
node._ = 1; // mark the nodes that are endings of real words
}
function findChildren(node, prefix, list, maxLength) {
if (node._ === 1) list.push(prefix);
for (const char in node) {
findChildren(node[char], prefix + char, list, maxLength);
if (list.length >= maxLength) return list;
}
return list;
}
function findSuffixes(prefix, maxLength) {
prefix = prefix.toLowerCase();
let node = root;
for (const char of prefix) {
let nextNode = node[char];
if (!nextNode) return [""];
node = nextNode;
}
let words = findChildren(node, prefix, [], maxLength);
return words;
}
return {root, findSuffixes};
}
Re: Trie in JavaScript: The data structure behind autocomplete
#33Tries 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 bas…
I've learned recently that a trie can also be succinctly encoded, like encoded as a string that contains almost only the node values and ~nothing else. This way for some languages you can encode all the valid words of that language in less space that it would be needed for the Hunspell dictionary used to generate them. Plus you get instant start-up as the dictionary had already been processed at build time basically.
Re: Trie in JavaScript: The data structure behind autocomplete
#34Trie 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
I can't figure out how this works. Shouldn't insert return a reference to the new trie?
Re: Trie in JavaScript: The data structure behind autocomplete
#35There 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/typesens…
Does the trie help in memoizing the edit distance between multiple words? Or do you pay the O(n^2) cost per word? I'd love to hear details of how this works!
Re: Trie in JavaScript: The data structure behind autocomplete
#36Trie 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
I can't figure out how this works. Shouldn't insert return a reference to the new trie?
No, it mutates the input trie. If you call `insert(trie, "foo")` with an empty trie, it will be modified to look like
{'f': {'o': {'o': {END: True}}}}
Re: Trie in JavaScript: The data structure behind autocomplete
#37Yes, that's also the data-structure you want to use when working on a URL router for instance, in a http framework.
Although, unless you have 10,000 of different http routes, the performance gains might not be that significant all things considered.
Re: Trie in JavaScript: The data structure behind autocomplete
#38There 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/typesens…
here's the fuzzy search impl on an adaptive-radix-trie in typesense: https://github.com/typesense/typesense/blob/96bc8a078/src/ar...
Re: Trie in JavaScript: The data structure behind autocomplete
#39It's such a simple and elegant as data structure. If you only care about word lookup you can implement it in just 35 lines of modern JavaScript: function trieBuilder(word_list) { const root = {}; for (const word of words_list) { let node = root; for (const char of word) { let nextNode = node[char]; if (!nextNode) node[char] = nextNode = {}; node = nextNode; } node._ = 1; // mark the nodes that are endings of real wor…
Nice implementation!
There is an option to get all suffixes without traversing subtree, but it comes with extra O(N) memory where N is combined length of all stored words - depending on case might be acceptable since memory for storing words itself is O(N) anyway. https://stackoverflow.com/a/29966616/2104560 (update 1 and update 3)
Re: Trie in JavaScript: The data structure behind autocomplete
#40Trie also can be used as a hashset/map, roughly it's like hash(obj).toString is a "word" for a trie and in the leaf we store the object.
It's https://en.wikipedia.org/wiki/Hash_array_mapped_trie which used in Scala's immutableMap https://dotty.epfl.ch/api/scala/collection/immutable/HashMap...