The row that starts at zero

A pattern of eight characters is compared against a text of a hundred and fifty-six. The table has 1,413 cells. Filled one way it answers 148; filled the other way it answers 0.

Nothing about the recurrence changed. Nothing about the order the cells were computed in changed. The cell count is identical to the cell. What changed is one line — what the top row was initialised to — and with it, which question the rectangle was asked.

The upper number is not wrong. It is the honest edit distance between the pattern and the whole text: turning one into the other means deleting about a hundred and fifty characters, and the table says so. It is simply not an answer to the question anybody asks of a text, which is whether the pattern is in there and where.

What the initialisation means #

The distance table is a statement about prefixes. Cell $(i, j)$ holds the cheapest way to turn the first $i$ characters of one string into the first $j$ characters of the other, and the boundary rows say what it costs to start:

$$D(i, 0) = i \qquad D(0, j) = j$$

Read those two aloud and they are claims. The first says that aligning $i$ characters of the pattern against nothing costs $i$ deletions, which is true and stays true. The second says that aligning nothing against $j$ characters of the text costs $j$ insertions — and that is the assumption the whole difficulty comes from. It insists that the text be consumed from its first character. A match beginning at position ninety is charged ninety insertions before it starts.

Set the top row to zero instead:

$$D(i, 0) = i \qquad D(0, j) = 0$$

Now a prefix of the text is free. The pattern may begin matching anywhere, and the cell that used to hold the cost of consuming the first $j$ characters now holds nothing to pay for skipping them.

For contrast, the same recurrence with the ordinary boundary:

Two boundary conditions, one recurrence, and the second is not a variation on the first. It is a different problem with a different answer read from a different place.

Only the top row, and only the top #

The left column is not zeroed and the asymmetry is the definition of the problem.

$D(i, 0) = i$ says that consuming $i$ characters of the pattern against nothing costs $i$ deletions, and it has to stay, because a search asks about the whole pattern. Free the left column as well and the table would happily report that the pattern occurs everywhere at no cost, by matching none of it.

There is a third setting, and it is worth naming so that it is not confused with this one. Free both boundaries and floor every cell at zero, and the answer becomes the best-matching pair of substrings — the cheapest region of the text against the cheapest region of the pattern. That is a genuinely different question again: it asks whether the two strings share anything, rather than whether one occurs in the other, and it needs the numbers read as a similarity climbing from zero rather than a cost accumulating from it. Three questions, one rectangle, and the differences between them are four lines of boundary and one comparison operator.

Which is the reason to state the initialisation on the plate rather than in the surrounding paragraph. Two tables filled by the same recurrence, at the same cost, in the same order, holding numbers that are not the same quantity, is precisely the situation in which a caption saying distance 148 and a caption saying distance 0 are both correct and the pair of them is misleading.

The last row is the text, scored #

Once the top row is zero, cell $(m, j)$ — bottom row, column $j$ — holds a quantity worth naming carefully: the cost of the best alignment of the whole pattern that ends at position $j$ of the text.

So the last row is not one number. It is the text scored, character by character, for how nearly the pattern occurs ending there.

The text in that figure was written to contain the word measured twice — once spelled correctly and once as measurod. The row finds both: cost 0 at position 150 and cost 1 at position 29. Nothing was told where to look.

That is the practical content of the change. A global distance is a scalar and a search is a function over positions, and the second is what the same rectangle was holding all along.

What the threshold does, and what it does not #

A search of this kind is usually stated with a tolerance: find every place the pattern occurs within $k$ errors. It is tempting to read $k$ as a parameter of the algorithm. It is not. It is a parameter of the report.

The rows widen in a particular way and it is worth reading. At $k = 1$ the answer is 29, 149, 150, 151 — three of those four are the same occurrence reported at three adjacent end positions, because an alignment allowed one error may stop one character early or one character late. Approximate matching produces clusters rather than points, and any implementation that reports occurrences has to decide what to do about that. Taking the local minimum of each run is the usual choice; it is a choice, and it is not part of the table.

