I used to use Lucene back in the 1.x days when a fuzzy search was a complete table scan. It was quite a surprise to see how your single term fuzzy query was interpreted as one term query for each fuzzy hit OR-ed together. The Lucene team soon realized they needed to code a levenstein automaton but none of them had ever done that before. They pulled several all-nighters reading math papers and coding and when they succeeded they were so happy they told the world about it [0]. It's a great story.
https://dzone.com/articles/lucenes-fuzzyquery-100-times