A distance that is a path through a grid

Two strings are near each other if one can be turned into the other with few changes. Three kinds of change are allowed — substitute a character, delete one, insert one — and the distance is the smallest number of them that does the job.

That definition is a minimum over an infinite set: there are arbitrarily long sequences of edits taking one string to another, and most of them are wasteful. Turning it into something computable means finding a structure the minimum can be taken over, and the structure is a grid.

The grid is a graph, and the recurrence is a relaxation #

Put a node at every pair $(i, j)$ of prefix lengths. Draw three arcs into it: from $(i-1, j)$ at cost 1, meaning a character of the first string was deleted; from $(i, j-1)$ at cost 1, meaning one of the second was inserted; and from $(i-1, j-1)$ at cost 0 if the two characters agree and 1 if they do not.

Then the edit distance is the length of the shortest path from $(0, 0)$ to $(n, m)$ in that graph, and it is a shortest path in exactly the sense this site’s graph field means: counting on a graph built the machinery, and every arc here has non-negative weight, so Dijkstra’s algorithm would compute this correctly.

Nobody uses Dijkstra for it, and the reason is worth stating because it is the general reason dynamic programming exists. The graph is acyclic and a topological order of it is known in advance — any of the three fill orders from the same table, filled two ways — so the priority queue that Dijkstra spends its time maintaining has nothing to decide. Relaxing the arcs in topological order gets the same answers with no queue at all. A dynamic program is a shortest-path computation on a graph whose topological order was free.

That framing pays for itself immediately in two places. It explains why the answer is at a corner rather than distributed through the table: the corner is the sink. And it explains what the outlined route in every figure here is — a shortest path, and one of possibly many, since a graph can have several.

What one cell costs, in the unit this field already had #

The strings field on this site counts character comparisons, because the comparison that is not one comparison established that a comparison of two strings is not one act. The same counter applies here and gives a number that is exact and slightly surprising.

A distance table makes one character comparison per interior cell, and no more: the cell asks whether $a_i$ and $b_j$ agree, and everything else it does is arithmetic. So the character-comparison count is exactly $nm$.

Set that against what it costs to find a string rather than measure how far it is from one. On a text of four thousand characters and a pattern of twenty-four, this site’s Knuth–Morris–Pratt reads 4,988 characters and reports every occurrence. The distance table over the same pair reads 96,000.

The factor is 19.2, and it is not a constant: it is $m$, the length of the shorter string, up to the constant KMP’s own bound carries. Exact matching is linear in the text and approximate matching is the product of the two lengths, and every algorithm in the next three essays is an attempt to get part of that factor back.

It is a metric, and one of the four conditions is doing work #

Edit distance satisfies the four conditions that make a distance a metric: it is non-negative, it is zero exactly when the strings are equal, it is symmetric, and it obeys the triangle inequality.

Three of those are immediate. The fourth is not, and it is asserted here over two dozen random triples rather than quoted: turning $a$ into $c$ cannot cost more than turning $a$ into $b$ and then $b$ into $c$, because the concatenation of the two edit scripts is itself an edit script from $a$ to $c$. Measured over two dozen triples the tightest case has a slack of exactly one edit, which is the interesting part — the triangle is nearly an equality on some triples, so a program using it to prune a search of a string database will prune very little on the pairs where pruning would help most.

Symmetry is the condition worth being careful about, because it is a property of the prices rather than of the idea. Insert and delete are each other’s inverses, so pricing them equally makes the distance symmetric; pricing an insertion at 1 and a deletion at 3 is a perfectly reasonable model — it is what a spell-checker built around a particular kind of typing error would use — and under it $d(a, b) \ne d(b, a)$. A program that halves its work by computing only one direction is relying on the prices, and nothing in the recurrence tells it so.

How many shortest paths there are, which is usually not one #

Every figure in this field outlines a route and the outline is a choice. Ties in the table are broken towards the diagonal, and where there are ties there are other routes of exactly the same cost.

That is not a caveat, it is a countable quantity: the number of shortest paths in a directed acyclic graph is itself a dynamic program over the same graph, filled in the same order, adding where the shortest-path computation took a minimum. Run it beside the distance table and the answer comes out exactly.

The canonical example is unique, which is presumably why it became the canonical example — the picture everybody draws of it is the whole truth. Two random strings of sixty characters have six hundred and fifty thousand equally good alignments, and a program reporting one of them is reporting an arbitrary member of a large set. Which member depends on the order of the arguments to a min, and nothing about the problem prefers any of them.

This matters wherever the alignment is the deliverable rather than the number. A file-comparison tool showing “these lines changed” is showing one optimal edit script out of many, and two implementations that disagree about which lines changed can both be right. The distance is well defined; the witness is not.

The price of a substitution is a parameter, and moving it changes the problem #

Nothing about the definition forces a substitution to cost one. It costs one because it is one operation, which is a reasonable convention and is not the only one.

Price it at two, and no optimal alignment ever substitutes: a substitution can always be replaced by a deletion and an insertion for the same total, so the operation might as well not exist. What remains is a distance built from insertions and deletions alone, and that quantity has another name — it counts exactly the characters that are not part of the longest common subsequence.

The identity is exact: $d_2(a, b) = n + m - 2\lvert\mathrm{LCS}(a,b)\rvert$, and this site’s gate checks it on a dozen random pairs rather than on the example that makes it look plausible.

The identity is the sort of claim that is easy to believe and easy to leave unchecked, so the third table is the check rather than an illustration of it. It asks the same pair a different question — not how many edits but how long is the longest subsequence they share — and fills a table with a different recurrence in it to get there.

Three operations, and the fourth that is often wanted #

The three edits are a modelling choice too, and the most common extension is the transposition: swapping two adjacent characters, which is one keystroke error and costs two edits under the definition above.

Adding it changes the recurrence — a fourth predecessor, at $(i-2, j-2)$, available when the two characters cross — and changes nothing about the size or shape of the table. That is worth noticing because it is the general pattern: the table’s dimensions come from the state, which is a pair of prefix lengths, and the operations come from the transitions, which are the arrows into a cell. Adding an operation costs one more transition per cell and no more cells at all, so it moves evals and leaves cells exactly where it was.

The cost model can move much further without disturbing either. A substitution matrix prices each pair of symbols separately; an affine gap penalty charges more to open a gap than to extend one, which needs three tables rather than one because a cell has to know whether it is inside a gap. Both are used in practice — the substitution matrix comes from how often each substitution is actually observed, which makes it a measurement rather than a convention — both are still $\Theta(nm)$ cells, and neither is implemented here. This field takes unit costs and says so on every plate, which is the same discipline the coding field applies to its models, and a bound of $\Theta(nm)$ survives every one of these changes while saying nothing about any of them.

The boundary conditions are the problem statement #

One more thing follows from the shortest-path framing and it is the hinge the whole field turns on.

The recurrence for an interior cell is the same in every variant of this problem. What differs is the boundary: the values along the top row and the left column, which say what it costs to align a prefix against nothing.

Set the top row to $j$ and the left column to $i$ and the result is the global distance — every character of both strings must be accounted for. Set the top row to zero instead and the result is approximate search: an alignment may start anywhere in the text for free, so the last row holds, for each position, the distance to the best match ending there. Set both to zero and the result is local alignment, the form used to find a shared region inside two otherwise unrelated sequences.

Three problems, three sets of boundary values, one interior recurrence and one table of identical size. That is worth stating plainly because it means the cost model developed here transfers to all three without modification, and because it is the cheapest possible demonstration that a table’s content is decided somewhere other than in the loop that fills it.

What the distance is not #

Two properties get assumed and neither holds.

It is not normalised. Two ten-character strings at distance five share almost nothing; two thousand-character strings at distance five are nearly identical. The number alone is uninterpretable without the lengths, which is why every plate in this field prints them.

It is not a search. The distance between a short pattern and a long text is dominated by the difference in their lengths — measured above, a twenty-four character pattern against a four-thousand character text comes out at 3,976, which is 4,000 minus the 24 characters that matched. That number is correct and useless. Asking whether a pattern occurs approximately somewhere in a text is a different problem, solved by the same table with the top row initialised to zero instead of to $j$, and it is not taken here — this field measures the distance between two strings, and approximate search over a text is named as the neighbour and left.

