Earlier quoted context omitted.
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}}}} I don't think this implementation is efficient enough to ever be worth using in a real program, though.
Trie in JavaScript: The data structure behind autocomplete
41–50 of 59 posts
Re: Trie in JavaScript: The data structure behind autocomplete
#42It'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)
And thanks for the link, that is an interesting optimization!
EDIT: one fun non-practical application (histogramming the letters in a word is simpler and faster) is an anagram finder using prime numbers:
https://observablehq.com/@jobleonard/finding-anagrams-using-...
Re: Trie in JavaScript: The data structure behind autocomplete
#43I implemented them several times in Excel. Beats most lookups in terms of fun and speed.
As in a spreadsheet-based prefix tree?
Can I see it?
Re: Trie in JavaScript: The data structure behind autocomplete
#44for (let character... Please use const. Everything should be const until there is a proven need otherwise.
I reckon there's a kind of broken rationale where people think, "ok well this value will mutate over time so I can't possibly use a const", even though a new block scope is initialized on each iteration. The `for(let i in blah)` idiom is basically cargo-culted now without thought.
Take the code in this article as an example. What danger can there possibly be with using a let when iterating over the set of characters in a word? The inside of the for loop is two lines long. The extra information that using const provides to whoever maintains this code is negligible. Using a const doesn’t hurt, but that level of nitpicking it doesn’t add much value whether in this thread or in code reviews.
Re: Trie in JavaScript: The data structure behind autocomplete
#45However, the idea of implementing in JS gives me the impression that the author is advocating implementing autocomplete on the client (browser) [1]. I would encourage developers not to do so. Depending on the data set to be rendered, that could be a big perf hit or not feasible in certain scenarios, but if the data set is not dynamic or has a small memory footprint (ie, states in the US), then it should be fine to have that data sent to the client to be processed on.
My general rule of thumb - limit business logic to the server and rendering logic to the browser.
You can implement server-side autocomplete - send the partial search string as a request to the server, which responds with the autocomplete list of strings to be rendered in the UI, debouncing [2] to limit the number of requests to the server (instead of requesting on every user change to the partial search string). Of course, this would have its trade offs (API reqs introduce their own perf concerns), but you want to go this route if your search data set is dynamic and sufficiently large.
[1] Not sure if that was the author's intention bc I cannot access the author's blog on my work machine.
Re: Trie in JavaScript: The data structure behind autocomplete
#46Re: Trie in JavaScript: The data structure behind autocomplete
#47Earlier quoted context omitted.
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)
Thanks! I just realized it doesn't work with strings containing underscores, but simply using __ instead of _ (so double underscores) as the key to end-of-word markings fixes that. And thanks for the link, that is an interesting optimization! EDIT: one fun non-practical application (histogramming the letters in a word is simpler and faster) is an anagram finder using prime numbers: https://observablehq.com/@jobleonar…
UPD: Sorry, "up to 15" is a wrong phrasing. I checked once how "prime factorial" fits into primitive, and first 15 primes can fit into long. So it's possible to handle even more symbols if it's smth like "aaaaaaa"64 times because it would be just 2^64
Re: Trie in JavaScript: The data structure behind autocomplete
#48I used to hate tries, mostly bc I refused to take the time to understand them, but it is a pretty cool concept with a narrow but very practical use case. It does what it does really well, nothing more. However, the idea of implementing in JS gives me the impression that the author is advocating implementing autocomplete on the client (browser) [1]. I would encourage developers not to do so. Depending on the data set…
Re: Trie in JavaScript: The data structure behind autocomplete
#49I used to hate tries, mostly bc I refused to take the time to understand them, but it is a pretty cool concept with a narrow but very practical use case. It does what it does really well, nothing more. However, the idea of implementing in JS gives me the impression that the author is advocating implementing autocomplete on the client (browser) [1]. I would encourage developers not to do so. Depending on the data set…
Re: Trie in JavaScript: The data structure behind autocomplete
#50I wrote a trie based offensive language filter for a chat system used by the NHL's original streaming games broadcasts, way back in '99. It was written in C, and used the PerfectHash program to produce the hash table used by the trie to contain a dictionary of every known curse word, slang variant, and common misspellings in about a dozen languages. About 5 years ago I was looking at some open source chat systems, an…