dictomaton

Shameless plug: I have a Java library that does this even more efficiently. It constructs a Levenshtein automaton of a word in linear time and then computes the intersection between a dictionary (stored in a deterministic acyclic minimal finite state automaton) and the Levensthein automaton. It also has other features, such as: - Perfect hash automata (an automaton that gives a unique hash for every word/sequence). - String-keyed maps that use a finite state automaton to store keys. More info: https://github.com/danieldk/dictomaton http://search.maven.org/#artifactdetails%7Ceu.danieldk.dicto...

The article takes a very weird turn: If we need extra information about the words, we can use an additional data structure along with the MA-FSA. We can store it in a hash table. This is not necessary at all, since an acyclic finite state automaton can be used as a perfect hash function. If you sum the right language cardinalities of the transitions followed, you get a unique hash code (1..n, where n is the number of strings in the automaton). For efficiency, you can precompute the cardinalities in the transitions or states. You can then use a normal array for whatever data you want to associate with a word. With respect to parts 1 & 2 of the series, one can construct a Levenshtein automaton for a given word in linear time[1]. Such an automaton matches any string within the given edit distance of the word. You can then compute the interse