There is a second reason the clusters matter, and it is about counting rather than about tidiness. A published figure of the form this method found 340 approximate occurrences is a count of whatever the method decided to report, and the two natural policies — every position under the threshold, and one per run — differ here by a factor of three at $k = 2$ and by more as the threshold rises. Nine positions become three occurrences. Neither number is wrong and the two are not comparable, which is the same trap a bound quoted against the wrong quantity sets one field over.

By $k = 5$ the report has twenty-eight positions and includes places like 16, 46 and 122 that have nothing to do with the word. The threshold has passed the point where the answer is about the pattern at all.

Ends, not starts #

The last row knows where a match ends. It does not know where one begins, and this is a distinction that almost every informal statement of the problem elides.

The reason is structural rather than incidental. The value in cell $(m, j)$ was assembled from cells above and to the left; finding the starting column means walking backwards through the table along the path that produced it, exactly as an alignment is recovered. That is a second pass, it needs the table to still be there, and it costs a further $O(m + j)$ per reported occurrence.

There is a small consolation and it is worth having. The end position is enough to bound the start: an alignment costing $c$ that ends at $j$ began no earlier than $j - m - c$ and no later than $j - m + c$, because each of the $c$ errors can move the start by at most one. So a report of ends here, at cost 2 is a report of a window of five starting positions, which for many purposes is the answer. Turning the window into a point is what costs the second pass.

So an approximate matcher has two prices and the literature quotes one:

• finding the end positions: the table, once;
• locating the starts: a traceback per occurrence, which needs the whole table retained.

The second is the reason the rolling-frontier trick — keeping two rows instead of the whole rectangle — is not free here. It answers how many and where do they end in $\Theta(m)$ space and cannot answer where do they start at all, because it has thrown away everything it would need to walk back through. The same split appears again, in a much sharper form, when an index is asked to count and to locate.

What it costs, against what exact search costs #

The cell count is the product of the two lengths and does not move. That is not a small thing.

Exact matching does not sit on that curve. KMP reads the text in a number of character comparisons bounded by twice its length; Horspool reads a fraction of it.

Put beside each other: allowing a single error takes the cost of searching a text from something proportional to its length to something proportional to its length times the pattern’s. On twenty thousand characters and a pattern of eight that is a factor of eight, which sounds survivable; on a genome and a pattern of thirty it is not, and it is why every practical approximate matcher is a filter followed by a table rather than a table.

The band does not transfer #

Ukkonen’s band is the obvious thing to reach for. If the answer is at most $k$, then no optimal path strays more than $k$ cells from the diagonal, so the cells outside a band of width $2k+1$ need not be computed at all — and on the distance problem that is an enormous saving, exact whenever the value returned is no larger than the band.

It does not carry over unchanged, and the reason is the boundary condition again. A distance table has one diagonal, running from the corner it starts at to the corner it ends at. A search table has no such thing: a match may begin at any column of the free top row, so there are as many diagonals as there are starting positions, and the union of the bands around all of them is the whole rectangle.

There are real methods that recover a saving here — cutting off columns of the last row once every cell in them exceeds the threshold is the standard one, and it is genuinely effective on long texts with few matches. It is a cutoff rather than a band, its saving depends on the data rather than on the answer, and it earns nothing in the worst case. Saying which of those two shapes a method has is the difference between a bound and a hope.

The same table, on a text that nearly matches #

The zeroed top row is worth seeing once more where the answer is not zero, because the last row’s shape is the whole product and a perfect match flattens it.

At zero errors it is an exact matcher #

The last check is the one that makes the whole construction believable. Set $k = 0$ and the table must report exactly the exact occurrences, no more and no fewer.

On abracadabra abracadabra searched for abra, the row reports end positions 4, 11, 16 and 23 — four occurrences, at exactly the four places a scan finds them. That is asserted rather than observed: the same text and pattern go through a plain scan and the two answers are required to agree character for character.

That is the sense in which this is one problem with a dial rather than two problems. It is also the sense in which the dial is expensive: the exact case, which a linear scan settles, costs the full rectangle here.

