Levenshtein Automata

Introduction

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.

Try It: Fuzzy Dictionary Lookup

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">Type a word and choose a maximum edit distance <b>k</b>. The Levenshtein automaton runs each dictionary word through the NFA and lists every match instantly.</p>
<div class="controls">
  <input id="query" type="text" value="kitten" autocomplete="off" spellcheck="false" placeholder="Type a word…" />
  <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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Levenshtein Automaton (NFA simulation via bit-parallel row update).
// The NFA has states (i, e): position i in query, e errors so far.
// We represent the active NFA state-set as a row of the DP matrix and
// advance it character by character through the input word.
//
// editDistance(a, b) — classic DP, O(|a|*|b|)
function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({length: m + 1}, (_, i) => i);
  for (let j = 1; j <= n; j++) {
    let prev = dp[0];
    dp[0] = j;
    for (let i = 1; i <= m; i++) {
      const tmp = dp[i];
      dp[i] = b[j-1] === a[i-1]
        ? prev
        : 1 + Math.min(prev, dp[i], dp[i-1]);
      prev = tmp;
    }
  }
  return dp[m];
}

// levenshteinAccepts(query, word, k) — runs word through the NFA for (query, k).
// Uses the row-by-row DP approach: dp[i] = min edits to match query[0..i-1]
// against word[0..j-1]. Accept iff dp[m] <= k after consuming all of word.
// Also handles deletions (epsilon transitions) via a forward pass after each char.
function levenshteinAccepts(query, word, k) {
  const m = query.length;
  // dp[i] = edit distance between query[0..i-1] and the prefix of word consumed so far
  let dp = Array.from({length: m + 1}, (_, i) => i);
  // Clamp to k+1 (anything beyond k is "too far")
  dp = dp.map(v => Math.min(v, k + 1));
  for (let j = 0; j < word.length; j++) {
    const c = word[j];
    const next = new Array(m + 1);
    next[0] = dp[0] + 1;
    for (let i = 1; i <= m; i++) {
      const sub = dp[i-1] + (query[i-1] === c ? 0 : 1);
      const del = dp[i] + 1;
      const ins = next[i-1] + 1;
      next[i] = Math.min(sub, del, ins, k + 1);
    }
    dp = next;
    // Early exit: if every state exceeds k, no path can recover
    if (Math.min(...dp) > k) return false;
  }
  return dp[m] <= k;
}

// Dictionary: 120 common English words
const DICT = [
  'kitten','sitting','kitchen','mitten','bitten','written','smitten','kipper',
  'bitter','litter','glitter','twitter','knitter','kite','kit','kid','kin',
  'king','ring','sing','sting','string','spring','bring','thing','think',
  'thin','than','that','chat','cat','bat','hat','rat','mat','sat','fat',
  'flat','flab','flag','flaw','claw','clay','play','plan','clan','can',
  'van','ban','bin','bit','sit','hit','fit','fix','six','mix','max',
  'map','cap','cup','cut','but','bus','bug','bun','sun','run','rut',
  'nut','net','set','jet','yet','yep','yes','bay','day','say','pay',
  'way','war','car','bar','far','fan','fun','gun','gut','guy',
  'gym','gem','get','got','god','good','food','mood','moon','soon',
  'spoon','tooth','booth','book','look','cook','hook','took','wood',
  'wool','cool','pool','fool','tool','school','rule','role','pole',
  'hole','mole','sole','sale','tale','pale','male','vale','gale'
];

function run() {
  const query = document.getElementById('query').value.toLowerCase().trim();
  const k = parseInt(document.getElementById('k').value, 10);
  const resultsEl = document.getElementById('results');
  const infoEl = document.getElementById('info');
  resultsEl.innerHTML = '';

  if (!query) { infoEl.textContent = 'Type a word to start.'; return; }

  const matches = [];
  for (const word of DICT) {
    const d = editDistance(query, word);
    if (levenshteinAccepts(query, word, k)) {
      matches.push({ word, d });
    }
  }
  matches.sort((a, b) => a.d - b.d || a.word.localeCompare(b.word));

  infoEl.textContent =
    matches.length === 0
      ? 'No matches — try a larger k.'
      : fmt('%length% match(es) in %length2%-word dictionary (k = %k%).', { length: matches.length, length2: DICT.length, k: k });

  if (matches.length === 0) {
    resultsEl.innerHTML = '<span class="none">No words within that distance.</span>';
    return;
  }
  for (const { word, d } of matches) {
    const chip = document.createElement('span');
    chip.className = 'chip ' + (d === 0 ? 'exact' : d === 1 ? 'near' : 'far');
    chip.title = fmt('edit distance %d%', { d: d });
    chip.textContent = word + (d > 0 ? ` (+${d})` : '');
    resultsEl.appendChild(chip);
  }
  console.log('Query:', query, '| k:', k, '| matches:', matches.map(m => m.word + ':' + m.d).join(', '));
}

document.getElementById('query').addEventListener('input', run);
document.getElementById('k').addEventListener('change', run);
run();

