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

1–10 of 59 posts

Re: Trie in JavaScript: The data structure behind autocomplete

#2

Post by rockwotj »

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

Re: Trie in JavaScript: The data structure behind autocomplete

#4

Post by mgraczyk »

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

Re: Trie in JavaScript: The data structure behind autocomplete

#5

Post by thatswrong0 »

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

Oh sick we might have to switch to this for our autocomplete / autosuggestion functionality - precisely because it's lacking weighting :)

Re: Trie in JavaScript: The data structure behind autocomplete

#6

Post by benrbray »

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

Re: Trie in JavaScript: The data structure behind autocomplete

#9

Post by js_chap »

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 ^ ^ ^

You probably want fuzzy search: https://en.m.wikipedia.org/wiki/Approximate_string_matching
Post reply on HN