Published by Dimitris Kougioumtzis · Updated
Compute unit-cost edits and trace an optimal alignment backward. Ties prefer a diagonal match/substitution, then deletion, then insertion.
Compute prefix-to-prefix edit costs, then walk backward from the final cell. Record a match, substitution, deletion or insertion at each predecessor step and reverse the operations to obtain a forward alignment.
When to use Levenshtein alignment reconstruction
Explaining an edit distance with an actual optimal character alignment.
Choosing an alternative
The existing edit-distance view reports the cost matrix. This view also serializes a deterministic optimal alignment; Damerau-Levenshtein additionally permits adjacent transpositions.
Worked example: input and state changes
Example input
kitten | sitting
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: Rows are source prefixes; columns are target prefixes. Initialize empty-prefix edits.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 8, "result": 0, "output": [] }Step 13: Choose match/substitution, deletion or insertion.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 1, 1, 2, 3, 4, 5, 6, 7, 2, 2, 1, 2, 3, 4, 5, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 22 ], "kind": "matrix", "columns": 8, "result": 0, "output": [] }Step 25: Choose match/substitution, deletion or insertion.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 1, 1, 2, 3, 4, 5, 6, 7, 2, 2, 1, 2, 3, 4, 5, 6, 3, 3, 2, 1, 2, 3, 4, 5, 4, 4, 3, 2, 1, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 36 ], "kind": "matrix", "columns": 8, "result": 0, "output": [] }Step 38: Choose match/substitution, deletion or insertion.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 1, 1, 2, 3, 4, 5, 6, 7, 2, 2, 1, 2, 3, 4, 5, 6, 3, 3, 2, 1, 2, 3, 4, 5, 4, 4, 3, 2, 1, 2, 3, 4, 5, 5, 4, 3, 2, 2, 3, 4, 6, 6, 5, 4, 0, 0, 0, 0 ], "active": [ 51 ], "kind": "matrix", "columns": 8, "result": 0, "output": [] }Step 50: Optimal alignment uses 3 edits. Operation codes: 0 match, 1 substitute, 2 delete, 3 insert.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 1, 1, 2, 3, 4, 5, 6, 7, 2, 2, 1, 2, 3, 4, 5, 6, 3, 3, 2, 1, 2, 3, 4, 5, 4, 4, 3, 2, 1, 2, 3, 4, 5, 5, 4, 3, 2, 2, 3, 4, 6, 6, 5, 4, 3, 3, 2, 3 ], "active": [], "kind": "matrix", "columns": 8, "result": 3, "output": [ 7, 1, 107, 115, 0, 105, 105, 0, 116, 116, 0, 116, 116, 1, 101, 105, 0, 110, 110, 3, -1, 103 ] }
Expected final state
Optimal alignment uses 3 edits. Operation codes: 0 match, 1 substitute, 2 delete, 3 insert.
Complexity and input bounds
Family: Strings. Time complexity: O(nm) time and space.
Implementation detail: Strings have at most twelve lowercase letters and may be empty. Backward ties prefer a diagonal match/substitution, then deletion, then insertion. Downloads return the distance and write an operation count followed by kind/source/target triples, using -1 for a gap.
Space complexity: O(nm) cost matrix plus O(n+m) alignment output and saved animation 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. Gaps are shown as a dash in explanations.
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
Several optimal alignments can exist. Match steps cost zero, gaps consume a character on only one side, and reconstructed operation order must be reversed after backward traversal.
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 13 14 15 16 | // a/b are lowercase ASCII integer codes, n/m 0..12. Returns unit-cost Levenshtein distance and writes an optimal alignment. Output capacity at least 1+3*(n+m): [operation count, then triples (kind, source code, target code)]. Kinds 0 match, 1 substitute, 2 delete, 3 insert; gap code -1. Canonical backward tie order diagonal, deletion, insertion. Match triples cost zero; every other triple costs one. Empty strings supported. 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, output) { let d = Array(256).fill(0); let s = m+1; let value = 0; let cost = 0; for (let i = 0; i <= n; i++) { d[i*s] = i; } for (let j = 0; j <= m; j++) { d[j] = j; } for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { cost = 1; if (a[i-1] == b[j-1]) { cost = 0; } value = d[(i-1)*s+j-1]+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; } d[i*s+j] = value; } } let reverse = Array(256).fill(0); let row = n; let column = m; let count = 0; let op = 0; let fromValue = -1; let toValue = -1; while (row > 0 || column > 0) { cost = 1; if (row > 0 && column > 0 && a[row-1] == b[column-1]) { cost = 0; } fromValue = -1; toValue = -1; if (row > 0 && column > 0 && d[row*s+column] == d[(row-1)*s+column-1]+cost) { op = cost; row--; column--; fromValue = a[row]; toValue = b[column]; } else { if (row > 0 && d[row*s+column] == d[(row-1)*s+column]+1) { op = 2; row--; fromValue = a[row]; } else { op = 3; column--; toValue = b[column]; } } reverse[count*3] = op; reverse[count*3+1] = fromValue; reverse[count*3+2] = toValue; count++; } output[0] = count; for (let k = 0; k < count; k++) { for (let t = 0; t < 3; t++) { output[1+k*3+t] = reverse[(count-1-k)*3+t]; } } return d[n*s+m]; } |
Source
Primary Wagner-Fischer dynamic-programming research, including correction sequences. The playground uses unit costs and an explicit deterministic alignment tie order.
- The String-to-String Correction Problem
Robert A. Wagner; Michael J. Fischer (1974). Research paper.