The branches that find nothing

A backtracking search over a self-index has one shape and every implementation of it has the same inner loop.

At each node of the search tree, take the current interval and try extending it by every character of the alphabet. Each extension is a rank walk down the wavelet tree, producing the sub-interval for that character. If the sub-interval is non-empty, recurse with the error budget decremented if the character was not the pattern’s.

The loop over the alphabet is the part this essay is about, because on a deep node most of those extensions produce nothing.

The count #

Twelve patterns, eight characters each, one error permitted, over eight thousand characters of a twenty-symbol alphabet.

Sixteen thousand eight hundred extensions attempted. Nine thousand two hundred and six of them produced an empty interval — 54.8%.

Each of those is a full rank walk: five levels of the tree, two ranks a level, ten bit-vector operations. The result is the number zero.

The published shape spends a hundred and sixty-eight thousand ranks. Enumerating the interval’s symbols instead spends twenty-four thousand and takes the seven thousand five hundred and ninety-four live extensions and none of the dead ones — a factor of 7.0.

The word “attempted” is doing work in that count and deserves unpacking. An extension is attempted when the loop reaches a character and performs the rank walk; it is dead when the walk returns an interval of zero width. So a dead extension is not a branch the search declined to take — it is one it took, all the way down the tree, and abandoned at the bottom.

That distinction matters because a reader might imagine the loop is cheap on dead characters, discovering absence at the first level. It is not. A rank walk on a wavelet tree follows the character’s code from the root to its leaf and computes the interval at every level; an interval that becomes empty at level two is still walked to level five, because the walk does not test for emptiness on the way down and would gain nothing by doing so — the code word is fixed and the walk is the same length.

An implementation could test at each level and cut short. That is a genuine optimisation of the loop and it is not what any published account describes, and it would recover part of the saving here without recovering the rest: the enumeration’s advantage is not only that it abandons dead branches early but that it never enumerates them.

What “removing” means here #

It is worth being precise about the difference between the two savings this strand has produced, because they are often described in the same sentence and they are not the same kind of thing.

The count that was already there made each extension cheaper: the compound walk returns a symbol’s rank and the number of smaller symbols from one descent, where the published shape summed σ separate ranks. Every extension still happens; each one costs less.

The enumeration makes the dead extensions not happen. The live ones cost the same as before — the descent reaches their leaves and hands back their intervals, which is what the rank walk did — and the dead ones are never attempted, because the descent never enters an empty child.

Those compose badly, and the reason is the subject of two factors that do not multiply. What matters here is that they are different mechanisms: one is arithmetic on a walk and the other is a pruning.

Why the dead share is so high #

The intervals a backtracking search works in are narrow, and a narrow interval holds few of the alphabet’s symbols.

At the root the interval is the whole text and every symbol is present, so nothing is dead. One character in, the interval is the rows for that character — a twentieth of the text, still holding most symbols. Six characters into an eight-character pattern on eight thousand characters, the interval holds a handful of rows and therefore a handful of symbols.

The search’s work, meanwhile, is concentrated at the bottom: a branching search’s node count grows with depth, so most nodes are deep, and most deep nodes have narrow intervals.

So the waste is worst exactly where the search spends its time. That is the opposite of the usual situation, where an optimisation helps the easy case and vanishes in the hard one.

The number that bounds it #

There is a simple bound on how many symbols an interval can hold and it explains most of the shape.

An interval of w rows holds at most w distinct symbols, and on a random-ish text it holds about σ(1 − (1 − 1/σ)^w) — the coupon-collector expression. At w = 6 and σ = 20 that is 5.2 symbols, so 14.8 of the 20 extensions are dead: 74%.

At w = 100 it is 19.9, so almost nothing is dead.

The measured 54.8% is an average over a search whose intervals span both regimes, weighted by how many nodes are at each width.

That expression is also why the dead share is nearly zero on DNA at any interval width above ten rows: σ(1 − (1 − 1/4)^10) is 3.98 out of 4. Two at binary, five at twenty-six measures that consequence directly, and DNA’s dead share at one error is 19% against protein’s 55%.

