A band as wide as the answer

A route through the distance grid that has reached cell $(i, j)$ has made at least $\lvert i - j \rvert$ insertions or deletions, because those are the only steps that change the difference between the two coordinates and each of them changes it by one.

That single observation is the whole of this essay. If the answer is at most $k$, then no optimal route ever reaches a cell with $\lvert i - j\rvert > k$, so every cell outside a band of width $2k+1$ around the diagonal can be left uncomputed — not estimated, not approximated, left out, with the answer unchanged.

The guarantee is one-sided, and the shape of that matters #

Restricting the table to a band cannot make the answer smaller: every route the band allows was already allowed, so the value it computes is an upper bound on the true distance, always.

It can make the answer larger. If the true optimal route leaves the band, the band’s best route is worse than the true one and the value comes out too high.

So the band’s output has exactly one useful property: if the value is no larger than the band, it is exact. A route achieving that value stayed inside the band, and any route beating it would have had to use more than $k$ indels, which would have cost more than $k$. That is Ukkonen’s condition and it is the certificate.

What it does not say is anything at all about a run whose value exceeds its band. Such a run has proved that the distance is greater than $k$, which is genuine information and is what makes the doubling below work — but the number it reports is an upper bound of unknown quality.

Right, and unable to say so #

Here is what that produces in practice, and it was not anticipated when this field was planned.

Two strings of three hundred characters, thirty edits apart, true distance 25. Sweeping the band from 1 upwards:

The band of three has the right answer. It is exactly 25, it is not close to 25, and it stays 25 for every wider band all the way to the full table. And nothing available to that run can distinguish it from a run that happens to be wrong: the value exceeds the band, the theorem is silent, and the only honest report is “at most 25”.

Certification costs a factor of 8.8 in cells over the run that already had the number.

The observation generalises past this instance and it is worth naming, because this site has met it before under other headings. A method can hold a correct answer and no certificate for it, and the cost of the certificate is a separate quantity. The streaming field found the same shape from the other side: the guarantee that is per query measured a sketch whose bound permitted seven hundred failures and which produced none, so the bound and the behaviour were both correct and about different things.

How little of the table survives #

The fraction that matters is $\frac{2k+1}{m}$, and on the inputs this method is used for it is very small.

A spell-checker comparing a mistyped word against a dictionary entry runs on strings of eight to twelve characters with a threshold of one or two, so the band covers a third of a small table and the saving is modest. The interesting case is long strings that are nearly identical: two versions of a source file, two genomes, two revisions of a document. There $n$ is large, $d$ is small, and the band is a sliver.

Measured on two strings of two hundred characters six edits apart, a band of eight computes 3,290 cells of 39,396 — 8.35%, with 36,106 cells skipped. At a thousand characters and two edits, Ukkonen’s whole run is 8,003 cells against a full table’s 1,003,002, which is 0.8%.

Doubling, and why the wasted rounds are not wasted #

The band is useful only if $k$ is known in advance, and it never is. Ukkonen’s answer is to guess and double.

Start at $k = \lvert n - m\rvert$ — no smaller band can reach the far corner at all, because getting there requires that many indels — and run. If the value is certified, stop. Otherwise double $k$ and run again.

The rounds that fail are the interesting part of the accounting. A round with band $k$ that comes back uncertified has proved the distance exceeds $k$, so the next round is not a guess in the dark. And because the bands double, the final band is under twice the answer, and the total cells summed over every round are under twice the last round’s — a geometric series with the largest term last.

The measured result is that the total is proportional to $n \cdot d$, with $d$ the answer, across a range of $d$:

The right-hand column varies by a factor of 1.31 across a thirteen-fold change in the answer, which is what “proportional to $nd$” looks like when it is measured rather than asserted. The full table on the same strings computes 1,003,002 cells at every one of those points, because it cannot see the answer.

What it costs when the strings are far apart #

The method is output-sensitive, and the honest half of that is what happens when the output is large.

