Damn Cool Algorithms: Levenshtein Automata

For those of you like me who tried to read this article without the proper education to understand everything at first pass, here is the definition of a couple of acronyms he used without defining first:<p>NFA = Nondeterministic Finite Automata (<a href="http://en.wikipedia.org/wiki/Nondeterministic_finite-state_machine" rel="nofollow">http://en.wikipedia.org/wiki/Nondeterministic_finite-state_m...</a>) DFA = Deterministic Finite Automata (<a href="http://en.wikipedia.org/wiki/Deterministic_finite-state_machine" rel="nofollow">http://en.wikipedia.org/wiki/Deterministic_finite-state_mach...</a>)

I wonder if this method could extend to character transposition and weight-able costs; e.g., allow "hello"/"ehllo" = distance 1, as logically this is a single typing mistake of whacking the 'h' a bit early.<p>I've used the perl String::Approx module to great effect, but it takes a lot of resources to blast through a large dictionary.

I thought for a moment that Nick is back writing blog posts, but this is from the archives.<p>If you are a developer, esp Python and AppEngine, you really should read all the archives - it is one of the best general online sources for python, appengine (and the datastore) and dev.

Unfortunately, "food" is a poor example for explaining how Levenshtein Automata work in general because it has a double letter. This means that in one state, you have the "o" transition to more states than usual because it is both the next letter and the next letter after that. If you want to generalize his automaton, do the powerset construction for some other word like "news".

I use levenshtein heavily for one of my products <a href="http://www.getatomiq.com" rel="nofollow">http://www.getatomiq.com</a>