The cells that were never worth having

Every rung of this ladder so far has taken the subproblem set as given. The recurrence names its arguments, the arguments enumerate the cells, and the questions have been about what a cell costs and what order to fill them in.

The recurrence does not name its arguments. Somebody chose them, the obvious choice was pairs of prefixes, and the obvious choice is not the only one.

The choice is invisible because it is made at the moment the recurrence is written, in the act of deciding what the subscripts mean. The longest common subsequence of these two prefixes is a perfectly good subproblem and there is nothing wrong with it. It is simply not the only quantity whose values can be assembled into the answer, and the alternative on this page turns out to have a cost in a completely different variable — one that has nothing to do with how long the strings are.

What a non-matching cell does #

The longest-common-subsequence recurrence has two branches:

$$L(i,j) = \begin{cases} L(i-1,j-1) + 1 & a_i = b_j \\ \max\big(L(i-1,j),\ L(i,j-1)\big) & \text{otherwise} \end{cases}$$

The first branch produces a new value. The second propagates one. So of the $(n+1)(m+1)$ cells, exactly the ones on the first branch are doing work, and the rest are carrying answers from where they were computed to where they will be read.

How many are on the first branch is a question about the alphabet, not about the strings’ length. Over $\sigma$ symbols drawn uniformly, a pair of positions agrees with probability $1/\sigma$, so the expected number of matching pairs is $nm/\sigma$. On English text that is a twenty-sixth of the rectangle; on a nucleotide sequence a quarter; on a bit string a half.

That number has a name in the literature — $r$, the number of matches — and the method built on it is due to Hunt and Szymanski. It enumerates the $r$ matching pairs, in an order that lets each one be placed by a binary search over the answers found so far, for a total of $O((r + n)\log n)$.

It is worth pausing on how unusual that is as a cost. Every complexity claim on this site so far is in the size of the input: $n$ elements, $n$ and $m$ characters, $V$ vertices and $E$ edges. Here the cost is in $r$, which is a property of the input’s contents — two strings of the same length over the same alphabet can have wildly different $r$, and two strings that happen to share no characters at all have $r = 0$ and cost nothing. A bound in $r$ is an output-sensitive bound in the loose sense: it charges for how much structure the input has rather than for how much of it there is.

The measurement, and the losing case #

The two methods are run on the same pairs of strings at three alphabet sizes and required to agree on the answer.

Read the middle two columns and the method looks like a straightforward improvement that gets better as the alphabet grows. Read the third and fourth together and it is not: over two letters the sparse method does three times as much work as the grid it replaces, and over four letters it still does 1.6 times as much. It wins at twenty-six by a factor of 4.7.

The reason is the logarithm. Each match costs a binary search over the current set of best endpoints, which is $\log$ of the subsequence length so far — around fifteen comparisons here — where a grid cell costs a constant. So the sparse method’s real cost is $r \log n$ against the grid’s $nm$, and it wins when $r < nm/\log n$, which is when $\sigma > \log n$. At three hundred characters that threshold is about eight symbols, and the crossing on the plate is between four and eight.

A method whose losing case is as easy to state as its winning one is worth more than one whose is not, and this one’s losing case is not a corner: DNA is four letters and a bit string is two. Two of the three most common substrates for a longest common subsequence are exactly where this method should not be used, and the third — comparing lines of source files, where the alphabet is effectively the set of distinct lines and $\sigma$ is in the thousands — is where it is overwhelmingly the right choice and is what real file-comparison tools do.

There is a second reading of the two-letter row that is worth having, because it says something about where the method’s cost actually goes. Over two letters the strings share 240 characters of a 300-character sequence — the subsequence is four-fifths of the input — so the binary search is searching a long array, its cost per match is at its highest, and there are more matches than anywhere else. The three factors all move the wrong way together, which is why the losing case loses by three times rather than by a little. The method is worst exactly where the two strings are most alike, which is the opposite of the band’s behaviour and is worth knowing before choosing between them.

