Edit Distance and Sequence Alignment

What This Concept Is

Unit-cost Levenshtein distance transforms source a into target b by insertions, deletions and substitutions; matching equal characters costs zero. Here strings are sequences of Python Unicode code points, without normalization. A user-perceived character can contain several code points, so other tokenizations are different contracts.

Let D(i,j) be the cost for prefixes a[:i] and b[:j]. Empty-prefix bases are D(i,0)=i, D(0,j)=j. For positive i,j:

D(i,j) = min(D(i-1,j) + 1,
             D(i,j-1) + 1,
             D(i-1,j-1) + [a[i-1] != b[j-1]])

The three candidates correspond to the final alignment column: deletion, insertion, or two aligned characters. They exhaust valid alignments. Each removes at least one character, giving induction on i+j.

Why It Matters Here

This makes boundaries, last-decision reasoning and reconstruction visible in one table. It also teaches model discipline: an alignment score is meaningful only after specifying operations, costs, normalization and whether the whole strings or selected substrings must be aligned.

Concrete Examples

For ab -> acb, the prefix table is:

Source prefix / target prefix	empty	a	ac	acb
empty	0	1	2	3
a	1	0	1	2
ab	2	1	1	1

The optimum alignment is (a,a),(gap,c),(b,b), cost 1. The row for an empty source is not all zeros: inserting three target characters costs 3. kitten -> sitting costs 3 through two substitutions and one insertion.

Fill rows from small to large i and j, since left/up/diagonal dependencies are ready. Backtrack through any equal-cost predecessor. A full table uses O((m+1)(n+1)) time and storage including boundary initialization; the alignment has at most m+n columns. Value-only row compression can use O(min(m,n)+1) working cells. Low-space reconstruction needs additional reasoning, not just two rows.

Resource check. Lengths 100,000 by 100,000 imply ten billion interior cells. Eight bytes per cell alone would be roughly 80 GB, before container overhead or reconstruction, and time still visits those cells. No general feasibility promise follows. A band is exact only under a justified distance threshold or other restriction; silently ignoring paths outside it changes the answer.

Common Confusion / Misconceptions

LCS has a related table but a different objective. With insert/delete-only distance the relation is m+n-2*LCS; allowing unit substitutions changes it. Global alignment consumes both strings completely; local alignment changes boundaries and permits restarting. Affine gap cost needs to remember whether a gap is already open. Adding one transposition transition does not automatically implement unrestricted Damerau-Levenshtein distance; variants have different semantics.

How To Use It

Write the operation contract, derive boundaries from empty strings, and prove the last-column partition. Return an alignment, verify both ungapped strings, and recompute its cost. Compare against exhaustive tiny alignments. Record the table size before large experiments and measure value-only and witness-producing implementations separately.

Check Yourself

Why does a gap count as a real operation? What state distinguishes opening and extending a gap? Why does rolling storage alone not solve quadratic time?

Mini Drill or Application

Compare ab -> ba with unit substitutions versus insert/delete-only edits. Feedback: both distances happen to be 2; a -> b distinguishes them: 1 with substitution, 2 without. A useful test must actually separate the contracts.

Read This Only If Stuck

Skiena: approximate string matching, table construction and path reconstruction. The local chunk's padded-string convention differs from the prefix-length indexing here.