levenshtein_automata

levenshtein_automata is a Rust crate that constructs a deterministic finite automaton (DFA) which computes the Levenshtein (edit) distance between a fixed query string and any input, up to a chosen maximum distance. Instead of comparing strings one pair at a time, you build a DFA once for the query and then stream bytes of candidate strings through it, reading off the edit distance from the final state.

This makes it ideal for fuzzy search over large dictionaries: the automaton can be intersected with an ordered set or FST to enumerate every term within a given edit distance efficiently. It is the fuzzy-matching engine underpinning the tantivy search library.

What You Get

• A LevenshteinAutomatonBuilder that precomputes a reusable parametric DFA for a given max distance
• Byte-level DFA construction for any query string, returning Exact or AtLeast distances
• Optional Damerau-style transposition handling (treating swaps as a single edit)
• Optional fst feature to intersect the automaton with finite-state transducers for fuzzy dictionary lookup

Common Use Cases

• Fuzzy term matching in a full-text search engine
• Autocomplete and did-you-mean suggestions over a large vocabulary
• Spell checking and approximate string lookup against a dictionary

Under The Hood

Architecture - The crate separates concerns across focused modules: levenshtein_nfa.rs models the nondeterministic Levenshtein automaton, parametric_dfa.rs precomputes a distance-parameterized DFA that is independent of the concrete query, and dfa.rs specializes that parametric DFA into a concrete byte-level DFA for a given string. alphabet.rs groups input bytes into equivalence classes to shrink transition tables, and index.rs/lib.rs expose the builder and public types. The design follows Schulz and Mihov’s parametric-automaton approach so per-query construction is fast.

Tech Stack - Pure Rust (edition 2018) with no required runtime dependencies; an optional fst feature (feature flag fst_automaton) enables integration with finite-state transducers. levenshtein is used only as a dev-dependency for cross-checking distances in tests.

Code Quality - Around 1,700 lines total with a substantial tests.rs (~430 lines) plus benches, giving good confidence in correctness across distances and transposition modes. Module boundaries map cleanly to the algorithm’s stages.

API Design - The public flow is deliberate: create a LevenshteinAutomatonBuilder once (noted as not free), then call build_dfa per query, drive it with initial_state/transition, and read distance. The API is small but assumes familiarity with automata concepts, so the learning curve is moderate for callers new to DFA-based matching.