Where the crossing is, and why it is not where the ratio is #

The plate crosses between four symbols and eight, and the arithmetic that puts it there is worth doing rather than quoting, because the answer is not the ratio of the two column counts.

The grid costs about $nm$ cell fills. The sparse method costs about $r \log \ell$ where $\ell$ is the length of the answer, and $r \approx nm/\sigma$. Setting them equal gives $\sigma = \log \ell$ — the crossing is at an alphabet size equal to the logarithm of the subsequence length, and it therefore moves with $n$ rather than staying put. At three hundred characters $\log_2 \ell$ is between six and eight; at three million it would be around twenty, so a method that wins comfortably on English text at page length would be marginal on English text at book length.

That is an unusual shape for a crossover and it is the sort of thing this collection exists to notice. The two methods are not a constant factor apart with a fixed break-even; the break-even is a slowly growing function of the input size, so which method is right can change as a system’s data grows without anything about the data’s character changing. A limit is not a prediction is the standing caution, and here the specific form of it is that a benchmark taken at one size does not settle the choice at another.

Why the enumeration needs an order, and what the order buys #

Enumerating the matches is not enough on its own; they have to be processed in an order that makes each one’s answer available when it is needed.

The method walks the first string left to right, and for each character visits that character’s positions in the second string in decreasing order. The decreasing order is the whole trick: it prevents a single character of the first string from chaining with itself, which is what would happen if two of its matches in the same row were used one after the other.

Given that order, each match extends a subsequence, and which one it extends is found by a binary search over an array holding, for each achievable length, the smallest column at which a subsequence of that length can end. That array is non-decreasing, so a binary search is available, and the array’s final length is the answer.

The structure that array has is worth noticing because it is not the table’s structure at all. The grid stores an answer per subproblem and the sparse method stores a subproblem per answer — one entry per achievable length, holding where that length is cheapest to reach. It is the same inversion a bucket-by-value method makes against a comparison sort, and it is the reason the two costs are in different variables.

What “the subproblem set is a choice” means, taken generally #

Three subproblem sets for one problem have now appeared in this field, and they are worth setting beside each other because the pattern is more useful than any of them.

Pairs of prefixes — the grid. $nm$ subproblems, constant cost each, no precondition. The default, and the one that is right when nothing is known.

Pairs of prefixes near the diagonal — the band. $nk$ subproblems for an answer of size $k$, and it needs a bound on the answer to be safe, which is why a band as wide as the answer is careful about the difference between finding the right answer and certifying it.

Matching pairs — this page. $r$ subproblems, a logarithm each, and it needs the recurrence to have a branch that does nothing.

None of these is a different algorithm in any deep sense. All three fill the same relation with the same rule; they differ in which arguments they consider it worth evaluating at. And each one’s cost is in a different variable — $nm$, $nk$, $r\log n$ — none of which can be compared to the others without knowing something about the input.

This is the cost is the number of subproblems read as an instruction rather than as an observation. That essay’s slogan says where a dynamic program’s cost comes from. Turned around, it says where to look for an improvement: not at the loops, at the argument list.

It is also the place where this field’s slogan and the previous two rungs’ findings fit together into one sentence. A dynamic program’s cost is the number of subproblems, times the transitions per subproblem, arranged in an order that decides its space and its depth — four quantities, four places an improvement can attack, and only the first two appear in a complexity class. This rung attacks the first, the argmin that cannot go backwards attacks the second, and the order that has a depth is about the last two. Nothing in the phrase fill a table of subproblems distinguishes them.

What the sparse method gives up #

Two things, and one of them is the reason the grid is still what most implementations ship.

It computes a length, and recovering the subsequence is extra. The array of best endpoints holds where each length can end, not how it got there, so a traceback needs a parent pointer per match — which is $O(r)$ space rather than $O(n)$, and on a small alphabet that is worse than the table. That is the same shape as the table nobody has to keep: a compact representation that keeps the number and loses the witness, with the witness recoverable at a price.