<p class="hint">Type a word and choose a maximum edit distance <b>k</b>. The Levenshtein automaton runs each dictionary word through the NFA and lists every match instantly.</p>
<div class="controls">
  <input id="query" type="text" value="kitten" autocomplete="off" spellcheck="false" placeholder="Type a word…" />
  <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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Levenshtein Automaton (NFA simulation via bit-parallel row update).
// The NFA has states (i, e): position i in query, e errors so far.
// We represent the active NFA state-set as a row of the DP matrix and
// advance it character by character through the input word.
//
// editDistance(a, b) — classic DP, O(|a|*|b|)
function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({length: m + 1}, (_, i) => i);
  for (let j = 1; j <= n; j++) {
    let prev = dp[0];
    dp[0] = j;
    for (let i = 1; i <= m; i++) {
      const tmp = dp[i];
      dp[i] = b[j-1] === a[i-1]
        ? prev
        : 1 + Math.min(prev, dp[i], dp[i-1]);
      prev = tmp;
    }
  }
  return dp[m];
}

// levenshteinAccepts(query, word, k) — runs word through the NFA for (query, k).
// Uses the row-by-row DP approach: dp[i] = min edits to match query[0..i-1]
// against word[0..j-1]. Accept iff dp[m] <= k after consuming all of word.
// Also handles deletions (epsilon transitions) via a forward pass after each char.
function levenshteinAccepts(query, word, k) {
  const m = query.length;
  // dp[i] = edit distance between query[0..i-1] and the prefix of word consumed so far
  let dp = Array.from({length: m + 1}, (_, i) => i);
  // Clamp to k+1 (anything beyond k is "too far")
  dp = dp.map(v => Math.min(v, k + 1));
  for (let j = 0; j < word.length; j++) {
    const c = word[j];
    const next = new Array(m + 1);
    next[0] = dp[0] + 1;
    for (let i = 1; i <= m; i++) {
      const sub = dp[i-1] + (query[i-1] === c ? 0 : 1);
      const del = dp[i] + 1;
      const ins = next[i-1] + 1;
      next[i] = Math.min(sub, del, ins, k + 1);
    }
    dp = next;
    // Early exit: if every state exceeds k, no path can recover
    if (Math.min(...dp) > k) return false;
  }
  return dp[m] <= k;
}

// Dictionary: 120 common English words
const DICT = [
  'kitten','sitting','kitchen','mitten','bitten','written','smitten','kipper',
  'bitter','litter','glitter','twitter','knitter','kite','kit','kid','kin',
  'king','ring','sing','sting','string','spring','bring','thing','think',
  'thin','than','that','chat','cat','bat','hat','rat','mat','sat','fat',
  'flat','flab','flag','flaw','claw','clay','play','plan','clan','can',
  'van','ban','bin','bit','sit','hit','fit','fix','six','mix','max',
  'map','cap','cup','cut','but','bus','bug','bun','sun','run','rut',
  'nut','net','set','jet','yet','yep','yes','bay','day','say','pay',
  'way','war','car','bar','far','fan','fun','gun','gut','guy',
  'gym','gem','get','got','god','good','food','mood','moon','soon',
  'spoon','tooth','booth','book','look','cook','hook','took','wood',
  'wool','cool','pool','fool','tool','school','rule','role','pole',
  'hole','mole','sole','sale','tale','pale','male','vale','gale'
];

function run() {
  const query = document.getElementById('query').value.toLowerCase().trim();
  const k = parseInt(document.getElementById('k').value, 10);
  const resultsEl = document.getElementById('results');
  const infoEl = document.getElementById('info');
  resultsEl.innerHTML = '';

  if (!query) { infoEl.textContent = 'Type a word to start.'; return; }

  const matches = [];
  for (const word of DICT) {
    const d = editDistance(query, word);
    if (levenshteinAccepts(query, word, k)) {
      matches.push({ word, d });
    }
  }
  matches.sort((a, b) => a.d - b.d || a.word.localeCompare(b.word));

  infoEl.textContent =
    matches.length === 0
      ? 'No matches — try a larger k.'
      : fmt('%length% match(es) in %length2%-word dictionary (k = %k%).', { length: matches.length, length2: DICT.length, k: k });

  if (matches.length === 0) {
    resultsEl.innerHTML = '<span class="none">No words within that distance.</span>';
    return;
  }
  for (const { word, d } of matches) {
    const chip = document.createElement('span');
    chip.className = 'chip ' + (d === 0 ? 'exact' : d === 1 ? 'near' : 'far');
    chip.title = fmt('edit distance %d%', { d: d });
    chip.textContent = word + (d > 0 ? ` (+${d})` : '');
    resultsEl.appendChild(chip);
  }
  console.log('Query:', query, '| k:', k, '| matches:', matches.map(m => m.word + ':' + m.d).join(', '));
}

document.getElementById('query').addEventListener('input', run);
document.getElementById('k').addEventListener('change', run);
run();

Result

Console

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.

How the Automaton Works

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/levenshtein-automata/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Fuzzy matching at the speed of a finite automaton