The automata is incredibly slow, though it's also incredibly cool. I implemented a trie that allows for Levenshtein distance queries here github.com/jamra/LevenshteinTrie

That was just a fun project, not something I optimized or even tested appropriately.

The theory behind the trie is that the dynamic programming algorithm for Levenshtein distance gets passed to each recursive step, reducing the amount of comparisons needed.

I like this subject so I'm going to read the paper you linked ;)