What the budget does #

The error budget is the dial that decides how narrow the intervals get, and the dead share follows it.

At zero errors the search follows one path — the pattern’s own characters — so it has one live extension per level and σ − 1 dead ones. Measured: 31% dead, and the saving is 5.8.

At one error it branches once at each level and reaches narrower intervals: 55% dead, saving 7.0.

At two errors: 75% dead, saving 9.2.

The direction is worth stating because it is not what a reader expects from “more work means more to save on”. The work grows and the fraction of it that was never going to help grows with it. A looser budget is not merely a bigger version of a tighter one; it is a search spending a larger share of its time discovering absence.

A looser budget wastes a larger share is where that sweep is drawn out and where the interaction with the pattern length is measured.

There is an interaction between the budget and the pattern length that the sweep does not separate and that is worth flagging. A longer pattern reaches narrower intervals at a given budget, because more characters have been matched; a larger budget reaches narrower intervals at a given length, because more branches have been taken. Both push the dead share up and the plate above moves only one of them.

Sweeping both is a two-parameter surface and this strand draws one cut through it. What the cut establishes is the direction and the rough magnitude; a workload with a different pattern-length distribution will sit somewhere else on the surface, and the honest statement is that the dead share is between a third and three quarters over the region measured.

The two searches have to agree #

The whole claim is that the enumeration removes work and nothing else, so the check is that the answers are identical.

Both searches visit the same live intervals in the same order — the enumeration’s output is iterated in leaf order, the loop’s in alphabet order, and on a balanced tree those are the same order. Both accumulate the same occurrences. On every pattern of every trial the two report the same interval widths.

A difference would not be a slower search; it would be a wrong one. That is what makes the equality the primary check and the operation counts secondary, and it is why the two searches are run on the same tree with the same counter rather than on two constructions.

What is not removed #

The dead branches go and three other costs stay, which is worth listing so that the factor of seven is not read as a factor of seven on a search.

The live extensions. Seven thousand five hundred and ninety-four of them, each reaching a leaf. The descent reaches those leaves too and the cost is comparable.

The search’s own bookkeeping. The recursion, the budget arithmetic, the occurrence accumulation. Not counted here, and on a real implementation it is not negligible.

The locating. Once the search has its intervals, turning rows into text positions costs LF steps proportional to the sampling gap. That is untouched by any of this and on a sparse sampling it can dominate.

So a factor of seven on the ranks a backtracking search spends inside the tree is the honest scope. The unit of cost is not one is the habit that requires saying so.

Where the live extensions go #

The seven and a half thousand live extensions are the search’s real work and they are worth a sentence, because a factor of seven on the total means the dead half was six sevenths of it.

That arithmetic only works because the loop pays ten ranks for a dead extension and the descent pays two ranks a node for a subtree containing several live ones. So the two sides are not comparable per branch: the loop spends a full walk on each of sixteen thousand eight hundred branches, and the descent spends a shared walk on the ancestors of seven and a half thousand live leaves spread over several thousand nodes.

Working it through: 16,800 extensions at ten ranks is 168,000. The descent’s 24,000 ranks over the same search is 12,000 nodes entered, for 7,594 live leaves — about 1.6 nodes a live leaf, which is the ancestor sharing at work.

So the factor of seven decomposes into two roughly equal parts: half of it is not walking the dead branches, and half is sharing the walks of the live ones. Neither alone would give seven.

The shape of a pruning #

Stepping back from the alphabet, this is a pruning and prunings have a common shape worth naming.

A search explores a tree of possibilities. Some branches lead nowhere and the cost of discovering that is paid on the branch. A pruning is a test that identifies dead branches more cheaply than exploring them does.

The usual pruning in this field is a bound: an estimate saying this branch cannot reach an answer within the budget, so it need not be explored. The branch that cannot reach an answer is that kind, and its correctness depends on the estimate being a genuine bound rather than a heuristic.

This one is different and simpler. It is not an estimate; it is the same computation, reorganised so that the dead branches are never enumerated. There is no risk of pruning a live branch, because the structure that reports which branches are live is the structure the branches are taken through.

That makes it a safe pruning in a sense a bound-based one is not, and it is why the check on it is an equality of answers rather than a proof about a bound.

Two prunings that look alike and are not #

It is worth setting this pruning beside the one this collection already had, because the two are complementary and a search should use both.

The bound-based pruning asks whether a branch can still reach an answer. A search with one error left and four characters of pattern remaining cannot afford two more mismatches, so a branch requiring them is cut without being explored. That is the branch that cannot reach an answer, and its correctness rests on the estimate being a genuine lower bound: a heuristic that is sometimes optimistic prunes a live branch and loses an occurrence, silently.

The enumeration pruning asks whether a branch exists. It is not an estimate and cannot be optimistic, because the structure reporting which symbols are present is the structure the extensions go through.

They remove different branches. The bound removes branches that are live in the index and dead in the budget; the enumeration removes branches that are dead in the index whatever the budget. So neither subsumes the other and a search doing both removes more than either.

Whether the two compose multiplicatively is a question this strand does not measure and the answer is probably no, for the reason two factors that do not multiply gives about a different pair: two savings that both remove work from the same pool remove less together than the product suggests. The bound’s branches and the enumeration’s branches overlap wherever a branch is both absent and unaffordable, which at a tight budget is most of them.

What a search should do with this #

The practical form is short.

If the search branches, enumerate. Any search that tries more than one character at a node — approximate matching, wildcards, regular expressions over an index, a spelling-correction walk — is paying for dead branches and the enumeration removes them at no cost in bits.

If the search does not branch, do not. An exact search knows its character and the enumeration reports every present symbol to hand back one. The saving that is a loss measures that at about twice the walk’s cost.

And the factor depends on the alphabet. 2.8 on DNA, 7.0 on protein, at one error. A factor quoted without the alphabet is a factor about one workload.

What the search looks like written out #

The two inner loops are short enough to describe and the difference between them is one line, which is worth stating because it is smaller than the factor of seven suggests.

The published shape: for each character of the alphabet, walk the tree to compute its interval; if the interval is non-empty, recurse. The alphabet is the outer loop and the tree walk is inside it.

The enumeration: descend the tree once carrying the interval, collecting every leaf reached along with its sub-interval; then for each collected symbol, recurse. The tree walk is the outer structure and the symbols fall out of it.

Same recursion, same budget arithmetic, same accumulation. The only difference is which of the two — the alphabet or the tree — is the thing being iterated.

That is the sense in which this is a reorganisation rather than an algorithm. Nothing new is computed; the same ranks are performed in a different order, and the ones that would have produced zero are not performed because the order makes them visibly unnecessary.

A useful way to hold it: the loop asks σ questions of the form “is c here?” and the descent asks one question of the form “what is here?”. The second question has an answer whose size is the answer, and the first has σ answers most of which are “no”.

The extensions nobody counts #

There is one more thing worth noticing about the published shape and it is not about cost.

An implementation looping over the alphabet has to know the alphabet. That is fine for DNA and awkward for a general index, where σ might be a few hundred and most of it absent from any given text — a search over an index of English text would try every byte value at every node, and 200 of the 256 would be dead at the root.

The enumeration needs no alphabet at all. It reads what is there, which means an index over an unknown or open alphabet costs nothing extra, and a text using a small part of a large alphabet is handled without anyone having to compute which part.

That is not a saving anyone would build the operation for, and it removes a parameter from the implementation — which on the evidence of this collection is worth as much as most savings, because a parameter is a thing that can be wrong.

And there is a case where it is not merely tidier but necessary. A search over an index whose alphabet is the whole of Unicode’s assigned range cannot loop over it — the loop would be a hundred and fifty thousand rank walks a node against an interval holding a handful of characters. The published shape is unusable there and the enumeration is unchanged, because its cost never depended on σ except through the tree’s depth.

That is the far end of the alphabet axis this strand sweeps, and it turns a factor into a feasibility. Two at binary, five at twenty-six draws the four ordinary alphabets; the interesting extrapolation is the one where the loop stops being an option at all.