Levenshtein alignment reconstruction: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Levenshtein alignment reconstruction example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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": []
    }
  2. 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": []
    }
  3. 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": []
    }
  4. 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": []
    }
  5. 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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.