And it does not generalise to edit distance. The branch that made the argument work is the LCS recurrence’s max branch, which propagates without changing anything. The edit-distance recurrence has no such branch — every cell is a minimum over three genuine candidates and a mismatch costs one rather than nothing — so every cell is doing work and there are no cells to leave out. The techniques are not interchangeable, and the reason is a property of the recurrence rather than of the problem.

The second point is worth dwelling on, because the two problems are usually taught as the same problem with a different scoring rule. In the accounting this field keeps they are not the same at all: one has a subproblem set with structure to exploit and the other does not.

A method that is right about the problem people have #

There is a practical postscript that changes how the losing case should be read, and it is the reason this method is in every file-comparison tool despite the table above.

A file comparison is a longest common subsequence over lines, not over characters. The alphabet is the set of distinct lines in the two files, and in any real pair of source files nearly every line is distinct — so $\sigma$ is in the thousands, the matches are sparse to the point of being scarce, and $r$ is close to the number of lines that actually appear in both. On two thousand-line files sharing nine hundred lines, the grid is a million cells and the matches are a few thousand.

That is a factor of several hundred, on the single most common industrial use of this recurrence, and it is available because somebody noticed that the subproblem set was negotiable. The two-letter case where the method loses by three times is real and it is not the case anybody is in.

The general lesson is not use the sparse method; it is that the alphabet is a parameter of this problem and no statement of it mentions one. A bound of $O(nm)$ is true at every alphabet size, it is tight at two symbols, and it overstates the work by two orders of magnitude at the alphabet a diff tool actually sees. What O notation does not say is the standing form of that complaint; this is the instance where the missing parameter is worth the most.

What the counter does not see here #

The binary search’s comparisons are charged as transitions and the grid’s are not. A grid cell performs one character comparison and one or two arithmetic comparisons; a match performs about fifteen comparisons inside a binary search. The counter charges both as transitions, so the plate’s crossing is at the right place only if those units are comparable, and they are approximately rather than exactly. One run, four counts, four answers is the general form of that caution.

The alphabet is assumed uniform. Every $r$ on the plate is measured on strings whose characters are drawn independently and evenly, and real text is neither: English letters follow a steep frequency distribution, so the matches concentrate on the common letters and $r$ is larger than $nm/\sigma$ would predict. The direction is against the method, the size of the effect is a sum of squared letter frequencies rather than $1/\sigma$, and none of it is measured here. It is the same failure a corpus that was not generated is about, in a different field: a generated input has the statistics it was given and real input does not.

The enumeration’s own cost is folded in. Building the map from each character to its positions is one pass over the second string and is charged; walking it is charged per match. What is not charged is that the walk is a pointer chase through per-character lists, where the grid’s fill is a sweep over contiguous memory — so the sparse method’s locality is much worse than its transition count suggests, in exactly the way where an algorithm looks measures for traversals.

Where this ladder goes from here: the table that is a choice about the whole problem #

Three rungs have now attacked the same cost in three places: the transitions inside a cell, the order the cells are filled in, and which cells exist. What none of them has questioned is that the answer wanted is the one the recurrence computes.

That is the next thing worth taking, and there is a concrete case for it in this field already. An edit distance is a single number summarising two strings, and almost nothing that asks for one wants the number — a spell checker wants the candidates below a threshold, a file comparison wants the edit script, a search wants the positions. Each of those is a different question, each has its own subproblem set, and asking the general question and then discarding most of the answer is a fourth kind of waste that none of the three rungs above measures.

The measurable version is specific: for each of those uses, how much of the table computed is read? The band already answers it for the case of a known threshold. The interesting case is the threshold that is not known in advance but is discovered as the computation proceeds — the way a nearest-neighbour search tightens its radius as it finds candidates — and whether the number of cells that turn out to be needed is closer to $nk$ or to $nm$ is a measurement nobody on this ladder has taken.