The cutoff, and what shape of saving it is #

The band does not transfer and the cutoff does, and it is worth stating precisely because the two are so often described in the same breath and they are not the same kind of thing.

Fill the table column by column and keep track of one integer: the largest row index whose cell in the current column is at most $k$. Call it the last active row. Every cell below it in that column is already above the threshold, and because a cell is never smaller than the one above it minus one, everything below can only get worse as the column descends. So those cells cannot participate in any reported occurrence and need not be computed. Carry the index to the next column with a small update — it can rise by at most one per column — and the work per column is the depth of the active region rather than the full pattern length.

On text where the pattern does not nearly occur, the active region collapses to a few rows, and the total work becomes proportional to $kn$ rather than $mn$. For a pattern of thirty characters at three errors that is a factor of ten, and the factor grows with the pattern length, which is the direction that matters — long patterns are exactly where the rectangle hurts.

What kind of claim that is, though, is the point. It is not a bound. A text engineered so that the pattern nearly occurs everywhere keeps the active region at full depth and the method computes every cell, so the worst case is unchanged at $mn$. The saving is expected-case, it is a property of the text rather than of the answer, and the honest way to report it is with the text named.

Set that beside the band, which is the other shape. Ukkonen’s band computes $O(kn)$ cells and the saving is guaranteed whenever the returned distance is under $k$ — it depends on the answer, not on the data, and there is no input that defeats it. Two methods, both proportional to $k$ rather than $m$, and one of them holds on every input while the other holds on the inputs anybody has.

This collection has drawn that distinction before under a different heading, and it is worth naming as a general question to ask of any pruning: is the saving a function of the answer or a function of the data? The first survives an adversary and can be quoted as a bound. The second is a measurement, is usually much larger in practice, and turns into nothing precisely when somebody is trying to make it.

The table is online in the text and an index is online in the pattern #

There is a duality in the last section’s closing suggestion that is worth making explicit, because it says which of the two structures to reach for and the usual comparison — a rectangle against an index — does not.

The table is filled column by column, and a column depends only on its predecessor and on one character of the text. So the text may arrive one character at a time, be scored, and be discarded: the method needs $\Theta(m)$ state, never looks back, and reports each occurrence as its end position goes past. It is an online algorithm in the text and it requires the pattern in advance. Nothing about it can be prepared before the pattern is known, and everything about it is repeated for the next pattern.

An index inverts every clause. It requires the whole text in advance, spends a construction proportional to the text once, and thereafter answers about a pattern it had never seen — online in the pattern, since backward search consumes the pattern one character at a time and needs no notice of it at all.

So the two are not competitors on one axis; they are opposite corners of a small table with two axes on it, and which corner is wanted is decided by which of the two inputs arrives first and which one repeats.

One text, many patterns — a corpus searched repeatedly — favours the index, and the construction is amortised over the queries.

One pattern, endless text — a stream filtered for something known in advance — favours the table, and an index cannot be built at all, because there is nothing to build it over.

One pattern, one text is the case where the rectangle simply wins, since the index’s construction costs more than the single query it would serve.

And the case that is genuinely hard is the one the earlier essays measure: many patterns, an enormous text, and errors allowed. The index cannot answer the approximate question directly, so it answers an exact question about pieces of the pattern and hands the rest to a rectangle — which is seed-and-extend, and which is why that method has an index on one side of it and this table on the other.

What this leaves #

Two things, and both are the ground the rest of this collection covers.

The first is the cost model. Everything above charges one for an insertion, one for a deletion and one for a substitution, and calls the total a number of errors. That is a choice — a defensible one for a typo and a poor one for almost everything else — and the moment it becomes a parameter, the cheapest alignment moves.

The second is the rectangle. Approximate search over a large text cannot afford one cell per pair of positions, and no amount of care about the fill changes that. What changes it is not filling a table at all: preprocessing the text once into a structure that can answer questions about every position without visiting them, which is what an index is — and which turns out to have a price nobody on this site had yet been asked to pay.