Sequence Comparison: LCS, Edit Distance & Diff

Sequence comparison is not one problem. The same two inputs can be compared by asking what they share, how much one must be edited to become the other, or which changes should be shown to a human. Those objectives are related, but they are not interchangeable.

Before choosing an algorithm, define three things:

1. the tokens being compared—bytes, Unicode code points, grapheme clusters, words, lines, syntax nodes, or some domain object;
2. the allowed operations—insert, delete, substitute, move, transpose, or a domain-specific action;
3. the cost and output contract—only a number, one optimal alignment, every optimum, or a readable patch.

Changing any one of these can change both the answer and the suitable algorithm.

Three objectives that are easy to conflate #

Let $X=x_1x_2\ldots x_m$ and $Y=y_1y_2\ldots y_n$ be token sequences.

Longest common subsequence (LCS)

A longest sequence obtainable from both inputs by deleting zero or more tokens without reordering the survivors. Tokens need not be adjacent.

Edit distance

The minimum total cost of an allowed sequence of edits that transforms one input into the other.

Diff

A representation of change, usually as retained, inserted, and deleted token runs. A diff tool must choose an edit objective, but it also makes presentation choices such as tokenization, tie-breaking, context, and hunk boundaries.

For ABCBDAB and BDCABA, an LCS has length 4; BCBA and BDAB are two possible answers. Neither is a substring, because a substring must occupy one contiguous interval. LCS solves order-preserving selection, not contiguous matching.

Unit-cost Levenshtein distance allows insertion, deletion, and substitution, each at cost 1. A conventional line diff instead treats a changed line as one deletion plus one insertion. These models answer different questions: with substitution cost 1, changing one token costs 1; in an insert/delete-only script it costs 2.

LCS as a prefix dynamic program #

Define $L[i,j]$ as the LCS length of prefixes $X[1..i]$ and $Y[1..j]$. An empty prefix has no nonempty common subsequence:

$$L[i,0]=L[0,j]=0.$$

For nonempty prefixes,

$$L[i,j]= \begin{cases} 1+L[i-1,j-1], & x_i=y_j,\\ \max\{L[i-1,j],L[i,j-1]\}, & x_i\ne y_j. \end{cases}$$

The recurrence follows from the last token of an optimum:

• if $x_i=y_j$, one optimum can end with that shared token, leaving an optimum for the two shorter prefixes;
• if they differ, an LCS cannot use both final tokens as the same last element, so it omits at least one of them.

Every dependency has smaller indices, so filling rows from top to bottom and columns from left to right is a valid topological order of the subproblems. There are $(m+1)(n+1)$ states and constant work per state: $O(mn)$ time and, for the full table, $O(mn)$ space.

A small LCS table #

Compare ABC with BAC:

The bottom-right value is 2. Backtracking can produce either AC or BC; the tie at the interior states is real information, not an implementation error.

Edit distance as a shortest path through prefixes #

Define $E[i,j]$ as the minimum cost to transform $X[1..i]$ into $Y[1..j]$. With unit-cost insertion, deletion, and substitution,

$$E[i,0]=i,\qquad E[0,j]=j,$$

and

$$E[i,j]=\min\begin{cases} E[i-1,j]+1 & \text{delete }x_i,\\ E[i,j-1]+1 & \text{insert }y_j,\\ E[i-1,j-1]+[x_i\ne y_j] & \text{match or substitute.} \end{cases}$$

Here $[P]$ is 1 when proposition $P$ is true and 0 otherwise. The formula is exhaustive because the last operation of any transformation must be one of those three cases. Removing that last operation leaves an optimal—or improvable—solution to the corresponding smaller prefix problem.

This table is also a shortest-path computation on an acyclic grid:

• a vertical edge deletes a token from $X$;
• a horizontal edge inserts a token from $Y$;
• a diagonal edge matches equal tokens at cost 0 or substitutes at cost 1.

Nonnegative operation-specific costs fit the same recurrence by replacing each +1. The model must still make semantic sense: a zero-cost edit can collapse distinctions, and negative costs make “perform extra edits” artificially profitable.

Worked trace: kitten to sitting #

The distance is 3. One optimal script is:

1. substitute k with s: sitten;
2. substitute e with i: sittin;
3. insert g: sitting.

The table certifies that no two-edit script exists; the displayed script certifies that three edits suffice. A distance without a script gives only the lower-bound side of that explanation.

The exact LCS–edit-script duality #

LCS and edit distance have a clean identity only for an insert/delete-only model. If $\ell=L[m,n]$, keep the $\ell$ matched tokens, delete the other $m-\ell$ tokens of $X$, and insert the other $n-\ell$ tokens of $Y$. This yields

$$D_{\mathrm{ins/del}}=(m-\ell)+(n-\ell)=m+n-2\ell.$$

Conversely, every insert/delete script leaves some tokens untouched in their original order. Those survivors form a common subsequence, so a shorter script would imply a common subsequence longer than the LCS. The construction is therefore optimal in both directions.

The identity does not hold for unit-cost Levenshtein distance. A substitution can replace the delete-plus-insert pair for half the cost. It does hold if substitution is forbidden or assigned cost 2, although ties may then choose either representation.

Reconstructing an optimum #

A scalar answer needs only the final cell. An edit script or LCS needs the decisions that led there.

With the full table, start at $(m,n)$ and repeatedly move to a predecessor that justifies the current value:

• for LCS, a matching diagonal move emits the shared token; otherwise move toward a neighboring cell with the same maximum value;
• for edit distance, a zero-cost matching diagonal emits “keep,” while a predecessor satisfying the recurrence emits its substitution, deletion, or insertion.

