Live data from Hacker News

Redis on steroids: Autocomplete using Redis, Nginx and Lua

11–12 of 12 posts

Re: Redis on steroids: Autocomplete using Redis, Nginx and Lua

#11

Post by leorocky » Mon, Jun 09, 2014, 6:41 PM UTC

guiomie wrote: post #9

leorocky wrote: post #6

The usual implementation for autocomplete is to generate a trie data structure. A naive implementation will not have auto-correction or fix problems more established implementations have already addressed.

I'm currently implementing my own trie (for learning) for my own autocomplete module ... and I don't see how a trie (prefix tree) can solve the issues you just wrote.

It can't. You would have to fix the auto-correction before you searched the trie I'd think.

Re: Redis on steroids: Autocomplete using Redis, Nginx and Lua

#12

Post by mholt » Tue, Jun 10, 2014, 3:08 AM UTC

guiomie wrote: post #9

leorocky wrote: post #6

The usual implementation for autocomplete is to generate a trie data structure. A naive implementation will not have auto-correction or fix problems more established implementations have already addressed.

I'm currently implementing my own trie (for learning) for my own autocomplete module ... and I don't see how a trie (prefix tree) can solve the issues you just wrote.

When you traverse the prefix tree and you are blocked: meaning, the prefix does not match an entry in the structure, you perform edit operations: insert, delete, transpose, and substitute. If one of those garners a match, you keep going down the tree until you reach your edit distance.

Post reply on HN