What's new
- Levenshtein DFA mode: Compiled DFA for ~3x faster traversal (higher one-time startup cost)
- Damerau-Levenshtein DFA mode: Handles transpositions as single edits (e.g., "teh" → "the" at distance 1)
- Algorithm selection: New
algorithm parameter ("bit-parallel" or "dfa") in both C++ and Python APIs
- Metric selection: New
metric parameter ("levenshtein" or "damerau") for choosing distance metric
Python API
# Levenshtein bit-parallel (default, same as before)
results = fst.fuzzy_search("algoritm", 2)
# Levenshtein DFA — faster traversal, higher startup cost
results = fst.fuzzy_search("algoritm", 2, algorithm="dfa")
# Damerau-Levenshtein — transpositions count as one edit
results = fst.fuzzy_search("teh", 1, metric="damerau")Performance (370K-word dictionary, i5-9600K)
| Distance |
Lev BitParallel |
Lev DFA |
Damerau DFA |
| d=1 |
53 us |
17 us |
21 us |
| d=2 |
498 us |
168 us |
209 us |
| d=3 |
2,525 us |
924 us |
989 us |
