See also the Levenshtein Automatons used by Lucene 4.0 for fuzzy matching ... fun story, although they had to treat some Python code as a "black box" when implementing it ...

http://java.dzone.com/news/lucenes-fuzzyquery-100-times

Looks like some interesting research and dev going on in this space at the moment.