Documentation of the Foundational Paper
Date: 2025-11-06 Status: Complete Documentation of Core Algorithms
This directory contains comprehensive documentation for the paper "Fast String Correction with Levenshtein-Automata" by Klaus U. Schulz and Stoyan Mihov. This paper provides the theoretical foundation and core algorithms for the liblevenshtein-rust library.
The paper addresses efficient approximate string matching using deterministic finite automata. The key innovation is showing how to construct, for any input word W and error bound n, a deterministic Levenshtein automaton that accepts exactly all words within Levenshtein distance n from W, in time $\mathcal{O}(\lvert W\rvert)$ for fixed n.
Title: Fast String Correction with Levenshtein-Automata
Authors:
Keywords: Spelling correction, Levenshtein-distance, optical character recognition, electronic dictionaries
Paper Location: /home/dylon/Papers/Approximate String Matching/Fast String Correction with Levenshtein-Automata.pdf
Pages: 64 pages
Publication Type: Technical report / working paper
The Levenshtein distance between two words is the minimal number of insertions, deletions, or substitutions of letters needed to transform one word into the other. The paper shows how to compute, for any fixed bound n and any input word W, a deterministic Levenshtein-automaton of degree n for W in time linear in the length of W.
This automaton accepts exactly all words V where the Levenshtein-distance between V and W does not exceed n. Given an electronic dictionary (implemented as a trie or finite state automaton), the Levenshtein-automaton for W can be used to control search in the lexicon, generating exactly the lexical words V where the Levenshtein-distance between V and W does not exceed the given bound.
In many applications, we need to find "similar" words in a dictionary:
Naive Approach: For each dictionary word, compute Levenshtein distance to input word
\mathcal{O}(\lvert D\rvert \times \lvert W\rvert \times \lvert V\rvert)$ where $\lvert D\rvert$ = dictionary size, $\lvert W\rvert$ = input word length, $\lvert V\rvert$ = dictionary word lengthBetter Approach: Use automata to avoid computing distance for each word
\mathcal{O}(\lvert W\rvert)$ automaton construction + $\mathcal{O}(\lvert D\rvert)$ dictionary traversalTheorem (Main Result): For any fixed degree n, there exists a family of deterministic Levenshtein automata where:
\mathcal{O}(\lvert W\rvert)$ for input word W\lvert W\rvert$L_{\mathrm{Lev}}(n,W) = \{V \mid d_L(W,V) \le n\}$Key Insight: For fixed n, the structure of LEV_n(W) is independent of specific characters in W, only depending on:
Result: Precompute parametric tables T_n that describe all possible states and transitions
Further Optimization: Avoid constructing LEV_n(W) explicitly
Beyond Standard Levenshtein: Extend algorithms to support:
Result: $\mathcal{O}(\lvert W\rvert)$ construction complexity maintained for all variants
theoretical-foundations.md (planned) - Formal definitions, lemmas, theorems, mathematical conceptscore-algorithms.md (planned) - Elementary transitions, automaton construction, parametric tablesextended-operations.md (planned) - Transpositions, merges, splits algorithmsexperimental-results.md (planned) - Performance benchmarks from paper\mathcal{O}(\lvert W\rvert)$ algorithmThe liblevenshtein-rust codebase implements the algorithms from this paper:
Position Structure (/src/transducer/position.rs)
Transition Functions (/src/transducer/transition.rs)
Algorithm Variants (/src/transducer/algorithm.rs)
Algorithm::Standard → Chapters 4-6Algorithm::Transposition → Chapter 7Algorithm::MergeAndSplit → Chapter 8Automaton Construction (/src/transducer/builder.rs, /src/transducer/mod.rs)
The paper provides proofs that the implementation:
\mathcal{O}(\lvert W\rvert)$ construction for fixed n (Theorem 5.2.1)If you want to understand the theory:
theoretical-foundations.md (planned) for formal definitionscore-algorithms.md (planned) for construction proceduresextended-operations.md (planned) for transposition/merge/splitIf you want to understand the code:
core-algorithms.md (planned) for algorithm detailsIf you want to extend the library:
The minimum number of single-character edits (insertions, deletions, substitutions) to transform one word into another.
Example:
d_L("kitten", "sitting") = 3
kitten → sitten (substitute k→s)
sitten → sittin (substitute e→i)
sittin → sitting (insert g)
A finite state automaton that accepts all words within Levenshtein distance n from a given word W.
Formal Definition: $\mathrm{LEV}_n(W)$ is a deterministic automaton such that:
L(\mathrm{LEV}_n(W)) = L_{\mathrm{Lev}}(n,W)$L_{\mathrm{Lev}}(n,W) = \{V \mid d_L(W,V) \le n\}$An expression i#e where:
0 \le i \le \lvert W\rvert$)0 \le e \le n$)Intuition: Position i#e represents "having matched i characters of W with e errors so far"
A bit-vector $\chi(x, W[i])$ indicating where character x appears in the relevant subword of W starting at index i.
Example: For W = "hello", $\chi(\text{'l'}, W[2]) = \langle 1,1,0\rangle$ because:
Position i#e subsumes position j#f if:
e < f$ (fewer errors)\lvert j-i\rvert \le f-e$ (within reachable range)Intuition: If $\pi$ subsumes $\pi'$, then any word accepted from $\pi'$ is also accepted from $\pi$, so $\pi'$ is redundant.
Input: Word W = x₁...xw, degree n
Output: Deterministic Levenshtein automaton LEV_n(W)
Steps:
Define states: Parameterized by boundary index i
Set initial state: q₀ = {0#0}
Set final states: States containing positions i#e where i = |W|
Define transitions: Use table T_n and characteristic vectors
\Delta(M, y) = \bigsqcup_{\pi\in M} \delta(\pi, y)$\delta(\pi, y)$ uses elementary transition tableOptimize: Remove subsumed positions from states
Complexity: $\mathcal{O}(\lvert W\rvert)$ time and space for fixed n
Key Idea: Don't construct LEV_n(W) explicitly; simulate it
Algorithm:
Initialize: stack = [(ε, q₀^D, {0#0})]
While stack not empty:
Pop (V, q^D, M)
For each character x:
Compute q'
= δ^D(q^D, x) // Dictionary transition
Compute M' = Δ_*^W(M, χ(x, W[M])) // Simulated automaton transition
If both valid:
Push (Vx, q', M')
If both accepting: Output Vx
Advantage: States generated on-demand, avoiding upfront construction
Based on experimental results (Chapter 8.3):
The Universal Levenshtein Automata paper (documented in /docs/research/universal-levenshtein/) extends this foundational work:
The paper relates to classical Levenshtein distance computation:
\mathcal{O}(\lvert W\rvert \times \lvert V\rvert)$ time to compute $d_L(W,V)$\mathcal{O}(\lvert W\rvert)$ to build automaton accepting all $V$ with $d_L(W,V) \le n$See glossary.md for complete notation reference
Common symbols:
\Sigma$: Alphabetd_L(W,V)$: Levenshtein distance between words W and VL_{\mathrm{Lev}}(n,W)$: Language of words within distance n from W\chi(x,V)$: Characteristic vector of character x in word V\sqsubseteq$: Subsumption relation\sqcup$: Join operation on states\Delta$: Transition functionAnswer: Deterministic automata enable efficient traversal with no backtracking, crucial for large dictionaries.
\mathcal{O}(\lvert W\rvert)$ construction?Answer: For fixed error bound n, the number of distinct states is bounded by a constant times |W|.
Answer: They encode the minimal information needed to determine transitions, allowing table-driven computation.
Answer: This paper uses uniform cost = 1. For variable costs, see weighted Levenshtein distance (different approach).
Answer: Yes! The algorithms work for any alphabet $\Sigma$. See extended operations (Chapter 8) for biological applications.
If you find errors or have suggestions for improving this documentation:
Documentation follows the Apache-2.0 license (same as liblevenshtein-rust).
Original paper copyright © Klaus U. Schulz and Stoyan Mihov.
Last Updated: 2025-11-06 Status: Complete documentation of foundational paper Next: Read individual documentation files for detailed coverage
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |