The search that spends a budget

Backward search is a walk with no branching in it. One character of the pattern, one interval of rows, one narrowing; when the pattern runs out the interval’s width is the answer.

Allow errors and the walk becomes a tree. At every state the search may extend by any character of the alphabet — for free if it is the pattern’s own character, at a cost of one otherwise — or skip a pattern character, or consume a text character without consuming a pattern one. Three moves, a branching factor of $\sigma + 1$, and a budget that decides how deep the branching goes.

It is not a filter, which is the reason it is here #

The two filters in this phase both reduce an expensive stage: they propose candidate positions and hand them to a dynamic-programming table, which decides.

This does not propose anything. Every leaf it reaches with budget remaining is an interval of rows whose suffixes begin with a string within $k$ errors of the pattern, and that is the answer rather than a candidate. There is no verification stage, no false positive and no selectivity to report.

So it belongs beside the filters and is not one of them, and putting the three together is what three savings in three currencies is for. What it shares with them is the shape of the problem; what it does not share is that its cost is in the index rather than in the text.

The three moves #

At a state — an interval $[sp, ep)$, a position $i$ in the pattern, a remaining budget $b$ — the search may do three things.

Extend by a character $c$, which narrows the interval to the rows whose suffixes begin with $c$ followed by what was already matched. If $c$ is the pattern’s character at $i-1$ this costs nothing; otherwise it is a substitution and costs one.

Skip the pattern’s character, moving to $i-1$ without touching the interval. That is a deletion — the pattern has a character the text does not — and costs one.

Extend by a character without consuming a pattern character, which is an insertion, and costs one.

Every one of those is an interval extension or a bookkeeping step, and the interval extensions are what the plates count. There is no character comparison anywhere: an extension is two rank queries and an addition, exactly as in the exact search.

Where the pruning is #

The tree is pruned in exactly two places and both are forced rather than chosen.

An empty interval has no descendants. If no row’s suffix begins with the character being tried, that branch is over — which is the pruning that makes the whole method viable, because most characters at most states produce an empty interval once a few characters have been matched.

A state with no budget left finishes exactly. The rest of the pattern must match with no errors, which is an ordinary backward search: no branching, one extension per remaining character. That is where most of the tree’s leaves are, and it is why the node counts are far below the $\sigma^k m^k$ a naive bound would give.

There is no third pruning here and there could be one: an implementation can precompute, for each pattern suffix, the minimum number of errors any match must still incur, and abandon a branch whose budget is already below it. That is a real technique, it is not implemented here, and its absence is why the node counts in this strand are an upper bound on what a careful implementation spends.

It reads nothing #

The plates in this strand report three columns — cells computed, characters read, index ranks — and this method’s first two are zero.

Not small: zero. The index is queried under the seal that this field applies to every self-index, so a query that touched the text would be stopped at the read rather than reported afterwards, and the gate checks the counter at three budgets and finds nothing.

That is a stronger property than it sounds. The dynamic-programming table needs the text; the seed filter needs it for verification; the counting filter reads all of it. This method needs an index and nothing else, so a corpus that does not fit in memory can be searched approximately with only the index resident.

The text that does not have to be kept is where this collection established what self-indexing has to mean before such a claim can be made. Here it is load-bearing rather than decorative: the method’s whole advantage over the filters is that it never needs the thing they are reading.

What it spends instead #

Index ranks, and a great many of them. At a budget of three on a three-thousand-character text with a twenty-character pattern: 39,943 interval extensions and 177,046 rank queries.

The ratio between those two is about 4.4, which is the wavelet tree’s depth on a four-symbol alphabet plus the bookkeeping — a symbol rank is several bit-vector ranks, as rank is the only thing it does established, and the plates count both because a change to the tree’s shape moves one and not the other.

Against that, the whole table is 60,000 cells. Whether 177,046 ranks are cheaper than 60,000 cells is a question about a machine, not about an algorithm, and this collection does not answer it: a rank on a bit vector is a directory read and a popcount, and a table cell is three additions and a minimum. What the plates say is what each method does, in its own unit, with the units named.

Turning a row into a position #

The walk finds intervals of rows and a caller wants positions, which is the same conversion every structure in this field has to perform and which this method inherits rather than solves.

Each leaf is an interval; each row in it is one occurrence; and turning a row into a text position means walking LF until a sampled row is reached, exactly as in an ordinary locate. On the sweeps here the index is sampled at one value in thirty-two, so that walk is up to thirty-one steps per occurrence — a cost that has nothing to do with the budget and is not drawn on any plate in this essay.

It could be otherwise. An index sampled at the run boundaries locates in one predecessor query per occurrence, as every occurrence at the same price measures, and nothing about the walk cares which sampling is underneath it. The two strands of this phase compose: an approximate search over an r-index would spend the ranks measured here and locate at the price measured there.

Nothing in this collection has built that combination, and saying so is the point of the paragraph. Two independent improvements to the same structure are exactly the kind of thing that is assumed to compose and occasionally does not.

Exactness, checked against the table #

The method is exact and the check is the whole table.

At four budgets on a 1,500-character text, every end position the table reports as an occurrence within $k$ errors must be covered by a start position the walk reports. Not a sample: every one.

The check is stated in terms of ends and starts because the two methods answer different questions — the table reports where an occurrence ends and the walk reports where one begins — and an occurrence with $k$ errors starting at $s$ ends somewhere in a window of $2k+1$ positions. Reconciling them is the same conversion the filter that feeds the table needed, and the same helper does it.

That reconciliation is worth flagging as a place where a check can be too generous. A start position covers a window of ends, so a walk reporting many spurious starts would still cover every real end. The complementary check — that a budget of zero returns exactly the exact occurrences — is what closes that gap.

Duplication, and why the leaves outnumber the answers #

The plate of leaves against occurrences shows a gap that grows with the budget, and it is the method’s least attractive property.

A string within $k$ errors of the pattern can be reached by several different sequences of moves — substitute then delete, delete then substitute, insert a character and delete it again — and the walk explores all of them. At a budget of three the walk reaches seventeen leaves for seven distinct occurrences.

Some of that is removable: the standard trick is to forbid an insertion immediately followed by a deletion, and to canonicalise the order in which equal-cost operations are applied. None of it is done here, so the counts are an upper bound, and the shape of the growth is the finding rather than the constant.

What is not removable is that different alignments can produce genuinely different strings that both occur. Those are distinct answers, and the walk has to find each of them.

The costs by budget #

The whole sweep, in one place, on a three-thousand-character text with a twenty-character pattern over four symbols.

At $k = 0$: 20 extensions, 304 ranks, 4 occurrences. At $k = 1$: 336 extensions, 1,700 ranks, 4 occurrences. At $k = 2$: 4,150 extensions, 18,645 ranks, 5 occurrences. At $k = 3$: 39,943 extensions, 177,046 ranks, 6 occurrences.

Two thousand times the work for two more answers. That growth is the subject of the branches an error opens, which measures its factor and where it crosses the table; what matters here is that the growth is in the search rather than in a verification, which is what makes it a different kind of method from the two filters.

The check that must reject #

The failure this invites is to implement substitutions only. It is the natural first version: the loop over the alphabet is already there, the budget already decrements, and the result is a search that finds every occurrence differing from the pattern by $k$ substitutions.

Every position it returns is a real approximate occurrence. It returns fewer of them, and how many fewer depends on whether the text happens to contain an occurrence with an insertion or a deletion in it.

The gate constructs exactly that: a text holding the pattern with one character missing, a substitution-only walk beside the full one, and a requirement that the two disagree. Measured, one position against three.

That check is necessary because the answer set of the broken version is a subset of the right one — every gate that asks “is each reported position an occurrence” passes it, which is the same shape as reporting only the primary occurrences in the occurrences that cross a boundary.

A budget of zero must be an exact search #

The second rejection test is smaller and catches a different thing: at $k = 0$ the walk must return exactly the occurrences a scan finds, and at $k = 1$ it must return strictly more.

The first half catches a walk that has broken its no-cost path — a substitution charged where the character matched, say, which makes an exact search spend budget and find fewer things.

The second catches a walk whose budget is not being spent at all: a search that decrements nothing returns the exact occurrences at every $k$, costs almost nothing, and looks wonderful on every cost plate in this essay.

Both are cheap and both are necessary, and neither is implied by the exhaustive comparison at $k = 2$, which is why there are three checks rather than one.

Three methods, three places the cost lives #

It is worth stating where each method’s work happens, because the three answers are genuinely different and the plates make them look like three lines on one axis.

The table does its work over the text: $n$ columns times $m$ rows, every cell a comparison and two additions, and the text has to be present. Its cost does not depend on the error budget at all — $k$ only decides which of the filled cells count as answers, which is why the flat line on every plate here is not an approximation.

The filters do their work over the text as well, and then hand a fraction of it to the table. Their saving is the fraction; their collapse is when the fraction reaches one.

The walk does its work over the index, and its cost depends on the budget and on the alphabet and on nothing else about the text except how quickly intervals empty. It is the only one of the three whose cost is not a fraction of the table’s.

That is why the four-way plate has three columns rather than one axis, and why this collection refuses to sum them. The count somebody chose is the argument in general; here it is unusually stark, because one method’s principal cost is a number the others do not spend at all.

What this method is for #

Put plainly, because the cost plates in this strand are unflattering and the method is genuinely useful in a regime they do not emphasise.

It is for small budgets on a corpus that is not in memory. At $k = 1$ it costs 336 extensions and 1,700 ranks — well under any filter’s verification, and reading nothing. At $k = 2$ it is 4,150 and 18,645, still under the table. At $k = 3$ it is 39,943 against 60,000 cells, and at $k = 4$ it is five times over.

The filters run the other way: they are cheap where the text is available and where the candidate count is small, and their collapses arrive at the same budgets. So the three methods are not competitors in a single regime; they occupy different corners of a space with a budget on one axis and a resource on the other.

The multiplier per error is falling, and the crossing is two numbers #

Two thousand times the work for two more answers is the headline and the sweep says something more useful than a total: the per-error multiplier is not constant.

Take the extensions in order — 20, 336, 4,150, 39,943 — and divide each by the one before: 16.8, then 12.4, then 9.6. Each additional error costs less than the last, by about a fifth each time.

That matters for extrapolation, which is what anybody reading a budget sweep is doing. A reader taking the first multiplier and applying it forward predicts about 670,000 extensions at a budget of four. Continuing the observed decline predicts roughly 320,000 — and the essay’s own statement that a budget of four is five times the table’s 60,000 cells is 300,000. The falling multiplier extrapolates correctly and a constant one is out by a factor of two by the next step.

The mechanism is the pruning, and it strengthens with the budget rather than weakening. A state that has already spent errors is a state matching a string that differs from the pattern, and a differing string runs out of rows sooner — so the deeper the tree goes, the larger the share of its branches that die on an empty interval. The intervals do the pruning, and a larger budget hands them more to prune. That is why the naive $\sigma^k m^k$ bound this page dismisses is not merely loose but loose by a growing factor.

It also means the crossing against the table is not one number, and this page quotes it as though it were. In extensions the walk passes 60,000 between budgets three and four, at about $k = 3.2$. In ranks it passes 60,000 between two and three — 18,645 against 177,046 — at about $k = 2.6$.

Two units, two crossings, half an error apart. Which is exactly the position the count somebody chose argues for and this page adopts everywhere else: the units are not summed and are not converted, so the budget at which the walk stops paying has one answer per unit and the answer differs by enough to matter when the budget is an integer.

A reader choosing between the two methods therefore needs to know which of a rank and a table cell their machine finds expensive before the sweep says anything — and if ranks are the binding cost, the walk is already behind at a budget of three, where the extension count still says it is comfortably ahead. The branches an error opens measures the factor this section decomposes; what the decline adds is that the factor is a function of the budget rather than a property of the alphabet, so quoting one number for it is quoting a slope at a point.

The honest limit #

The walk here has two prunings and a published implementation has more. Bounding the remaining errors by a precomputed lower bound on each pattern suffix, and canonicalising equal-cost alignments, both cut the tree substantially; neither is implemented, so every node count in this strand is an upper bound.

The occurrence sets are compared against a full dynamic-programming table, which is quadratic, so the texts are three thousand characters and the patterns twelve to twenty. Nothing here says how the tree behaves on a corpus where the intervals stay non-empty for longer because there is simply more text.

And the cost is reported in interval extensions and ranks rather than in time. Which of a rank and a table cell is cheaper is a property of a machine and of a representation, and this collection’s fifth counter — the branch predictor — has not been pointed at either.