The band is a heuristic search, and the heuristic is stronger than the band #

The shortest-path framing pays for itself once more, and this time it produces something the string literature states as a special trick.

A shortest-path search can be guided by an admissible heuristic: a lower bound $h(v)$ on the cost from $v$ to the sink. Any node whose $g(v) + h(v)$ exceeds the best known total cannot be on an optimal route and need not be expanded. That is A*, and it needs a heuristic that never over-estimates.

Here one is available in closed form. From cell $(i,j)$ the remaining strings have lengths $n-i$ and $m-j$, and any alignment of two strings of different lengths must perform at least their difference in indels. So

$$h(i,j) = \bigl\lvert (n-i) - (m-j) \bigr\rvert$$

is admissible, computable from the coordinates alone, and needs no lookahead whatever.

Now compare it with the band. The band cuts on $g$ alone: a cell at $|i-j| = t$ has already spent at least $t$, so if the answer is at most $k$ then $t \le k$. Adding the heuristic cuts on both ends at once — on strings of equal length, $h(i,j)$ is also $t$, so a cell on an optimal route satisfies

$$t + t \le k \qquad\Longrightarrow\qquad t \le k/2$$

Half the band, from the same argument applied to the other end of the path. The cells the band computes and the heuristic excludes are the ones that could reach the current position cheaply and could not get to the corner from there, and there are as many of them as there are of the ones the band already excluded.

That is worth having for two reasons beyond the factor of two. It says the band is not a string-matching trick but an instance of a general graph technique, so anything known about admissible heuristics applies — including that a better heuristic prunes more, and that a heuristic which over-estimates prunes faster and returns the wrong answer, which is the exact distinction between an exact band and a plausible one.

And it explains why the escape exists at all. The band works because a cheap, closed-form, provably-admissible lower bound is available from the coordinates. Where no such bound exists, no amount of care about evaluation order recovers anything — which is the general form of the rule, and it is a statement about the graph rather than about the strings.

Which of the six hundred and fifty thousand to report #

The alignment count table ends with a number large enough to make the question unavoidable: when a program reports an edit script, which of the many optimal ones should it report?

The answer is not “any of them”, because the consumer is usually a person. A file-comparison tool showing that ten scattered lines changed and one showing that a single block moved are describing the same edit distance, and one of them is readable. Real diff tools therefore apply a second criterion after the first — prefer alignments with fewer, longer runs; prefer boundaries at blank lines or at indentation changes — and those are heuristics about presentation rather than about distance.

That places the tie-break where it belongs. The distance is a well-defined minimum and the alignment is a choice made under a second objective the recurrence knows nothing about, which is why two correct implementations can disagree and why “why did it show me that diff” is a question with an answer that is not about edit distance at all.

The cheapest honest thing an implementation can do is what this field’s plates do: print how many optimal alignments there were beside the one being shown. One means the picture is the whole truth; six hundred and fifty thousand means it is a convention.

Where this goes #

Everything after this essay is an attack on the $nm$.

The table is quadratic in the lengths and the answer is often small. When two strings are close, almost every cell is far from the route and could not have been on it — that is a band as wide as the answer, and it computes eight cells in a hundred. When the answer is not small the cells still have to be computed, but not one at a time: a column computed in machine words does sixty-four of them per operation. And when the alignment is wanted rather than the number, the space can come back down to a line at the cost of computing the table twice, which is the alignment that fits in one line.

None of the three changes the class, and that is the point worth carrying. $\Theta(nm)$ is correct for all of them and is the least informative true statement available about any of them.

There is one more thing this framing hands over for free, and it is the reason the field’s later essays can be written at all. Because the table is a shortest-path computation on a graph with a known topological order, anything true of shortest paths is available here without re-deriving it: the number of shortest paths, counted above; the fact that a prefix of a shortest path is a shortest path, which is what makes the traceback work; and the fact that a lower bound on any path from a node to the sink is a lower bound on the whole route through it, which is what lets a band be cut without losing the answer. Every one of those is used in the next three essays, and every one of them is a statement about graphs rather than about strings.