4 ms·
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 b
by karterk 5y ago
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/typesense/typesense https://github.com/typesense/typesense
[2]: https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html
- bollu 5y agoDoes 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!
- karterk 5y agoWith 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.
- ignoramous 5y agohere's the fuzzy search impl on an adaptive-radix-trie in typesense: https://github.com/typesense/typesense/blob/96bc8a078/src/art.cpp#L1743 https://github.com/typesense/typesense/blob/96bc8a078/src/ar...