If $d$ is comparable to $n$ — two unrelated strings — then the final band is comparable to $n$, the band covers the whole table, and the doubling has run every earlier round for nothing. At three hundred characters and a distance of 25, Ukkonen’s total is 38,235 cells against a full table’s 90,300: a saving of 58%, which is real and is a constant factor rather than the factor of a hundred available on close strings.

At a distance of $n/2$ there is no saving at all and a small loss. That is the correct behaviour for a method whose whole premise is that the answer is small, and it is why the doubling starts at $\lvert n-m\rvert$ rather than at 1 — on strings of very different lengths the first few rounds would be pure waste.

The method that does not have this failure mode is in the next essay: it computes every cell of the full table and does sixty-four of them at a time, so its cost is $nm/w$ regardless of the answer. Banding and bit-parallelism are the two ways to attack the same product and they attack different factors of it, which is why real implementations use both — bit-parallel within a band.

The order the band forces #

A band is a statement about which cells to compute, and it interacts with the fill order in a way worth making explicit.

Row order works: for each row, run $j$ from $\max(0, i-k)$ to $\min(m, i+k)$. Reads that fall outside the band are not missing cells — they are infinite, because no route goes there — and the implementation has to say so rather than skipping them, or the minimum silently takes whatever the array held.

That is the second time in this field that the difference between absent and zero decides correctness, and it is why the cells outside the band in every figure here are drawn as outlines rather than filled with anything. A picture that shaded them the colour of a low value would be showing the mistake.

The same bound, reached from the other side #

There is a second algorithm with the same $\Theta(nd)$ behaviour that arrives at it from a completely different direction, and it is worth naming because it is the one most people have actually run.

Instead of computing cells and restricting which ones, it tracks for each diagonal the furthest cell along that diagonal reachable with $e$ edits, and increases $e$ until the far corner is reached. The state is one number per diagonal rather than a table, the loop is over edit counts rather than over rows, and the cost is $O(nd)$ for the same reason: at $e$ edits only $2e+1$ diagonals are live.

That is the algorithm behind the diff in most version-control systems, and its parameterisation explains a behaviour anybody who has used one has seen — a diff between two nearly identical files returns instantly, and a diff between two unrelated files of the same size takes noticeably longer. The cost is in the answer, not in the input.

It is named here and not implemented, for the reason this site names rather than implements elsewhere: it would be a second route to a bound already measured, and the measurement above is of a method whose cells this field’s counter can count. A furthest-reaching-diagonal search does not fill a table, so the ninth counter would have nothing to report about it.

Why the lower bound has to be exact #

The band works because $\lvert i - j\rvert$ is a lower bound on the cost of any route through the cell, computable from the cell’s coordinates and nothing else, and because that bound is never optimistic in a way that could exclude the true optimum.

Both halves matter and the second is the one that fails in practice. A pruning rule built on a bound that is sometimes too large discards routes that were cheaper than it claimed, and the result is not an approximation with a stated error — it is an answer that is wrong in a way nothing reports. A rule built on a bound that is merely weak, never optimistic, prunes less and stays exact.

That is the difference between this band and the heuristics that look like it. A search that cuts on “this partial alignment is already worse than the best complete one found so far” is also exact, for the same reason. A search that cuts on “this partial alignment looks unpromising” is not, and the two are one line apart in an implementation.

The general form worth carrying: a pruning rule is exact exactly when the quantity it cuts on is a lower bound that provably cannot be beaten from where it is applied. Everything else is a heuristic, and a heuristic in place of a bound turns a computation into an estimate without changing the shape of the code.

Two rounds always suffice #

The doubling schedule treats a failed round as having produced nothing but a refutation. It produces more than that, and using it turns an unbounded number of rounds into exactly two.

A round with band $k$ returns a value $v$ that is an upper bound on the true distance, always — that is the one-sided guarantee the essay opens with. So run the next round at band $v$ rather than at $2k$. The true optimal route uses at most $d \le v$ indels, so it lies inside a band of $v$; the round therefore returns $d$ exactly; and $d \le v$ means the value does not exceed the band, so the certificate is automatic. Two rounds, whatever the strings.

