Every other Approximate Match entry on this site answers a
question about one pair: one pattern against one text, or one string against one other
string. A real spell checker or autocomplete box usually isn't asking that — it's asking "which of
these ten thousand dictionary words are close to what I just typed?" Running
Edit Distance once per candidate, from scratch, wastes
an enormous amount of work whenever candidates share a prefix: cat, cap,
car, cart, and care all start identically, yet a per-word
table pays for that shared ca five separate times, once per word. Precisely formalized
by Klaus Schulz and Stoyan Mihov, a Levenshtein automaton fixes
this by building one structure from the query word and a max edit distance k, then
walking a trie of the whole dictionary against it — every
shared prefix computed exactly once, and an entire branch skipped the instant it's provably out of
budget, before a single word hanging off it is ever touched. This is the real mechanism behind
Lucene's and Elasticsearch's fuzzy-match queries, which build exactly this kind of automaton at
query time and intersect it with a compressed trie of the index.
The trie below holds 18 words: bad, bat, cap, car, care, cart, cast, cat, coat, cost,
cot, dog, dot, dote, zest, zip, zone, zoo. Type a query and pick a max distance
k, then press Step or Run to walk the trie
depth-first. Each node's label shows the character it adds; the automaton's whole "memory" at that
node is one row of edit-distance values, printed in the log as it's computed. A node lights up
green (match) if it's a real stored word within k edits, amber
(real word, too far) if it's stored but over budget, and every node still gray
when the walk ends never had its row computed at all — an entire branch pruned in one decision
the moment its own row proves nothing below it can recover.
Leave bound on correct (row minimum) and try
cat at k = 1: the walk visits 25 of the trie's 35 nodes and finds 8
matches (bad — no, bat, cap, car, cart, cast, cat, coat, cot), pruning the unrelated z
branch (zip/zoo/zone/zest) and the back half of dot/dote without ever
computing their rows. Raise k to 2 and the budget covers nearly everything — 33 of
35 nodes visited, only 2 pruned, 12 matches. Switch bound to
broken (row's last value) and the walk visits exactly one node — the
root — and reports zero matches, for any k up to the query's own length. See
Pitfalls for why.
The automaton's "state" at any point in the walk is exactly one row of the classic
Edit Distance recurrence — the same
three-way minimum (match for free, or pay one edit for the cheapest of substitute, delete, insert)
that page's whole table computes, here computed one row at a time as the walk descends one more
character into the trie. Row i holds, for every prefix length j of the
query, the edit distance between the trie path so far (length i) and that prefix of
the query — exactly Edit
Distance's own dp[i][j], just indexed by trie depth instead of by a second whole
string.
The prune rule leans on one fact: extending the trie path further (moving to row
i+1, i+2, …) can only ever match or exceed the smallest value
already sitting in row i at the point the final column is eventually reached — every
extra character forces at least one more edit somewhere, never fewer. So the moment every entry in
the current row exceeds k, no word hanging off this node, however it continues, can
ever come back within budget. That's a stronger and cheaper check than looking at the row's
last entry alone (see Pitfalls) — the same "a whole region is provably out of reach, skip
it without checking a single cell inside it" idea
Banded Edit Distance uses to skip
table cells more than k off the diagonal, applied here to skip whole trie subtrees
instead.
What's built and stepped through here is the practical, widely-used construction (the one Steve
Hanov's well-known "Levenshtein distance using a trie" write-up popularized): recompute a real row
of m+1 numbers at every node, in O(m) — or O(k), banding the
row the same way Ukkonen bands the table — work per step. Schulz and Mihov's actual paper goes
further: because only rows shaped like "small integers within k of each other" ever
occur, the number of distinct rows reachable for a given (word, k) is finite
and can be enumerated once in advance, turning the whole thing into a true finite-state machine
whose transitions are table lookups — O(1) per character, independent of both
m and k, after an upfront cost to build the table. This page builds the
row explicitly every time, which is simpler to verify and just as correct, at the cost of that
extra per-step factor.
nextRow is the one-character extension of the recurrence; search
walks the trie depth-first, pruning on the row's minimum:
function nextRow(prevRow, ch, word) {
const m = word.length;
const row = [prevRow[0] + 1]; // one more trie character = one more forced deletion at j=0
for (let j = 1; j <= m; j++) {
const del = prevRow[j] + 1;
const ins = row[j - 1] + 1;
const sub = prevRow[j - 1] + (ch === word[j - 1] ? 0 : 1);
row.push(Math.min(del, ins, sub));
}
return row;
}
function search(trieRoot, word, k) {
const matches = [];
const rootRow = Array.from({ length: word.length + 1 }, (_, j) => j);
function recurse(node, row, prefix) {
if (node.isEnd && row[row.length - 1] <= k) matches.push(prefix);
if (Math.min(...row) > k) return; // whole subtree provably out of budget
for (const [ch, child] of node.children) {
recurse(child, nextRow(row, ch, word), prefix + ch);
}
}
recurse(trieRoot, rootRow, '');
return matches;
}Verified from scratch before writing anything above: a seeded 5,000-trial stress harness built
random small dictionaries (5-19 words, alphabet {a,b,c}, length 1-6) and random
(query, k) pairs, comparing this trie-pruned search against an independent brute-force
check (compute Edit Distance against every dictionary
word directly, keep the ones ≤ k) — 5,000/5,000 identical result sets. Self-tested the
harness by swapping in the broken bound below; it disagreed with brute force on 985 of 2,000
further trials, confirming the check has teeth. The exact functions above were then extracted from
the shipped page and re-run through a fake-DOM harness driving the real Step/Run controls on the
18-word demo dictionary, reproducing the precise visited/pruned/match counts quoted in Try It.
Pruning on the row's last value instead of its minimum doesn't prune too little — it
fails completely, in exactly the regime the technique exists for. Row 0 (the root, before
a single trie character has been read) is always [0, 1, 2, …, m] — the cost of
turning an empty string into each prefix of the query, which is unavoidably m at the
last position. Check that last value against k instead of the row's minimum, and for
any k < m the very first check already fails, before the walk descends into a
single child. Measured directly on the shipped demo's 18-word dictionary: for "cat"
(m = 3) at k = 1 or k = 2, the broken bound visits exactly 1
node — the root — and returns zero matches, silently, no error, for a word that's sitting right in
the dictionary. Once k grows to meet or exceed m, the same bug stops
mattering at all: the last value can never exceed a k that's already at least as big
as the whole query, so nothing gets pruned and the walk degrades to a plain, correct, unpruned
traversal of every node — slow, but no longer wrong. The bug is invisible exactly when
k is large enough to not need pruning, and total exactly when pruning is the entire
point.
The saving is proportional to shared prefixes, not to dictionary size. A
dictionary where no two words share a single leading character gets no benefit from the trie at
all — every root-to-word path is its own isolated chain, and the walk still computes one full row
per character of every word, the same total work Edit Distance would do run once per word. The
18-word demo dictionary above shows real savings (96 row-cells computed at k = 1
versus 320 cells a naive per-word Edit Distance table would fill) specifically because five of its
words share the prefix ca and three share zo/z — a
dictionary of real English words, which shares prefixes constantly, is exactly the case this
technique was built for.
Time: in the row-rebuilt form shown here, O(V·m), where
V is the number of trie nodes actually visited (never more than the trie's total node
count, and typically far fewer once pruning kicks in) and m is the query length —
or O(V·k) banding each row the way
Banded Edit Distance bands its table, since
only entries within k of the current trie depth can ever matter. In the true
finite-state form Schulz and Mihov describe, each visited node costs O(1) regardless
of m or k, after a one-time table-building cost that depends on
k alone — the form real search engines ship, since one automaton gets reused across
every node of a large, static index. Space: O(m) for the active row
at any single node in this page's version — the recursion holds one row per stack frame, each of
length m + 1.
This only pays off against a structure that actually shares prefixes across candidates — a trie, or the compressed DAWG/FST real engines use — never against a flat list checked one word at a time, which is exactly what Bitap with Edit Distance, Banded Edit Distance, and Damerau-Levenshtein Distance compute instead — one pair at a time, with nothing to share between candidates. For a side-by-side comparison across all eleven approximate-match entries, see Choosing an Approximate String Matcher.