If anyone wants to know how deep down the rabbit hole this stuff goes, they should read this blog post [1] on writing a Levenshtein Automaton to speed up fuzzy matching in Lucene by 100 times. It gets deep!
[1]: http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is...