Reverse the emitted operations at the end. Backtracking takes $O(m+n)$ steps for one result.

Ties mean there are multiple optima. A reproducible tool must state a deterministic rule, such as preferring exact matches, then deletions, then insertions. That rule selects one proof path; it does not make the other optimal paths wrong. Enumerating all optima can require exponential output because the table may contain many branching ties.

Reducing memory without losing the objective #

Each DP row depends only on the previous row and the current row’s left neighbor. If only the distance or LCS length is required, keep two rows and place the shorter input on the column axis. Space falls to $O(\min(m,n))$ while time remains $O(mn)$.

def levenshtein(a, b):
    """Unit-cost distance for any indexable token sequences."""
    if len(b) > len(a):
        a, b = b, a

    previous = list(range(len(b) + 1))
    for i, x in enumerate(a, start=1):
        current = [i]
        for j, y in enumerate(b, start=1):
            current.append(min(
                previous[j] + 1,          # delete x
                current[j - 1] + 1,       # insert y
                previous[j - 1] + (x != y),
            ))
        previous = current
    return previous[-1]

This code intentionally cannot reconstruct a script: overwritten rows discard most proof edges.

Hirschberg’s algorithm recovers an LCS in linear working space. It splits one sequence near its midpoint, computes forward LCS lengths against every prefix of the other sequence, computes backward lengths against every suffix, and chooses a split maximizing the sum. It then recursively reconstructs the two halves. The subproblems across each recursion level cover only the original grid area, so the total remains $O(mn)$ time and $O(\min(m,n))$ auxiliary space, excluding the output.

This trade is useful when the $mn$ table is the limiting resource. It may do more passes and have less favorable cache behavior than storing the full table, so “asymptotically less memory” does not imply “always faster.” For data larger than memory, layout and I/O become first-class concerns; see External-Memory Algorithms.

Myers’ edit graph for similar sequences #

For a diff with insertions and deletions, use coordinates $(x,y)$ for consumed prefixes of $X$ and $Y$. A deletion moves right, an insertion moves down, and a maximal run of equal tokens moves diagonally at zero edit cost. Myers’ algorithm explores this graph by increasing edit count $d$.

Let diagonal $k=x-y$. For each $d$, keep the farthest $x$ reached on every feasible diagonal after exactly $d$ edits, then greedily extend the zero-cost matching diagonal—a snake. Reaching $(m,n)$ for the first time proves that $d$ is the minimum insert/delete script length, because all paths using fewer edits were exhausted in earlier layers.

If $N=m+n$ and the minimum script has length $D$, the core method runs in $O(ND)$ time. This is attractive when two files are long but differ in only a few places; it can approach quadratic work when they are very different. Keeping one wavefront suffices for the distance in $O(N)$ space. Straightforward path reconstruction retains historical wavefronts and costs more; Myers also gives a linear-space refinement.

The theoretical algorithm finds a shortest script. A production command named “Myers” may add heuristics or presentation policies. Current Git documentation explicitly distinguishes its default/basic greedy mode from minimal, which spends extra time to ensure the smallest diff, and from patience and histogram, which choose anchors differently. Treat a tool’s documented contract—not an algorithm family name—as authoritative.

Tokenization is part of correctness #

The recurrence compares tokens for equality; it cannot decide what a token ought to mean.

Unicode normalization is not automatically benign. Normalizing before comparison may be correct for search but incorrect for an exact patch, because it can hide a real encoding-level change. Likewise, ignoring whitespace can improve a review view while making the resulting script incapable of reproducing the target bytes.

Where the basic models stop fitting #

• Moves and renames: insert/delete distance represents a moved block as deletion plus insertion. Detecting moves is an additional inference problem.
• Transpositions: swapping adjacent tokens takes two substitutions under ordinary Levenshtein distance; Damerau-style models add a transposition operation and require a different recurrence.
• Biological alignment: substitution scores, affine gap-open/gap-extend penalties, local alignment, and evolutionary interpretation are not plain unit-cost edit distance.
• Structured documents: JSON, XML, or program syntax often needs tree-aware matching so that hierarchy and keys survive token movement.
• Very long sequences: $O(mn)$ time can be prohibitive even with linear memory. Banded DP is effective only when a credible distance bound exists; sparse or domain-indexed methods require additional assumptions.
• Similarity scores: raw distance grows with input length. Normalizing it creates a new metric contract and must specify the denominator and behavior on empty inputs.

If the only question is whether unit edit distance is at most $k$, any successful path stays within $|i-j|\le k$. Computing only that diagonal band reduces work to $O(k\max(m,n))$—or reports immediately when $|m-n|>k$. If every feasible path leaves the band, the correct conclusion is “distance exceeds $k$,” not a clipped distance value.

Choosing the method #

The baseline table is often the right first implementation: it is easy to verify and supports arbitrary local costs. Optimize only after the objective, input scale, and required output are fixed.

Failure patterns and diagnostics #

Three invariants catch most implementation mistakes:

1. every DP cell equals one of the recurrence’s justified alternatives;
2. replaying a reconstructed script exactly produces the target sequence;
3. for insert/delete-only comparison, $D=m+n-2LCS$.

Exercises #

1. Fill the LCS table for BANANA and ATANA. Reconstruct two answers if a tie permits them.
2. Give insertion, deletion, and substitution costs $(1,1,3)$. Explain why an optimum never needs a substitution when delete-plus-insert costs only 2.
3. For two 1,000,000-line files with a ten-line insertion, compare the state counts suggested by full DP and by the $O(ND)$ edit-graph view.
4. Construct two strings whose unit Levenshtein distance differs from their insert/delete distance.