Lucene's FuzzyQuery is 100 times faster in 4.0 (2011)
blog.mikemccandless.com