The site's fifth approximate match entry, and a direct
extension of Edit Distance. Edit distance allows three
edits — insert, delete, substitute — and charges one full edit for a two-character typo like
teh → the, since it has to substitute e→h and
h→e separately. Damerau–Levenshtein distance adds a fourth edit: swapping
two adjacent characters counts as a single edit instead of two substitutions. It's named
for Fred Damerau, who found that transpositions, along with the original three edit types, accounted
for the overwhelming majority of real spelling errors in a 1964 study — exactly the "recieve" →
"receive" shape of mistake below.
Fixed pair A = "recieve", B = "receive" — a real, common misspelling:
the i and e at positions 4 and 5 are swapped, nothing else differs. Press
Step or Run to fill the table. In Damerau–Levenshtein
mode, watch cell dp[5][5] reach two rows and two columns back instead of one — that's
the transposition check — and settle the whole distance at 1. Switch the mode
dropdown to Levenshtein (no transposition) and rerun on the identical pair: without
that fourth option the same table can only substitute twice, and the distance comes back
2 — same input, same table shape, only the recurrence's option set differs.
The base cases and the first three options are exactly
Edit Distance's own recurrence: match costs
nothing, substitute/delete/insert each cost dp[i-1][j-1]/dp[i-1][j]/
dp[i][j-1] plus one. The new option only applies when the current and previous character
of each string are a swapped pair of each other — A[i-1] = B[j-2] and
A[i-2] = B[j-1] — and when it applies, it proposes dp[i-2][j-2] + 1: whatever
it cost to align everything before both swapped characters, plus one edit for the swap itself,
skipping past both positions at once instead of one. The full recurrence keeps whichever of the four
options is cheapest:
dp[i][j] = min(
dp[i-1][j-1] + (A[i-1] === B[j-1] ? 0 : 1), // match or substitute
dp[i-1][j] + 1, // delete A[i-1]
dp[i][j-1] + 1, // insert B[j-1]
dp[i-2][j-2] + 1 // transpose, only when A[i-1]=B[j-2] and A[i-2]=B[j-1]
)On "recieve"/"receive", every cell before dp[5][5] matches
plainly (r, e, c all line up), so by the time the table reaches
position 5 the diagonal, up, and left neighbors all still cost 1 apiece to fix the swap the ordinary
way — but the transposition option reaches back to dp[3][3], which is still 0 (nothing to
fix yet), plus 1 for the swap. That's why the distance lands on 1 instead of 2.
This variant — restricted to whole, non-overlapping edits, never re-touching a pair of characters
once they've been transposed — is called Optimal String Alignment (OSA) distance. It's
the version almost every practical spell-checker and fuzzy-match library actually ships, because it's
just Edit Distance's table with one more O(1) check per cell. See Pitfalls for why "OSA"
and "Damerau–Levenshtein distance" are not quite the same thing, despite OSA being the version most
people mean when they say the latter.
function osaDistance(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const cost = a[i - 1] === b[j - 1] ? 0 : 1;
let best = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
best = Math.min(best, dp[i - 2][j - 2] + 1); // adjacent transposition
}
dp[i][j] = best;
}
}
return dp[m][n];
}OSA distance and true Damerau–Levenshtein distance are two different numbers, and they
disagree on real string pairs. OSA's rule above forbids ever re-touching a character that was
part of a transposition — each pair of positions gets edited at most once. The true (unrestricted)
Damerau–Levenshtein distance allows a transposed pair to be edited again afterward, and that
extra freedom can find a cheaper path. Take A = "CA", B = "ABC": the true
distance is 2 — transpose CA → AC (one edit), then insert
B between them to get ABC (one more edit) — but that second edit touches the
C that was just transposed, which OSA's rule forbids. Run the reference implementation
above on this exact pair and it reports 3
(insert A, substitute C→B, substitute A→C), because it's barred from the cheaper route.
Verified computationally, not just asserted: a brute-force comparison of OSA against a from-scratch
implementation of the true (unrestricted) algorithm found no divergence at all between the two over
every string pair up to length 5 on a two-letter alphabet — the gap only opens once insertion is mixed
with transposition on the same characters, exactly what this example does.
A consequence of the gap above: OSA distance is not a proper metric. A real
distance function has to satisfy the triangle inequality — d(x, z) ≤ d(x, y) + d(y, z),
detouring through a third point can never be shorter. OSA breaks it on the very same three strings:
osa("CA", "AC") = 1 (one transposition) and osa("AC", "ABC") = 1 (one
insert), so a walk through "AC" costs 2 — but osa("CA", "ABC") = 3 directly,
which is more than the two-step detour. True Damerau–Levenshtein distance doesn't have this
problem, which is one real reason to reach for it over OSA when an algorithm downstream (nearest-neighbor
search, clustering) actually depends on the triangle inequality holding — not just as a theoretical
nicety.
Only adjacent transpositions get the discount — a swap split across other characters is
priced as ordinary substitutions, same as plain Levenshtein. "converse" and
"conserve" differ by swapping their v and s, but those letters
sit three characters apart (converse vs. conserve), not next
to each other. The transposition check above only ever compares A[i-1]/A[i-2]
against B[j-2]/B[j-1] — a strictly adjacent pair — so it never fires here.
Checked directly against the reference implementation: both this page's osaDistance and a
plain Levenshtein distance (no transposition option at all) return the same answer, 2,
on this pair. Recognizing "these two letters got swapped somewhere in the word" in general is a
different, harder problem than this page's algorithm solves.
Time: O(m·n) — the transposition check adds one constant-time
comparison to each of the (m+1)(n+1) cells
Edit Distance's own table already fills, so the
asymptotic cost is unchanged. Space: O(m·n) for OSA distance shown here
(each cell only ever reads back two rows, so a rolling three-row window would work for the distance
alone, the same trade Edit Distance's own
space-optimized mode makes for one row); the true unrestricted algorithm in Pitfalls needs an
additional small table indexed by alphabet character and is not implemented on this page.
OSA distance is the practical default for spell-checkers, fuzzy autocomplete, and typo-tolerant search — cheap to compute, and transpositions are common enough in real typing mistakes that the fourth edit type pays for itself, even with the restriction Pitfalls names. For the version of this idea packed into a single bit-parallel machine word instead of a full table, see Bitap with Edit Distance (Wu–Manber), which supports substitutions, insertions, and deletions but not transposition. For a table restricted a different way — by distance from the diagonal instead of by which edits are allowed — see Banded Edit Distance (Ukkonen's Algorithm). A sixth entry, Jaro-Winkler Similarity, shares this page's interest in transpositions but drops the dynamic-programming table entirely — and it isn't a proper metric either, for a reason of its own checked on that page. For a side-by-side comparison across all eleven approximate-match entries, see Choosing an Approximate String Matcher.