Edit Distance and the Shape of a Two-Dimensional Table

The edit distance between two strings is the minimum number of single-character insertions, deletions, and substitutions that transform one into the other. The dynamic program that computes it fills a rectangle whose cell (i, j) holds the distance between the length-i prefix of the first string and the length-j prefix of the second. That rectangle is the most drawn table in computer science, and the reason it is worth re-examining is that almost every property of the algorithm — its time, its space, its reconstruction behaviour, its practical optimizations — is a statement about the geometry of the grid rather than about the recurrence.

Three edges into each cell

Let A have length m and B length n, with A[i] and B[j] one-indexed. The recurrence is

D[0][j] = j
D[i][0] = i
D[i][j] = min( D[i-1][j] + 1,          # delete A[i]
               D[i][j-1] + 1,          # insert B[j]
               D[i-1][j-1] + (A[i] != B[j]) )   # substitute, or match at cost 0

Each cell reads the cell above, the cell to the left, and the cell diagonally up-left. Three edges per vertex, (m+1)(n+1) vertices, so the running time is Θ(mn) and the table is Θ(mn) cells. The base row and column encode transforming a prefix into the empty string, which costs one deletion or insertion per character.

The diagonal edge is the one that carries the structural information. It advances both strings by one character, so it represents either a match at zero cost or a substitution at cost one. The vertical and horizontal edges advance one string only, so they represent insertions and deletions. Every alignment of the two strings corresponds to a monotone lattice path from (0,0) to (m,n) using these three steps, and the distance is the minimum-weight such path. Reading the grid as a DAG makes the correspondence exact: an alignment is a path, and the DP is a shortest-path computation on a grid.

This is the same graph formulation as the state-graph treatment of recurrences, specialized to a planar graph with bounded out-degree. The special structure is what makes the space optimizations possible: because every edge moves either right, down, or diagonally, the computation can be swept in a fixed direction and cells can be discarded once no future cell needs them.

The table has an edit-distance structure of its own

The distance matrix is not arbitrary. Adjacent cells differ by at most 1, because moving one step in either string changes the distance by at most one edit. Values along any row or column are non-decreasing, since a longer prefix cannot be easier to transform. The diagonal difference D[i][j] − D[i-1][j-1] is bounded by the substitution cost and is therefore 0 or 1 when that cost is 1, and a match forces it to 0.

These properties are the basis for the practical optimizations. The most important is banding: if the two strings are known to be within distance k, no cell with |i − j| > k can lie on an optimal path, because each unit of offset requires at least one insertion or deletion to correct. Restricting the computation to a diagonal band of width 2k + 1 reduces the work from Θ(mn) to Θ(k·min(m,n)), which for small k is nearly linear. The correspondence is exact in both directions: a path of weight at most k exists inside the band if and only if the distance is at most k and a witness stays inside it, and a path leaving the band has already paid more than k in insertions and deletions alone. The cost is that the band computes distances only up to k; if the true distance exceeds it, the band returns the threshold rather than the distance.

Banding is used in the other direction too. When two long strings are compared for near-identity — two versions of a source file, two reads from a sequencing instrument — the distance is small relative to the length, and the band turns a quadratic computation into a linear one. When the distance is large, the band must widen to min(m,n) and the saving vanishes.

Two rows, and what they cost

The recurrence reads only row i-1 to compute row i, so two rows of n+1 cells suffice for the value. A single row also works, with a saved scalar for the diagonal.

def edit_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, 1):
            cur[j] = min(prev[j] + 1,            # delete ca
                         cur[j - 1] + 1,         # insert cb
                         prev[j - 1] + (ca != cb))
        prev = cur
    return prev[-1]

The prev[j - 1] term is the diagonal, and it is why a naive single-row version needs a temporary variable holding the old prev[j] before it is overwritten. ca != cb evaluates to a boolean, which Python treats as 0 or 1 in arithmetic; in C the same idiom is (a[i-1] != b[j-1]) and in Rust u8::from(a != b). Languages that do not coerce booleans need an explicit conditional.

Space drops from Θ(mn) to Θ(min(m,n)) by iterating the shorter string along the row axis, which is a real improvement when one string is much longer than the other: comparing a 10-character pattern against a 10^6-character text uses 10 cells per row rather than 10^7.

