Damn Cool Algorithms: Levenshtein Automata

Not sure why the Myers bit vector algorithm from 1999 is not included in these comparisons. Since it can operate on whole 32-bit or 64-bit registers at a time, it is really O(NM/w) which is in effect just O(N) and just gives you the whole edit distance. Heikki Hyyrö has a few papers and a PhD thesis from circa 2001..2005 that walk you through this in pseudo-code that you could port to any low level language and also generalize the…

https://github.com/intel/hyperscan/ implements this along multiple regex matching and a pcre pattern compatible engine (chimera).

Actually, if you want to see whether the edit distance (Levenshtein) is within a fixed bound, say k, it's no longer O(mn), but around O(kn) (since you're only ever filling a narrow band of width ~k along the diagonal instead of the whole rectangle). Nonetheless, the DFA construction is priceless if you want flexible matching against a dictionary.

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: NFA = Nondeterministic Finite Automata (http://en.wikipedia.org/wiki/Nondeterministic_finite-state_m...) DFA = Deterministic Finite Automata (http://en.wikipedia.org/wiki/Deterministic_finite-state_mach...)