The site's ninth approximate match entry, and the second
that answers Levenshtein Automaton's question —
which of many candidates are close to a query — with a completely different mechanism. The automaton
computes an exact, bounded edit distance by walking a trie in lockstep with the query. This page never
computes an edit distance at all: it slices every string into overlapping 3-character windows
("trigrams"), scores two strings by how many windows they share, and only ever examines a candidate an
inverted index says shares at least one window with the query — everything else is
skipped without being touched. It's a heuristic, not an exact distance, and it's the real mechanism
behind PostgreSQL's pg_trgm extension and a large share of production fuzzy-search
autocomplete.
The dictionary below is the same 18 words the Levenshtein Automaton demo uses: bad, bat, cap, car, care, cart, cast, cat, coat, cost, cot, dog, dot, dote, zest, zip, zone, zoo. Type a query, pick a threshold, and every word scoring at or above it (Dice coefficient over shared trigrams) is highlighted as a candidate. Shared trigrams are shown in bold.
Leave the query at cat with threshold 0.30: four words clear the bar (cat, bat, cap, car). Now watch cot in the table below it — a single-letter change from cat, the exact same edit distance as bat/cap/car — sitting at a flat 0.000, tied with words that share nothing with "cat" at all. See Pitfalls for why.
| word | trigrams (shared in bold) | score |
|---|
1. Pad and slice. Wrap the string in a single boundary space on each side (so
cat becomes " cat "), then take every overlapping 3-character window:
" ca", "cat", "at ". The padding matters — without it, a
window like "cat" could sit anywhere inside a longer word instead of anchoring to the
string's own start or end. (Some real implementations, PostgreSQL's pg_trgm among them,
pad more heavily to weight prefix windows further; this page uses one space per side to keep the
count simple and the demo table readable.)
2. Build one inverted index for the whole dictionary. For every word, for every
trigram it contains, record that word under that trigram's bucket. cat's three trigrams
each get a bucket entry; car shares " ca" with it, so both words end up in
that one bucket together.
3. A query only ever touches its own buckets. Slice the query into its own
trigrams, look up each one's bucket, and union the results — that union is the entire candidate set.
A word sharing zero trigrams with the query is never scored, never even glanced at, no matter how
large the dictionary is. Querying cat against this page's 18-word dictionary touches
exactly 8 candidates (bat, cap, car, care, cart, cast, coat, cat itself) — the other 10 are skipped
by the index before any scoring happens at all.
4. Score what's left with the Dice coefficient. For candidate word,
count the shared trigrams (matching duplicates one-for-one, not just checking set membership) and
divide by 2 · shared / (|query trigrams| + |word trigrams|). A perfect match scores 1;
no shared windows scores 0. This is a similarity heuristic, not a distance — there's no triangle
inequality to lean on, and (see Pitfalls) no guarantee that a lower true edit distance means a higher
score.
function trigrams(s) {
const padded = ' ' + s.toLowerCase() + ' ';
const out = [];
for (let i = 0; i + 3 <= padded.length; i++) out.push(padded.slice(i, i + 3));
return out;
}
function trigramSimilarity(a, b) {
const ga = trigrams(a), gb = trigrams(b);
const counts = new Map();
for (const g of ga) counts.set(g, (counts.get(g) || 0) + 1);
let shared = 0;
const used = new Map();
for (const g of gb) {
const cap = counts.get(g) || 0;
const u = used.get(g) || 0;
if (u < cap) { shared++; used.set(g, u + 1); }
}
return (ga.length + gb.length) === 0 ? 0 : (2 * shared) / (ga.length + gb.length);
}
function buildTrigramIndex(dictionary) {
const index = new Map(); // trigram -> Set of words containing it
for (const word of dictionary) {
for (const g of trigrams(word)) {
if (!index.has(g)) index.set(g, new Set());
index.get(g).add(word);
}
}
return index;
}
function search(index, query, threshold) {
const candidates = new Set();
for (const g of trigrams(query)) {
const bucket = index.get(g);
if (bucket) for (const w of bucket) candidates.add(w);
}
// only candidates sharing >= 1 trigram are ever scored — everything
// else in the dictionary is skipped without being touched
return [...candidates]
.map(word => ({ word, score: trigramSimilarity(query, word) }))
.filter(r => r.score >= threshold)
.sort((a, b) => b.score - a.score);
}Checked against the dictionary and query used in the demo above before writing any HTML: querying
cat at threshold 0.30 returns exactly cat (1.000), bat,
cap, and car (0.333 each) — matching the table below. Dropping the threshold
to 0 confirms the index-driven candidate set is exactly 8 words wide, not all 18.
A genuine one-edit match can score a flat zero, indistinguishable from an unrelated word.
Seven of this page's 18 dictionary words are exactly one true edit away from cat
(checked with the site's own Edit Distance algorithm):
bat, cap, car, cart, cast,
coat, and cot. Their trigram Dice scores against cat spread
from 0.333 (bat/cap/car) down to 0.286 (cart/cast/coat) down to a flat 0.000 for
cot — tied with dog, zip, and every other word that shares
literally nothing with the query. The heuristic doesn't preserve true edit-distance order even among
candidates that are, by the exact measure, equally close.
Why cot specifically loses everything: the edit lands on the one character
every trigram of a 3-letter word passes through. cat's three trigrams
(" ca", "cat", "at ") all include the middle letter — change it
(cat → cot) and every trigram changes, wiping the overlap to zero. Changing the
first or last letter instead only poisons two of the three trigrams, leaving one
survivor: bat keeps "at ", car keeps " ca". On a
short string, where an edit lands matters as much as how many edits there are.
No single threshold is fair across string lengths. A one-character substitution
in the middle of a growing string was tested at lengths 3, 4, 6, 8, 12, 16, 24, and 32 characters;
Jaccard similarity against the unedited string climbed from 0.000 at length 3 to
0.455 at length 8 to 0.778 at length 24, then flattened. The same
single edit gets proportionally cheaper to detect as the string grows, because a fixed-size edit only
ever poisons a fixed number of trigrams while the total trigram count keeps growing. A threshold loose
enough to catch a real short-word typo will also wave through long strings that are mostly different;
a threshold strict enough for long strings will silently discard real short-word matches like
cat/cot above.
Building the index: O(n) total, where n is the combined
length of every dictionary word — one pass generating trigrams, one hash-map insert per trigram.
Querying: O(m + hits), where m is the query's own length
and hits is the total size of the posting lists for the query's own trigrams — a word
sharing zero trigrams with the query costs nothing at query time, not even a comparison. That's the
entire performance case for building the index at all: scoring every dictionary word directly, the
way running Damerau-Levenshtein once per word
would, costs O(dictionary size × m) regardless of overlap.
Trigram Similarity and Levenshtein Automaton
now both answer "many candidates at once," from opposite ends: the automaton is exact but needs a
trie built over the dictionary and a chosen edit-distance bound k; this page is
approximate, needs no bound, and is cheaper to build an index for, at the cost of the pitfalls above.
For a side-by-side comparison across all eleven approximate-match entries, see
Choosing an Approximate String Matcher.