Asking about symbols that are not there

The previous operation removed a factor of the alphabet from one extension. It did not remove an extension.

The count that was already there measured the compound walk: a wavelet tree can return a symbol’s rank and the number of smaller symbols before a position from one descent, at exactly the cost of the rank alone. Where a bidirectional extension had been summing σ separate ranks, it now performs one walk — 139.7 bit-vector ranks against 10.0 at a twenty-six letter alphabet.

That made each question cheaper. It did not stop the question being asked. A search that extends an interval by every character of the alphabet still tries every character, and on a pattern deep in a backtracking search almost all of them produce an empty interval — a full rank walk down the tree whose entire result is the discovery that there was nothing there.

The operation #

Descend from the root carrying the interval. At each node the interval splits in two, and a child is entered only if its half is non-empty. At a leaf, report the symbol and the interval it occupies.

The nodes visited are exactly the ancestors of the leaves present. So the cost is proportional to how many distinct symbols the interval holds rather than to how many the alphabet has.

On the interval drawn above — sixty-four positions of a twenty-six symbol alphabet, holding four distinct symbols — the descent enters fifteen nodes and spends twenty-four bit-vector ranks. A loop over the alphabet spends two hundred and sixty: twenty-six symbols at ten ranks each, whether or not the symbol is there.

That is a factor of ten point eight, and the ratio is not a constant. It is the whole subject of the strand.

The picture is worth reading carefully because it shows the whole mechanism. Every dark node is one the walk entered; every pale node is one the loop pays for and this walk never touches. The dark nodes form a subtree that fans out from the root and stops at four leaves, and the pale ones are the rest of a twenty-six leaf tree.

What the picture does not show is that the loop’s cost is not the pale nodes. A loop asking about symbol c walks the path from the root to c’s leaf, which is mostly dark nodes — it re-walks the shared top of the tree once per symbol. So the loop’s waste is partly in nodes the descent visits too, visited many times over, and partly in nodes it never visits at all. The descent’s advantage is both: it visits each node once, and it visits fewer of them.

What the descent returns beyond the set #

The operation hands back more than which symbols are present, and the extra is what makes it useful to a search rather than merely to a census.

Each reported symbol comes with the interval it occupies in its own leaf — [rank_c(lo), rank_c(hi)) — which is exactly the interval a search would extend into. So a search that enumerates does not then have to compute the intervals; they arrived with the enumeration.

That is a second saving on top of the first and it is easy to overlook. A loop that discovers a symbol is present has to compute its interval, which is the same rank walk again unless the implementation is careful. The descent computes both in one pass because the interval is what it carried down.

There is a third thing the descent gives away for free and it matters to a document listing rather than to a search: the count of each symbol in the interval, which is the width of its sub-interval. A caller wanting to know not just which symbols are present but how often each occurs gets that at no extra cost, where the loop gets it only by subtracting the two ranks it already computed — the same information, and the loop was already computing it.

So on that particular query the two are closer than the ratios above suggest, because the loop’s per-symbol work produces a count too. What the loop cannot avoid is doing it for the absent symbols.

Where the cost goes #

The cost is d log(σ/d) + d nodes for d distinct symbols, which is the standard counting bound on the ancestors of d leaves in a tree of σ.

At d = 1 that is one root-to-leaf path: log σ nodes, and the descent is a rank walk. At d = σ every node of the tree is entered, which is 2σ − 1 nodes, and the descent costs about the same as the loop.

So there is no regime where the descent is much worse and one where it is much better, which is the shape a replacement operation should have.

Measured at σ = 32: the loop costs three hundred and twenty ranks at every point. The descent costs ten ranks when one symbol is present and sixty-two when all thirty-two are. That is a factor of thirty-two at one end and five at the other.

The descent’s cost rising from ten to sixty-two while the symbol count rises from one to thirty-two is the log(σ/d) discount visible directly: at d = 1 the cost per symbol is ten and at d = 32 it is 1.94.

Sweeping the interval’s width rather than the symbol count shows the same curve from the other side. A four-position interval on twenty-six letters holds four distinct symbols and the descent costs fourteen ranks against the loop’s two hundred and sixty — a factor of 18.6. By sixty-four positions the interval holds twenty-three symbols and the descent has flattened at fifty-four ranks, a factor of 4.8, and it does not rise further however wide the interval gets.

That flattening is the reason the operation has a bounded worst case. Once every symbol is present there is nothing left to enter, so the descent’s cost is capped at the whole tree — 2σ − 1 nodes — and the loop’s is σ⌈log σ⌉. The ratio at the cap is log σ / 2, which at twenty-six symbols is 2.4 and at a thousand is 5.

So the operation is never much worse than the loop and is often much better, and the “often” is the region a search actually works in.

Why a node is two ranks and not four #

One implementation detail decides whether any of this is worth having.

At a node, the left child’s interval is [rank₀(lo), rank₀(hi)) and the right child’s is [rank₁(lo), rank₁(hi)). Computing all four bounds looks like four ranks.

It is two, because rank₀(x) is x − rank₁(x). One rank at each end of the interval gives both children.

A version calling rank₀ separately returns exactly the same symbols at twice the cost, and nothing about the answer can see the difference. A node costs two ranks is the check: the ranks a descent spends must equal twice the internal nodes it entered, exactly.

That is the kind of claim that would otherwise be a comment in the source, and a comment cannot fail.

What a search actually spends its time on #

The reason to build this operation is a search, and the numbers there are larger than the census numbers above.

A backtracking search for an eight-character pattern within one error, over a twenty-symbol alphabet: the published shape spends a hundred and sixty-eight thousand bit-vector ranks and takes sixteen thousand eight hundred extensions, of which nine thousand two hundred and six find nothing. Fifty-five per cent of the work is discovering absence.

