Levenshtein Automata

Every time you type "recieve" and your phone quietly fixes it to "receive", something elegant has run in the background. That something is rooted in edit distance — the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into another.

Edit distance was formalized by the Soviet mathematician Vladimir Levenshtein in 1965. Computing it for two strings of length $n$ takes $O(n^2)$ time via dynamic programming — perfectly fine for one pair, but potentially slow when you need to check a query against a dictionary of millions of words.

The key insight is that you don't need to compute edit distance one pair at a time. Instead, you can build a nondeterministic finite automaton (NFA) from the query word such that the automaton accepts exactly the set of all strings within edit distance $k$. That automaton can be run over every dictionary word in linear time in the word's length — no matter how long or complex the query. The result is fuzzy search that scales like a regular expression, not like an all-pairs distance matrix.

Type any word in the box below and choose a maximum edit distance $k$. The automaton runs each dictionary word through the NFA and lists every match in real time.

<p class="hint">{{hint}}</p>
<div class="controls">
  <input id="query" type="text" value="kitten" autocomplete="off" spellcheck="false" placeholder="{{placeholder}}" />
  <label>k =
    <select id="k">
      <option value="0">0</option>
      <option value="1" selected>1</option>
      <option value="2">2</option>
      <option value="3">3</option>
    </select>
  </label>
</div>
<div id="info" class="info"></div>
<div id="results" class="results"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; gap: .6rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
input[type=text] { font: 15px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid #adb1b8;
                   border-radius: 8px; width: 200px; }
select { font: 15px system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #adb1b8;
         border-radius: 8px; }
label { font-size: .95rem; display: flex; align-items: center; gap: .35rem; }
.info { font-size: .88rem; color: #555; margin-bottom: .5rem; min-height: 1.3em; }
.results { display: flex; flex-wrap: wrap; gap: .35rem; max-height: 220px; overflow-y: auto; }
.chip { font: 14px ui-monospace, monospace; padding: .25rem .6rem; border-radius: 6px;
        background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.chip.exact { background: #0a7d33; color: #fff; border-color: #085e27; }
.chip.near  { background: #1d3557; color: #fff; border-color: #152540; }
.chip.far   { background: #c9ccd1; color: #333; border-color: #adb1b8; }
.none { font-size: .95rem; color: #888; font-style: italic; }

// Code not found

Notice what happens as you raise $k$: the match set grows, and words that differ by several edits start appearing. At $k = 0$ only exact matches pass; at $k = 1$ one-character typos are caught; at $k = 2$ you're tolerating two errors at once. The automaton does not recompute a full distance matrix — it processes each word in a single left-to-right scan, just like a regex engine. This is related to how pattern matching engines work efficiently under the hood.

The construction is elegant. Fix a query string $q$ of length $m$ and a tolerance $k$. The NFA has states $(i, e)$ where $i \in \{0,\ldots,m\}$ is a position in $q$ and $e \in \{0,\ldots,k\}$ is the number of errors accumulated so far.

• Match (no error): reading character $q[i]$ moves from $(i, e)$ to $(i{+}1, e)$.
• Substitution (1 error): reading any character $c \neq q[i]$ moves from $(i, e)$ to $(i{+}1, e{+}1)$.
• Insertion (1 error): reading any character moves from $(i, e)$ to $(i, e{+}1)$ — the input advances but the query position doesn't.
• Deletion (1 error): an $\varepsilon$-transition moves from $(i, e)$ to $(i{+}1, e{+}1)$ — the query position advances without consuming input.

The automaton accepts if it reaches any state $(m, e)$ with $e \leq k$ after reading the entire input word. The total number of states is $O(k \cdot m)$, and each input character is processed in $O(k)$ time, giving $O(k \cdot |word|)$ per dictionary word — linear in the word length.

This construction was proven correct by Levenshtein (1965) and is exact: the automaton accepts a string $w$ if and only if the true edit distance $d(q, w) \leq k$. No approximation, no false negatives. The NFA can also be determinized (converted to a DFA) for lookups that are even faster in practice, though the DFA may have exponentially more states in the worst case.

Efficient fuzzy matching powered by Levenshtein automata shows up everywhere strings meet real-world noise:

• Spell-checking and autocorrect: word processors and mobile keyboards use edit-distance search to suggest the closest dictionary word to a mistyped query.
• Search engines: query expansion with $k = 1$ or $k = 2$ tolerates user typos without requiring exact keyword matches.
• DNA sequence alignment: biological sequences diverge through mutations (substitutions), insertions, and deletions — exactly the three edit operations. Approximate string matching is a core primitive in bioinformatics tools like BLAST.
• OCR post-processing: optical character recognition often produces near-miss strings; edit-distance lookup corrects them against a known vocabulary.
• Approximate indexes: production databases (Elasticsearch, Lucene) build Levenshtein automata on the fly to implement fuzzy queries.

The relationship to sequence alignment is deep: the standard dynamic-programming table for edit distance is the same table used in global alignment, just without gap penalties varying by position.

Levenshtein automata are a beautiful example of turning a distance into a machine. Instead of measuring how far apart two strings are, you build an automaton from the query that recognizes all close strings at once — and run it in linear time over every candidate.

The construction is exact (proven by Levenshtein in 1965), efficient ($O(k \cdot m)$ states, $O(k \cdot |word|)$ per lookup), and practical (it powers the fuzzy search in your phone, your search engine, and your genome browser). The next time autocorrect silently fixes "teh" to "the", you know which machine made the call — and why it could afford to check the whole dictionary in a blink.