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

51–59 of 59 posts

Re: Trie in JavaScript: The data structure behind autocomplete

#51

Post by rockwotj »

thatswrong0 wrote: post #5
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 :)

Whoot! Hope you find it useful :)

Re: Trie in JavaScript: The data structure behind autocomplete

#53

Post by karterk »

bollu wrote: post #35
karterk wrote: post #13

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/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!

With brute-force you have no idea about what letters could follow a given letter, but with a Trie you already know the possible combinations so you avoid needless permutations.

Re: Trie in JavaScript: The data structure behind autocomplete

#54

Post by jeffeld »

enumjorge wrote: post #44
padolsey wrote: post #29

Earlier quoted context omitted.

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.

It’s funny that you bring up cargo-culting because I find the unflinchingly rigid rule of “const for everything unless the code requires a let/var” to be cargo-cultish. I think it’s proponents vastly overestimate the value that you get out of it. In FE dev mutability is typically an issue at the app state level, and that’s not something you fix with const. It also doesn’t stop objects from being modified, and you sho…

It's not about adding value, it's about picking up bad habits from example code.

Re: Trie in JavaScript: The data structure behind autocomplete

#55

Post by danbmil99 »

Cybiote wrote: post #24
danbmil99 wrote: post #7

Fun fact: the trie data structure was invented by Ed Fredkin, a pioneer in Quantum computing as well as cellular automata

This is the best kind of correct but it's an interesting phrasing since Fredkin is a kind of Quantum supremacy skeptic (hotkey-find Classicatopia in: https://windowsontheory.org/2017/10/30/the-different-forms-o... ). Fredkin's contribution were to reversible computation and since Quantum computers are a kind of reversible computer, many ideas and gate notions carried over.

I agree, that is a more accurate description of Ed's work & opinion re Q-computing

Re: Trie in JavaScript: The data structure behind autocomplete

#56

Post by danbmil99 »

danbmil99 wrote: post #55
Cybiote wrote: post #24

Earlier quoted context omitted.

This is the best kind of correct but it's an interesting phrasing since Fredkin is a kind of Quantum supremacy skeptic (hotkey-find Classicatopia in: https://windowsontheory.org/2017/10/30/the-different-forms-o... ). Fredkin's contribution were to reversible computation and since Quantum computers are a kind of reversible computer, many ideas and gate notions carried over.

I agree, that is a more accurate description of Ed's work & opinion re Q-computing

I guess you can ask, can someone be a significant contributor to a field they don't believe in? Didn't Einstein contribute to Quantum Mechanics, while simultaneously harboring grave misgivings? (God doesn't play dice etc)

Re: Trie in JavaScript: The data structure behind autocomplete

#57

Post by nomaxx117 »

I remember having a class "competition" my freshman year of college to implement the fastest autocomplete system. It had to be Java, so I used JNI to call into a well-optimized set of C routines for constructing and querying a trie. I ended up winning by a lot - no one else even implemented a trie. I spent a lot of time making sure that I would have the fastest trie implementation, but that wasn't even necessary.
Post reply on HN