3 ms·
The usual implementation for autocomplete is to generate a trie data structure. A naive implementation will not have auto-correction or fix problems more establ
by leorocky 12y ago
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.
- mholt 12y agoTrue, but tries do not automatically solve those problems, either, and most tries use lots of memory, especially on 64-bit systems (pointers, pointers everywhere!).
- guiomie 12y agoI'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.
- leorocky 12y agoIt can't. You would have to fix the auto-correction before you searched the trie I'd think.
- mholt 12y agoWhen 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.