Levenshtein automata seem to pop up on here every once in a while. They are quite interesting from a theory perspective, but (like many things devised by the theory community) incredibly complex in practice. Lucene 4.0 uses them for fuzzy queries, you can read the full story of how they struggled to get them working somewhere in the Lucene blog.<p>If you want to implement fuzzy string matching, I would look at something like <a href="http://arxiv.org/abs/1008.1191" rel="nofollow">http://arxiv.org/abs/1008.1191</a> . The experiments look impressively fast.
I suggest everyone check out the rest of the algorithms on that site. They are cool. <a href="http://blog.notdot.net/tag/damn-cool-algorithms" rel="nofollow">http://blog.notdot.net/tag/damn-cool-algorithms</a>
and in ocaml: <a href="https://github.com/c-cube/spelll/blob/master/spelll.ml#L124" rel="nofollow">https://github.com/c-cube/spelll/blob/master/spelll.ml#L124</a>