The site's tenth approximate match entry, and a third
mechanism answering Levenshtein Automaton and
Trigram Similarity's own question — which of many
candidates are close to a query — from a different angle than either. Both of those need structure
imposed on the dictionary itself: the automaton needs a trie built from shared character prefixes,
Trigram Similarity needs an inverted index built from overlapping 3-character windows. A BK-tree
(named for its inventors, Burkhard and Keller) needs neither. All it asks of the distance function is
that it obey the triangle inequality — d(x, z) ≤ d(x, y) + d(y, z),
detouring through a third point can never be shorter — and it uses that one guarantee to arrange a
fixed dictionary into a tree once, then skip entire subtrees during a query without ever computing a
distance for anything inside them.
The dictionary is the same 18 words the Levenshtein Automaton and Trigram Similarity demos use:
bad, bat, cap, car, care, cart, cast, cat, coat, cost, cot, dog, dot, dote, zest, zip, zone,
zoo, built into a tree once (in that order — see Pitfalls for why the order matters) using
plain Edit Distance as the metric. Every edge is labeled
with the real edit distance between the words it connects. Type a query, pick a max distance
k, then press Step or Run to walk the tree. A node
lights up green (match) if its own distance to the query is ≤ k, tan
(visited) if it was checked but is too far, and stays dim (pruned)
if the triangle inequality proved nothing below it could possibly match — its distance is never even
computed.
Leave the query at cat with k = 1: the walk visits 10 of the tree's
18 nodes and finds 8 matches (cat, bat, cap, car, cart, cast, coat, cot) — the same 7 one-edit
neighbors of "cat" Trigram Similarity's own
Pitfalls section names, plus "cat" itself, without ever computing a distance for the other 8
words (dog, dot, dote, zest, zip, zone, zoo, and cost). Raise k to 2 and
the budget covers nearly the whole tree — all 18 nodes visited, 12 matches, nothing left to prune.
1. Building the tree. The first word inserted becomes the root — arbitrarily,
whichever word happens to come first. Every later word w descends from the root: compute
d = distance(node.word, w). If d = 0, w is already in the tree,
stop. If the current node already has a child reached by an edge labeled exactly d,
recurse into that child — don't attach here. Otherwise, attach w as a new child
of the current node, with the edge labeled d. No comparison ever happens between
w and anything outside the single root-to-attachment-point path actually walked.
2. Querying, via the triangle inequality's reverse form. At any node N
storing word N.word, with query q, compute d =
distance(N.word, q). N is a match if d ≤ k. Now consider a child
C reached by an edge labeled e = distance(N.word, C.word). The triangle
inequality guarantees distance(C.word, q) ≥ |e − d| — swap through N.word
and the detour can only ever cost more, never less. So if |e − d| > k, then
distance(C.word, q) is already provably > k, and so is the distance from
everything below C (the same argument reapplies one level further down,
recursively) — the whole subtree is skipped, with not one more distance computed inside it, for the
rest of the query.
This is the same "an entire region is provably out of reach, skip it without checking a single thing inside it" idea Banded Edit Distance uses to skip table cells and Levenshtein Automaton uses to skip trie branches — applied here to a tree keyed directly by distance values, needing no shared prefixes or fixed alphabet at all. Any distance function satisfying the triangle inequality works: edit distance, Hamming distance on fixed-length codes, even non-string metrics. That generality is also the entire risk — see Pitfalls.
function insert(root, word, distance) {
if (!root) return { word, children: new Map() };
let node = root;
for (;;) {
const d = distance(node.word, word);
if (d === 0) return root; // already present
if (node.children.has(d)) {
node = node.children.get(d); // same distance already taken — recurse
} else {
node.children.set(d, { word, children: new Map() });
return root;
}
}
}
function buildTree(words, distance) {
let root = null;
for (const w of words) root = insert(root, w, distance);
return root;
}
function query(root, q, k, distance) {
const matches = [];
(function visit(node) {
const d = distance(node.word, q);
if (d <= k) matches.push(node.word);
for (const [edge, child] of node.children) {
if (Math.abs(edge - d) <= k) visit(child); // triangle-inequality prune
}
})(root);
return matches;
}Verified before writing anything above: a 3,000-trial stress harness built random dictionaries
(5-19 words, lowercase a-z, word lengths 1-6), built each one into a tree under a random
insertion order, queried it with a word mutated 1-2 edits away from a real dictionary entry at a
random k in {0, 1, 2}, and compared the tree's match set against an
independent brute-force scan of the whole dictionary using
Edit Distance directly — 3,000/3,000 identical result
sets, 0 mismatches. 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.
The pruning is only sound if the distance function is a genuine metric — and a distance
function can look reasonable while quietly failing the triangle inequality. This site's own
Damerau-Levenshtein page already proved
this concretely: its restricted OSA distance gives osa("CA", "AC") = 1
and osa("AC", "ABC") = 1, but osa("CA", "ABC") = 3 — a direct detour through
"AC" costs 2, yet the direct distance reports 3, breaking
d(x, z) ≤ d(x, y) + d(y, z) outright. Feed OSA distance into a BK-tree built from just
those three words (root AC, with CA attached at edge 1, and
ABC attached under CA at edge 3, since osa(AC, ABC) = 1 already
matches the existing edge to CA) and query "AC" at k = 1: the
walk visits only 2 of the 3 nodes and reports matches {AC, CA} — ABC is
silently dropped, because at node CA the prune check sees |edge 3 − distance(AC,
CA) = 1| = 2 > 1 and skips it, even though the real, directly-computed osa(AC, ABC) =
1 is well within budget. The tree's own internal bookkeeping (an edge value computed once, at
insert time) is what goes stale here, not the query logic — checked by running the exact
insert/query functions above with OSA distance substituted for Edit
Distance and confirming this exact miss. Reach for a distance proven to satisfy the triangle
inequality (plain Edit Distance, Hamming distance) — never OSA/restricted Damerau-Levenshtein, and
never an ungraded similarity score like Jaro-Winkler,
whose own guide entry notes it isn't a proper metric either.
Tree shape depends entirely on insertion order — correctness doesn't, but the number of
nodes touched per query does. Building the demo's own 18-word dictionary in reverse order
instead produces a different tree (root zoo instead of bad, maximum depth 6
instead of 4) that still returns the identical 8-word match set for "cat" at
k = 1 — but visits all 18 nodes doing it, nearly twice the 10 the forward-order tree
needs. Checked across seven different insertion orders (the dictionary's own order, its reverse, and
five distinct shuffles) for the same query: every single one returned the exact same 8-word match
set, while the number of nodes actually visited ranged from 8 up to 18 — a 2.25x spread from
insertion order alone, on an identical dictionary and an identical query. A BK-tree built once and
queried many times locks in whatever spread its original insertion order happened to produce.
Build: n inserts, each descending the existing tree one edge at a
time until it finds an open slot — the total cost is O(n · depth), where
depth is whatever the tree's actual shape turns out to be (see Pitfalls). Query:
no fixed asymptotic bound holds independent of how the dictionary's own pairwise distances are
distributed — a query with a large enough k, or a pathological distance distribution,
degrades to visiting every node, exactly like the unpruned Levenshtein Automaton's broken-bound
pitfall. What can be measured directly, on this page's own 18-word dictionary in its own insertion
order: "cat" at k = 1 visits 10 of 18 nodes, a real 44% reduction from
having to check the whole dictionary, without needing a trie's shared prefixes or an inverted index's
n-gram overlap the way the other two "many candidates" entries do.
Levenshtein Automaton,
Trigram Similarity, and BK-Tree now all answer "many
candidates at once," each trading a different requirement for a different guarantee: the automaton
needs a trie and a chosen bound k but computes shared prefixes exactly once; Trigram
Similarity needs no bound and no exact distance at all, at the cost of the heuristic's own known
misses; a BK-tree needs no prefix structure and no n-grams, only a genuine metric, at the cost of a
tree shape that's entirely a function of insertion order. For a side-by-side comparison across all eleven
approximate-match entries, see
Choosing an Approximate String Matcher.