3 ms·
Semi-offtopic: The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can b
by danieldk 12y ago
Semi-offtopic:
The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can be stored in a flat array/slice). This gives you O(n) time lookups, where n is the length of the word, and reduces much of the redundancy in a dictionary.
Words within an edit distance can be found by computing a Levenshtein automaton for the word (which can be done in linear time) and computing the intersection language of the dictionary automaton and the Levenshtein automaton.
This approach is fast and very compact. I have a Java implementation:
https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
- eric_bullington 12y agoOh, this is very cool. I wonder how many CAT (Computer-Aided Translation) tools out there (many of which are notoriously slow) could be significantly sped up using this approach. I'd bet most of them, although they're almost all closed-source so we will likely never know.
- Loic 12y agoI am a chemical engineer so reading "deterministic acyclic minimized finite state automaton" is sending me back in my first years at university. As I want to implement instant search with part of string matching, this can be very interesting. This is to match "Octane, 2,4,6-trimethyl-" when typing "trimethyl". For the moment I am looking at the Linkedin approach[0]. Sorry for keeping this semi-offtopic thread alive, but these problems are so interesting that I cannot stop. [0]: https://github.com/jamra/gocleo https://github.com/jamra/gocleo