The same search enumerating instead spends twenty-four thousand ranks — a factor of seven — and takes the seven thousand five hundred and ninety-four live extensions and none of the dead ones.

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. One character in, the interval is the rows for that character — still wide, and still holding most symbols. Six characters in, on a text of eight thousand, the interval holds a handful of rows and therefore a handful of distinct symbols.

So the loop’s waste is worst exactly where the search spends most of its time, which is at the bottom of the tree where the branching factor has multiplied. That is the opposite of a saving that appears in the easy case and vanishes in the hard one.

The share of dead branches rises with the error budget — 31% at no errors, 55% at one, 75% at two — which is the opposite of what a reader might expect from “more work means more to save on”. The work grows and the fraction that was never going to help grows with it, because a larger budget reaches narrower intervals and a narrower interval holds fewer symbols.

The saving follows: 5.8, 7.0 and 9.2 at the three budgets. So the operation is worth most exactly where an approximate search is most expensive, which is the useful direction and is not automatic. The search that spends a budget is where the budget became a dial in this collection rather than a setting.

Where it does not pay #

The honest limit is the alphabet, and it is severe on the case this operation is most often wanted for.

On a binary alphabet the loop asks two questions and the descent enters two nodes, so the saving is a factor of two and there is nothing to report. On DNA — four symbols — it is 2.7. On protein it is 4.8 and on the Latin alphabet 4.8.

Approximate matching in this field is mostly done on DNA, and DNA sits near the bottom of that list. The branches an error opens is where the branching factor of an approximate search was first measured here, and its numbers are on a four-symbol alphabet for the same reason: that is where the work is.

That does not make the operation worthless there: a factor of 2.7 on a search costing millions of operations is a real saving. It does mean that a factor quoted from a natural-language measurement is about four times what a genomics workload will see.

The shape the strand takes #

Three questions follow and each is a separate essay.

What is the cost proportional to? The distinct symbols present, with a logarithmic discount for their sharing ancestors — measured against a fixed alphabet so that d moves and σ does not.

What does it do to a search? Removes the dead branches, which are between thirty-nine and seventy-five per cent of the extensions depending on the error budget.

What does the answer’s order mean? The set is the same on every tree shape and the order is not, and a search that reads the output as sorted computes a plausible wrong number.

The third is the one that makes this operation the same shape as the one before it. Every child at once and the tree the operation insists on between them established that the compound walk needs an ordered tree and that a Huffman-shaped one produces a number wrong on 81% of queries. The enumeration has the same dependency in the same place, and it is weaker: the set needs no order, and only a caller wanting the symbols sorted does.

What the operation is not #

Two things it might be mistaken for are worth separating, because both are real operations with different costs.

It is not a range distinct-count. Reporting how many distinct symbols an interval holds without naming them can be done in o(d log σ) with additional structure, and the descent is not that: it names them, and its cost is the naming.

It is not select. A caller wanting the kth occurrence of a symbol needs a different walk, upward rather than downward, and this collection built that separately — select is not rank backwards is where the asymmetry between the two directions was measured. The descent is a downward operation and returns no positions.

What it is, precisely, is a range operation that returns the alphabet’s restriction to a range together with the sub-intervals. That is a longer sentence than “enumerate the distinct symbols” and it is the accurate one, because the sub-intervals are half of what makes it useful.

The published name, and why it took a strand to arrive #

The operation has a name in the literature — interval_symbols — and it has had one for a decade. It is not obscure, and this collection did not discover it.

What took a strand is noticing that two problems already in hand were instances of it. A backtracking search branching over the alphabet is enumerating an interval’s symbols; a document listing finding the distinct documents in a row range is enumerating an interval’s symbols. Neither is described that way in its own literature, and neither paper’s vocabulary contains the word.

The tree answers the question is where the second of those lands, and the two together are a case study in a specific kind of blindness. A structure added for one reason has a published operation set; the operation set contains an answer to a problem already being solved another way; and nothing about the reason the structure was added suggests looking.

The instruction that comes out is narrow enough to act on: when a structure is added, read its operation list against the problems already open. Not a general injunction to read more, but a specific thing to do at a specific moment.

What it costs to have #

Nothing. That is worth stating plainly because it is unusual in this collection.

The descent needs no structure the tree does not already have: the same bit vectors, the same directories, the same code table. It is a different traversal of an object already built, so it adds no bits and no construction time, and a structure that supports rank supports it.

Compare that with the other savings this field offers. A compressed bit vector costs a directory and a decode per rank. A denser sampling costs bits. A bidirectional index costs a second index. Every one of those is a trade.

The enumeration is not a trade. It is a strictly better way to perform an operation the structure already performed, and the only reason not to use it is that a caller wants one named symbol rather than all present ones — in which case the rank walk is what it always was and nothing is lost.

That is the rare shape and it is worth naming because it is what makes the strand’s headline safe. A factor of seven on an approximate search, at no cost in bits, is a claim that does not need a denominator.

What was actually removed #

It is worth being precise about the relationship between this operation and the one before it, because the two are usually described as complementary and they are not.

The compound walk removes a factor of σ from computing a smaller-count for one named symbol. The enumeration returns, for every present symbol at once, both its interval and — by running-summing the counts in leaf order — its smaller-count.

So the enumeration does what the walk does, for every symbol, in one descent. On a branching search they do not compose: taking both is taking the second one twice. Two factors that do not multiply is where that is measured, and the shortfall from the product turns out to be exactly the walk’s own factor.

Where they differ is the exact search, which knows which symbol it wants. There the enumeration reports every symbol present in order to hand back one of them, and costs about twice what the walk costs. The two savings split by the shape of the search rather than stacking.