dictomaton

My Java library, which does some of the things described in the article (DAWGS, perfect hashing, Levenshtein automata): https://github.com/danieldk/dictomaton

This very topic was discussed yesterday. For a given word, you can construct an automaton that matches that word within a certain edit distance in O(n) where n is the length of the word. Since the result is a DFSA, you can also see if a string matches in O(n). (See the work of Schulz & Mihov.) Moreover, rather than going over each word in a dictionary to find out whether that word is within a certain distance, you can compute the intersection language of the Levenshtein automaton and the dictionary automaton (which is generally faster, intersection is O(mn) in the number of states of the two automata). For an implementation of this and more, see: https://github.com/danieldk/dictomaton

> besides finite state dictionaries, ..., String mappings based on perfect hash automata I'm implementing a similar library in Rust. One of the key things I've found missing in Daciuk's great work on the topic is the handling of the registry. In your code[1], it looks like you're using a straight a hash table. I thought you'd like to know that I've had great success sacrificing complete DFA minimization in exchange for a small constant memory overhead by using an LRU cache of only some classes of states. My code still needs a good deal of polish, and I intend to write a blog post, but I bet you can make sense of the general strategy from the code and reuse it.[2] N.B. Lucene's implementation permits sacrificing complete minimization, but they don't use an LRU cache and I think still permit the registry to grow without bound. [1] - https:/

FWIW, my Dictomaton Java library also has support for Levenshtein automata (besides finite state dictionaries, perfect hash automata, and String mappings based on perfect hash automata): https://github.com/danieldk/dictomaton

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