On the pair the table measures, starting from a band of three: round one costs 2,091 cells and returns 25, round two runs at a band of 25 and costs about 15,300, and the total is 17,391 with a certificate. The doubling schedule reaches its certificate at 38,235, and the single band-32 run that certifies costs 18,476. The two-round schedule is cheaper than either.

The catch is in the first round’s quality and it is worth stating plainly, because it is why doubling is the schedule everybody actually uses. The second round’s cost is set by $v$, not by $d$, and a bad first round makes $v$ enormous — the band of one on this pair returns 87, and a second round at 87 would compute 52,500 cells to certify an answer of 25. The schedule is only as good as the upper bound it starts from, and doubling is the schedule that refuses to trust any upper bound at all.

Which points at the sensible hybrid rather than at a winner. Start at $\lvert n - m \rvert$ as before; each round, take the next band as the smaller of twice the current band and the value just returned. That never runs a band larger than doubling would and takes the shortcut whenever the reported value is informative, which on close strings is immediately. Nothing about it needs a new theorem — both halves are the guarantee already stated, read in the two directions it can be read in.

The band assumes what an indel costs #

Every route argument here counts indels: a step off the diagonal is one insertion or deletion, so a cell at distance $\lvert i-j\rvert$ from the diagonal has cost at least $\lvert i-j\rvert$. That inequality is where the band comes from, and it is a statement about the cost model rather than about the grid.

Change the model and the arithmetic changes with it. With an indel costing $g$ and a substitution $s$, a cell $\lvert i-j\rvert$ off the diagonal has cost at least $g\,\lvert i-j\rvert$, so a threshold of $k$ admits a band of width $k/g$ — narrower for an expensive gap, wider for a cheap one. That is still a clean bound and the method survives intact, with $k$ read in cost units rather than in edits.

Affine gaps break it, and the way they break it is worth seeing. Under a gap charged to open and then per character, a run of $L$ indels costs $o + L e$ rather than $Lg$, so the cost of straying $L$ from the diagonal grows with slope $e$ — and $e$ is deliberately small, because the whole point of an affine model is that a long gap should not be charged as many separate events.

So the band that a threshold $k$ admits is $(k - o)/e$ wide, and with a typical opening of eight and an extension of one, a threshold of twenty admits a band of twelve where a unit-cost model would have admitted twenty. That direction is fine. The trouble is that a realistic affine model has $e$ well under one relative to a substitution, and then the admissible band is several times wider than the answer — which is exactly the regime where a sliver becomes a stripe and the saving evaporates.

The band is therefore not a general-purpose optimisation but a consequence of one particular cost model’s geometry, and a table built under a model that makes long gaps cheap has given up most of it. That is not a small caveat given who uses these tables: sequence aligners use affine gaps precisely because biological insertions are single events, and they recover their savings from filtering and from bit-parallelism rather than from banding.

What is being traded #

The band trades a guarantee for work, and the trade has three positions rather than two.

Full table. $nm$ cells, exact, no assumption.

Band with a known bound. $n(2k+1)$ cells, exact whenever the bound holds, and a report of “greater than $k$” when it does not. This is the position a spell-checker is in: it does not want the distance between a typo and every dictionary word, it wants the words within two, and a run that reports “more than two” has answered the question that was asked.

Band with a guessed bound, doubled. $\Theta(nd)$ cells, exact always, at a constant factor over the previous line. This is the position a program is in when it must produce the number.

The middle line is the one usually left out of the description, and it is the one that matters most in practice — because most uses of edit distance are threshold queries wearing the clothes of a distance computation, and a threshold query does not need the distance at all.

One last thing about the band is worth keeping, because it is the transferable part. The band is a pruning rule derived from a bound, and it works because a lower bound on the cost of any route through a cell is available in closed form — $\lvert i - j\rvert$, computable from the cell’s coordinates alone, needing no lookahead and no search. That is what makes it exact rather than heuristic, and it is the same structure branch-and-bound uses everywhere: a cheap bound that provably cannot be beaten, applied to a region rather than to a point. Where such a bound exists the pruning is free; where it does not, no amount of cleverness about the order of evaluation recovers it.