This site has eleven approximate match entries now — Bitap, Bitap with Edit Distance, Banded Edit Distance, Myers Diff, Damerau-Levenshtein Distance, Jaro-Winkler Similarity, Soundex, Levenshtein Automaton, Trigram Similarity, BK-Tree, and Smith-Waterman — each one built, verified, and explained on its own page. What none of them individually answer is the question a visitor with a real problem actually has: which one do I reach for? This is the site's first guide — a cross-cutting page that compares existing entries instead of adding a new algorithm — and it exists because that question kept getting harder to answer from seven separate pages, each reasonably believing it was the only one you'd read.
"Approximate matching" is doing a lot of work as an umbrella term. It quietly bundles two different problems that don't share a good default answer, plus two more things that aren't really matching at all. Sort by which one you actually have first — the algorithm choice mostly follows from there.
Problem A: find a short pattern somewhere inside a much longer text, tolerating some number of typos. The text is big; the pattern is small; you're scanning for occurrences, not comparing two things of similar size. This is Bitap's and Bitap with Edit Distance's job — think typo-tolerant search inside a document, or a grep that forgives one dropped letter.
Problem B: given two whole strings (or sequences) of comparable size, how different are they? There's no "text" and no "pattern" here, just two things being compared directly. This is Banded Edit Distance, Myers Diff, and Damerau-Levenshtein Distance's job — think spell correction against a dictionary word, or diffing two versions of a file.
Also not quite Problem B: only a region of each sequence needs to match, and the rest can be completely unrelated. Every algorithm in Problem B accounts for both inputs end to end — even the parts that share nothing. A Smith-Waterman alignment doesn't: it finds the best-scoring matching region inside two sequences and simply ignores whatever surrounds it, however different that surrounding material is. Think a shared gene fragment between two otherwise-unrelated DNA reads, or a quoted excerpt buried in two much longer, unrelated documents.
Not really either one: score how alike two strings are, without counting edits at all. Jaro-Winkler Similarity sits outside both problems above — no scan, no edit count, just a bounded-window character match turned into a 0-to-1 score. It answers "how similar," not "how many edits" or "where does it occur."
Not a distance or a score at all: would these be filed under the same phonetic bucket? Soundex doesn't compare the two strings to each other in any of the senses above — it encodes each one independently into a fixed-width code, then checks the codes for exact equality. No graded answer, no edit count, no scan: either the codes match or they don't.
None of the above, if the real question is about many candidates at once. Every entry so far assumes exactly two things being compared — one pattern and one text, or one string and one other string. A Levenshtein Automaton answers a differently-shaped question: given one query and a whole dictionary of candidates, which ones are close enough — without paying full price per candidate the way running any entry above once per dictionary word would.
Both Bitap variants pack "which prefixes of the pattern could still be mid-match" into the bits
of a machine word and slide it across the text one character at a time — one shift, one AND, one OR
(or a small constant more) per text character, regardless of how far into the pattern that
character lands. The catch is the same for both: the whole trick depends on the pattern fitting in
one machine word. A pattern longer than the word width w still works, but picks up a
further ⌈m / w⌉ factor — the bit-parallel advantage erodes as the pattern grows.
Between the two: plain Bitap tolerates only substitutions
(O(n) exact, O(n·k) with k allowed substitutions) — a dropped
or inserted character breaks it, because every window it checks is locked to the pattern's exact
length. Bitap with Edit Distance (Wu-Manber)
closes exactly that gap, adding insertions and deletions to the same bit-parallel machine at roughly
double the constant factor per error level, still O(n·k). Reach for plain Bitap when
typos are substitution-shaped (OCR misreads, single-character swaps); reach for the edit-distance
version when a dropped or extra character is plausible too (typed search queries, user-entered
text).
All three of these compute an edit distance (or the edits themselves) between two whole inputs, building on the same idea as the site's unrestricted Edit Distance dynamic-programming table — but each restricts or reshapes that table for a different reason. Three questions decide between them:
Do you know a small upper bound on the answer before you start? If a spell
checker only cares about matches within 2 edits of a dictionary word, or an aligner only cares about
reads within a handful of mismatches, most of Edit Distance's full O(m·n) table is
wasted work — no cell more than k off the main diagonal can ever be part of an
optimal path of cost ≤ k. Banded Edit Distance
(Ukkonen's algorithm) restricts the table to that diagonal band, dropping the cost to O(k ·
min(m, n)) time and space. The trade: guess k too small and the algorithm
reports "impossible" instead of the true distance — you have to already have a reasonable estimate,
or be willing to retry with a larger band.
Do you need the actual edit script, not just a count, and would rather not guess a
bound at all? Myers Diff never needs a
k — it searches outward by number of edits D = 0, 1, 2, … across the
diagonals of the edit graph and stops the instant a path reaches the far corner, so it discovers the
true distance by construction in O((N+M)·D) time. That's also the shape a real line-
oriented diff/git diff needs: not just "how different," but the literal
list of insertions and deletions to turn one sequence into the other. The trade is that Myers Diff
(as built on this site) only permits insertions and deletions, not substitutions — it's built for
diffing sequences of lines or tokens, not for scoring word-level typos.
Do adjacent-swap typos matter, and do you want the exact answer over the full table
rather than a bounded one? Damerau-
Levenshtein Distance keeps Edit Distance's complete O(m·n) table (no band, no
guessing) and adds a fourth edit type: swapping two adjacent characters costs one edit instead of
two substitutions, catching the extremely common "recieve" → "receive" typo shape in a single move.
It's the practical default for spell-checkers and fuzzy autocomplete specifically because
transpositions are common enough in real typing to be worth the extra table check. One caveat
carried over from its own page: the cheap, widely-shipped version (Optimal String Alignment,
implemented here) isn't the true unrestricted transposition distance — it disagrees with it, and
fails the triangle inequality, once an insertion or deletion mixes with a transposition.
Every entry in Problem B computes a distance (or an edit script) that accounts for all of both inputs — a mismatched opening or closing stretch still gets charged, edit by edit, even when it's not the part anyone actually cares about. Smith-Waterman answers a structurally different question: given two sequences, is there a region inside one that closely resembles a region inside the other, regardless of what either sequence looks like outside that region? It reuses Edit Distance's own table-filling recurrence almost verbatim — score instead of count edits, and add one extra option at every cell: reset to zero instead of carrying a negative running score forward. That single change is the whole mechanism: a bad flank can never drag a good match elsewhere in the table down with it, because the table forgets and restarts instead of accumulating. The cost of that freedom is real, though: because the highest score can land anywhere in the table (not necessarily the bottom-right corner every Problem B entry reports from), finding the answer means scanning the whole table for its maximum, not reading one fixed cell — a checked example on that page shows the corner cell landing on a real wrong answer specifically because of this.
Jaro-Winkler Similarity doesn't fill a table or pack
a bit-parallel word at all. It finds which characters can pair up within a bounded window, counts
how many paired characters are out of order, and rewards a shared beginning — producing a 0-to-1
score in O(|A| · window) time, cheaper in practice than a full table despite sharing
its worst-case order. It was built for, and is still the default for, short strings where a shared
beginning is genuinely informative: names, usernames, product codes, database deduplication. Two
things make it a poor fit outside that niche: the window that keeps it cheap can also make it blind
to a rearrangement that spans the whole string (a swap outside the window is silently discarded, not
counted), and it is not a proper metric — the triangle inequality can fail, which matters if
something downstream (nearest-neighbor pruning, some clustering algorithms) assumes it holds.
Soundex throws away almost everything the other six
entries pay attention to. It doesn't compare the two inputs to each other at all during encoding —
it converts each one independently to a 4-character code (first letter kept literally, remaining
consonants mapped to one of six digit groups, vowels and Y dropped and resetting an adjacent-merge
rule that H and W are exempt from) and only checks the two codes for equality afterward.
O(n) time, O(1) space, and an answer that's either "match" or "no match" —
no partial credit, no bound to guess. That's exactly right for the problem it was built for in 1918
(filing U.S. Census surnames so that spelling variants land together) and exactly wrong for anything
needing a graded answer: Bard/Board/Beard/Bird/
Byrd all collide on the identical code despite being unrelated words, while true
homophones Knight/Night get completely different codes because the first
letter is never folded into the same digit groups as the rest of the string. Reach for it only when
an exact phonetic-bucket equality check is genuinely the question — a name-matching index, not a
similarity ranking.
Every entry above — including all three of Problem B's edit-distance variants — assumes the
comparison is against one fixed candidate. Run one of them once per dictionary word and the total
cost is proportional to the dictionary's size, no matter how much those words overlap. A Levenshtein Automaton instead builds one structure
from the query and a max edit distance k, then walks a trie of the whole dictionary against it: every shared prefix
computed exactly once, and an entire branch skipped the moment its own edit-distance row proves
nothing below it can recover — the shipped demo visits 25 of 35 trie nodes for one query at
k = 1, pruning the rest without ever touching the words hanging off them. This is the
real mechanism behind Lucene's and Elasticsearch's fuzzy-match queries, not a novelty built for this
site. The trade: it only pays off against a structure that shares prefixes across candidates (a
trie, or the compressed DAWG/FST real search engines use) — checked one at a time against a flat
list, it does no better than calling Damerau-Levenshtein or Banded Edit Distance directly.
Willing to trade exactness for a cheaper index and no bound to guess? Trigram Similarity answers the same "many candidates"
question with a different trade entirely: no edit-distance computation at all, just an inverted index
from every 3-character window ("trigram") to the words containing it, scored by how many windows two
strings share. Building it costs nothing upfront in the way choosing the automaton's k
does, and a candidate sharing zero windows with the query is skipped by the index before it's ever
scored. The cost is real: it's a heuristic, not a distance, and (see that page's own Pitfalls) a
genuine one-edit match can score a flat zero against a short query, tied with words sharing nothing
with it at all — reach for the automaton instead whenever you need the exact edit-distance guarantee,
not just a fast approximate filter.
Have a genuine metric distance and want an exact guarantee without building a trie or an index at all? A BK-Tree answers the same "many candidates" question a third way: no shared-prefix structure, no n-gram windows, just the distance function's own triangle inequality, used to arrange the dictionary into a tree once and then prove whole subtrees can't match without ever computing a distance inside them. The cost is real too, just a different one from either alternative above: the tree's shape (and so the number of nodes any one query actually touches) is entirely a function of insertion order, and — unlike the automaton or Trigram Similarity, which both compute their own distance from scratch — a BK-tree's correctness depends on the caller supplying a distance that's a genuine metric in the first place; feeding it this site's own Damerau-Levenshtein page's non-metric OSA distance produces a tree that silently drops real matches, checked concretely on that page.
| Entry | Answers | Time | Needs a bound k up front? | Reach for it when |
|---|---|---|---|---|
| Bitap | does the pattern occur, ≤k substitutions | O(n) / O(n·k) | no (k is a dial, not a guess) | typo-tolerant search, substitutions only, pattern fits a machine word |
| Bitap w/ Edit Distance | does the pattern occur, ≤k any edits | O(n·k) | no (k is a dial, not a guess) | same, but drops or extra characters are plausible too |
| Banded Edit Distance | minimum edit count, if ≤ k | O(k·min(m,n)) | yes — too-small k reports "impossible" | you already have a good estimate of how close the strings are |
| Myers Diff | minimum edit count + the edit script itself | O((N+M)·D) | no — discovers D by construction | diffing two sequences, no substitution, need the actual edits |
| Damerau-Levenshtein | minimum edit count, incl. adjacent transposition | O(m·n) | no — full table | spell-check / autocomplete, transposition typos matter |
| Jaro-Winkler | similarity score, 0 to 1 (not an edit count) | O(|A|·window) | no | short strings — names, usernames, dedup — not long text |
| Soundex | same phonetic code or not — no partial credit | O(n) | no | exact phonetic-bucket equality — name indexing, not similarity ranking |
| Levenshtein Automaton | which dictionary candidates are ≤k edits away, all at once | O(V·m), V = trie nodes visited | yes — a dial, like the Bitap variants | many candidates sharing prefixes (spell-check dictionary, autocomplete index) |
| Trigram Similarity | heuristic overlap score, all candidates at once — not an exact edit distance | O(m + hits) per query, index built in O(n) | no bound to guess — but no exactness guarantee either | fast approximate dictionary-wide filtering (pg_trgm-style fuzzy search) |
| BK-Tree | which dictionary candidates are ≤k away, all at once — exact, if the distance is a metric | O(n·depth) build; query has no fixed bound, typically far fewer than n nodes touched | no bound to guess — k is only chosen at query time | exact matching against a fixed dictionary, no trie/index to build or maintain |
| Smith-Waterman | best-matching region between two sequences, ignoring the rest | O(m·n) | no — the floor at zero replaces any bound | local alignment: DNA/protein matching, a shared fragment buried in unrelated text |
The site's own unrestricted Edit Distance — the plain
O(m·n) table with no band, no diagonal search, no bit-packing, allowing insert, delete,
and substitute with no bound on how many — sits underneath more of this guide than any single entry
admits on its own: Bitap with Edit Distance and
Banded Edit Distance restrict it to a bounded
window, Myers Diff and
Damerau-Levenshtein reshape its table or add an
edit type, the Levenshtein Automaton and
BK-Tree both reuse it directly (as a row recurrence and
as a plug-in distance function, respectively) rather than reshaping it at all, and Smith-Waterman adds a single extra option — reset to zero —
to the same recurrence to turn a global comparison into a local one. If none of the entries
above fit your actual problem — the inputs are small enough that O(m·n) is cheap
outright, or you want the simplest possible correct baseline before optimizing anything — that
unrestricted table is still the right place to start.
This is the site's first guide page — a new content type alongside the algorithm and data-structure entries, for when a family has grown large enough that comparing its members is more useful to a reader than adding a seventh. See the journal for how and why that decision got made.