Published by Dimitris Kougioumtzis · Updated
Allow insertions, deletions, substitutions and adjacent transpositions, including repeated edits of the same substring.
Track the last source occurrence of each target character and the last matching target column in the current row. Compare ordinary edit steps with a transposition spanning those earlier occurrences.
When to use Damerau-Levenshtein distance
Measuring spelling differences when swapped adjacent characters should count as one edit.
Choosing an alternative
Restricted optimal-string-alignment distance forbids editing a substring repeatedly. This unrestricted variant allows repeated edits: ca to abc costs two, whereas restricted OSA costs three.
Worked example: input and state changes
Example input
ca | abc
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initialize guarded distance matrix; outer row/column hold infinity.
State at this checkpoint
{ "values": [ 5, 5, 5, 5, 5, 5, 0, 1, 2, 3, 5, 1, 0, 0, 0, 5, 2, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 5, "result": 0 }Step 2: Compare ordinary edits with transposition via last matching rows 0, 0.
State at this checkpoint
{ "values": [ 5, 5, 5, 5, 5, 5, 0, 1, 2, 3, 5, 1, 1, 2, 0, 5, 2, 0, 0, 0 ], "active": [ 13, 0 ], "kind": "matrix", "columns": 5, "result": 0 }Step 4: Compare ordinary edits with transposition via last matching rows 0, 0.
State at this checkpoint
{ "values": [ 5, 5, 5, 5, 5, 5, 0, 1, 2, 3, 5, 1, 1, 2, 2, 5, 2, 1, 0, 0 ], "active": [ 17, 0 ], "kind": "matrix", "columns": 5, "result": 0 }Step 5: Compare ordinary edits with transposition via last matching rows 0, 1.
State at this checkpoint
{ "values": [ 5, 5, 5, 5, 5, 5, 0, 1, 2, 3, 5, 1, 1, 2, 2, 5, 2, 1, 2, 0 ], "active": [ 18, 1 ], "kind": "matrix", "columns": 5, "result": 0 }Step 7: Unrestricted Damerau-Levenshtein distance: 2.
State at this checkpoint
{ "values": [ 5, 5, 5, 5, 5, 5, 0, 1, 2, 3, 5, 1, 1, 2, 2, 5, 2, 1, 2, 2 ], "active": [], "kind": "matrix", "columns": 5, "result": 2 }
Expected final state
Unrestricted Damerau-Levenshtein distance: 2.
Complexity and input bounds
Family: Strings. Time complexity: O(nm) time and space.
Implementation detail: Unit insertion, deletion, substitution and adjacent transposition costs; strings contain up to twelve lowercase letters and can be empty. Downloads use a guarded matrix of at most 196 cells and return distance only. This view does not reconstruct a transposition alignment.
Space complexity: O(nm + alphabet size) auxiliary storage plus recorded matrix frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
source | target; each 0..12 lowercase letters. Unrestricted distance; this is not optimal-string-alignment distance.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Do not replace the last-occurrence recurrence with a two-cell transposition shortcut. Initialize the infinity guard row and column, and update last source occurrences after completing each row.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 | // Lowercase ASCII integer arrays a/b with n/m 0..12; empty strings supported. Returns unrestricted Damerau-Levenshtein distance with unit insertion, deletion, substitution and adjacent transposition costs. Maintains last occurrences and a guarded (n+2)*(m+2) matrix; repeated edits of a substring are allowed. This is not restricted optimal-string-alignment distance: ca -> abc costs 2. O(nm) time and space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, b, m) { let d = Array(256).fill(0); let last = Array(256).fill(0); let s = m+2; let inf = n+m; let matched = 0; let i1 = 0; let j1 = 0; let cost = 0; let value = 0; let trans = 0; d[0] = inf; for (let i = 0; i <= n; i++) { d[(i+1)*s] = inf; d[(i+1)*s+1] = i; } for (let j = 0; j <= m; j++) { d[j+1] = inf; d[s+j+1] = j; } for (let i = 1; i <= n; i++) { matched = 0; for (let j = 1; j <= m; j++) { i1 = last[b[j-1]]; j1 = matched; cost = 1; if (a[i-1] == b[j-1]) { cost = 0; matched = j; } value = d[i*s+j]+cost; if (d[(i+1)*s+j]+1 < value) { value = d[(i+1)*s+j]+1; } if (d[i*s+j+1]+1 < value) { value = d[i*s+j+1]+1; } trans = d[i1*s+j1]+(i-i1-1)+1+(j-j1-1); if (trans < value) { value = trans; } d[(i+1)*s+j+1] = value; } last[a[i-1]] = i; } return d[(n+1)*s+m+1]; } |
Source
The Lowrance-Wagner extension supplies the unrestricted adjacent-transposition recurrence. The playground uses unit costs satisfying the paper cost restrictions, not restricted optimal-string-alignment distance.
- An Extension of the String-to-String Correction Problem
Roy Lowrance; Robert A. Wagner (1975). Primary research for unrestricted transposition distance. - The String-to-String Correction Problem
Robert A. Wagner; Michael J. Fischer (1974). Research paper.