The cost is reconstruction. With two rows, the path cannot be traced back because the cells it would need were overwritten. Recovering the alignment needs the full matrix, or one bit per cell recording which of the three transitions attained the minimum. That bit matrix is mn bits — for two strings of length 10^4, about 12.5 MB, versus 400 MB for a 4-byte-per-cell matrix. Storing the bit and rerunning the walk is often the best available compromise.

Hirschberg: linear space and full reconstruction

Hirschberg’s algorithm recovers the alignment in O(n) space and O(mn) time, with no bit matrix. The construction is a divide-and-conquer over the rows of the grid.

Choose the middle row mid = ⌊m/2⌋. Compute the forward distance vector from (0,0) to every cell (mid, j) — that is one pass of the two-row DP over the first half. Compute the backward distance vector from (m,n) to every cell (mid, j) — another pass over the second half, run on the reversed strings. For each j, the sum of the two values is the cost of the best path that crosses row mid at column j. Take the j that minimizes the sum. That column is on some optimal path. Recurse on the two sub-rectangles (0,0) to (mid, j*) and (mid, j*) to (m,n).

The space bound follows because the recursion is depth-first: at each level only a constant number of vectors of length n are live, and the levels are processed one at a time, so peak space is O(n) regardless of depth. The time recurrence is T(m, n) = 2·T(m/2, n) + Θ(mn), whose solution is Θ(mn) because the total area of the sub-rectangles at each level is at most mn and the number of levels is O(log m).

The subtlety is that the split must be at a column that lies on an optimal path, and the argmin of the summed forward and backward vectors provides exactly that. A split at a column not on any optimal path would force the recursion to compute sub-distances that do not add up to the global optimum, and the reconstruction would be wrong while the value remained right — a failure mode that passes any test comparing only distances.

Variants change the transition, not the grid

The grid geometry survives changes to the cost model; only the three edges change.

Damerau-Levenshtein adds transposition of two adjacent characters as a single edit. The transition must then read D[i-2][j-2], which means the recurrence refers two rows back and the two-row space optimization needs three rows. A full unrestricted transposition model — where a substring can move arbitrarily far — is more expensive and is not a simple grid DP.

Longest common subsequence is edit distance with insertion and deletion at cost one and no substitution. The table is identical; for that insert/delete-only metric the distance is m + n − 2·LCS(m,n), because each string contributes one deletion per character not in the common subsequence, so the two computations differ only in which cells the traceback follows. Allowing substitutions changes the metric — two strings that share no characters would be at distance max(m, n) rather than m + n — so the identity does not carry over to the substitution cost of two.

Affine gap costs, used in biological alignment, charge a penalty for opening a gap and a smaller one for extending it. A single cell cannot express “currently inside a gap”, so the state gains a mode component and the table becomes three matrices — one for each of match, gap-in-A, gap-in-B — each referring to the others. This is a direct application of the sufficiency rule set out in state sufficiency: the extra dimension is required because the cost of the next step depends on how the previous step ended.

Weighted edit distance assigns per-character costs, so a substitution of a for b may cost more than one deletion plus one insertion. The recurrence is unchanged; only the three constants differ, and the metric properties (symmetry, triangle inequality) may no longer hold, which matters if the distance is used for indexing or clustering.

Where the quadratic bound is unacceptable

For strings of length in the millions — genomes, log files, large documents — Θ(mn) is infeasible regardless of constants. Three families of technique apply, and they are not DP in the strict sense.

The first is filtering: compute a cheap lower bound (character-frequency difference, q-gram profiles) and discard candidate pairs whose bound exceeds the threshold. This is how approximate matching systems avoid running the grid at all for most pairs.

The second is the bit-parallel approach, which packs one row of the DP into machine words and computes 64 or 128 cells per word operation using bitwise arithmetic. The result is the same recurrence with a factor equal to the word size, not a different algorithm.

The third is the Four Russians technique, which precomputes the effect of a block of the grid on the boundary vector. Because the boundary vector’s values differ by at most one and are non-decreasing, its normalized form has few distinct values, and the block transition can be looked up rather than computed. The resulting bound is Θ(mn / log n), a genuine asymptotic improvement obtained by exploiting the constrained shape of the values.

All three exploit the same fact: the DP’s state at a row boundary is not an arbitrary vector but one with bounded structure. Recognizing that structure is what separates a textbook implementation from one that handles real input sizes.