A node costs two ranks

A descent through a wavelet tree carries an interval and splits it at every node. The left child gets the positions whose bit is zero and the right child gets the positions whose bit is one.

Written out, that is four bounds: the left interval is [rank₀(lo), rank₀(hi)) and the right is [rank₁(lo), rank₁(hi)). Four rank queries a node.

It is two, and the reason is one line of arithmetic: rank₀(x) = x − rank₁(x). The zeros before a position are the position minus the ones before it, because every position is one or the other.

So one rank at each end of the interval gives both children, and a node costs two bit-vector ranks rather than four.

Why this is not a micro-optimisation #

A factor of two would be worth having anyway, and this one decides whether the operation is worth having at all.

The descent’s whole claim is that it beats a loop over the alphabet. On a twenty-six letter alphabet with four symbols present, the loop costs two hundred and sixty ranks and the descent costs twenty-four. At four ranks a node it would cost forty-eight — still better, and the factor falls from 10.8 to 5.4.

On a wide interval where every symbol is present the loop costs two hundred and sixty and the descent costs fifty-four. At four ranks a node it would cost a hundred and eight, and the factor falls from 4.8 to 2.4.

So the identity is roughly half of the operation’s advantage in the easy case and all of the margin in the hard one. On a two-symbol alphabet, where the loop costs four ranks and the descent costs two, doubling the descent makes the two identical and the operation pointless.

There is a second place the identity pays and it is easy to miss because it is not a rank. The emptiness test — enter a child only if its half of the interval is non-empty — needs both children’s bounds to decide, and having derived one from the other means the test costs a comparison rather than a query. A version computing rank₀ separately would pay the query even for a child it is about to discard.

So the identity and the pruning interact: on a narrow interval most children are empty, and most of the rank₀ queries a four-rank implementation performs are queries about intervals it will not enter. The waste is worst exactly where the operation is meant to be best.

Why no check on the answer can see it #

This is the part that makes the identity worth an essay rather than a comment.

A descent that computes rank₀ separately visits the same nodes, enters the same children, reaches the same leaves and reports the same symbols with the same intervals. Every value it returns is correct. The two implementations are indistinguishable by any test of their output, on any input.

What differs is a number that nothing in the answer records.

This collection has a name for that shape and a habit for it: an assertion that has never rejected anything proves nothing, and a property no output can reveal has to be asserted on the operation count. So the check is:

The ranks a descent spends equal twice the internal nodes it entered, exactly.

Not approximately, not within a tolerance. Exactly, because the identity is arithmetic and any deviation is a node doing something other than one rank per end.

Measured on a twenty-six symbol tree over four thousand characters with a two-thousand-position interval: fifty-four ranks for twenty-seven internal nodes. Twenty-six leaves, fifty-three nodes entered, twenty-seven of them internal.

There is a version of this failure that is worse than a doubled cost, and it is the reason the check is an equality rather than an upper bound. An implementation that computes rank₀ instead of deriving it, on a vector whose rank₀ is implemented as n − rank₁ internally, spends the same two queries and charges four — so the counter reports a cost the machine did not pay.

That is the mirror defect: an operation count that overstates rather than an implementation that overspends. An inequality check catches neither and an equality catches both, because both make the count differ from twice the node count.

This collection has met the overstating version before, in a different field. The comparison that is not one comparison is where the unit of a count first had to be pinned down, and the lesson is the same: a counter that is not tied to the structure by an exact relationship is a counter measuring itself.

The rejection test that goes with it #

An equality check passes trivially if the thing being counted is wrong in both places, so the strand carries a rejection alongside it.

The rejection removes a different property — the emptiness test — and requires the cost to change while the answer does not. A descent that recurses into every child unconditionally, empty or not, returns exactly the same symbols: an empty subtree contributes nothing, so the output is identical.

Measured on an eight-position interval over a twenty-six symbol alphabet: the pruned walk enters twenty-four nodes and spends thirty-four ranks; the unpruned one enters fifty-five and spends fifty-four. Same seven symbols, same intervals, 1.59 times the cost.

That is the two-ended shape. One check requires the count to be exactly twice the nodes; the other requires that a version doing more work is caught by the count and not by the answer. Together they say that the operation count is measuring the implementation rather than being computed from it.

Where else the identity applies #

The same arithmetic runs through every operation on a wavelet tree and it is worth collecting them, because the saving is the same each time and the reason it is available differs.

A rank walks one root-to-leaf path and needs only one child’s bound at each level — whichever the code says to follow. So it uses one rank a node, not two, and the identity buys it nothing: it never needs the other child.

An access walks down asking which side each position is on, which is one bit read and one rank a level. Same.

A select walks upward and needs the inverse operation, which the identity does not touch: mapping a position in a child back to the parent requires select₀ or select₁ on the parent’s vector, and there is no arithmetic relating those. Select is not rank backwards is where that asymmetry was measured, and it is the reason a tree supporting both operations needs two directories rather than one.

The compound walk — returning a rank and a smaller-count from one descent — uses the identity in a different form. When the code says “go right”, the count of everything that went left is the position minus the ones, which is rank₀ derived rather than computed. The count that was already there is that operation, and its saving is arithmetic on numbers already in hand for the same reason.

The enumeration is the only one that needs both children at every node, so it is the only one where the identity halves the cost rather than being irrelevant.

That is a satisfying pattern: the identity is worth nothing to the operations that follow one path and everything to the one that follows a subtree.

There is a sixth operation worth adding to that list because it is the one this strand’s other half depends on: the document listing descent, which is the enumeration applied to a document array. It uses both children at every node for the same reason and gets the same halving, and the tree answers the question quotes operation counts that assume it.

Two problems, one operation, one identity underneath both. That is worth noticing because it means the identity’s value is not local to a search: any query that needs a subtree of a wavelet tree rather than a path gets it, and any query that needs a path does not.

The classification is that clean. Path operations use one child a node and subtree operations use both, and the identity is worth a factor of two to exactly the second kind.

The general form of the trap #

The defect this check exists to catch has a shape that recurs, and it is worth stating without the wavelet tree.

A quantity computed twice when one computation determines the other is invisible to every test of correctness and visible only to a cost measurement. It is not a bug in any sense that a type system, a test suite or a code review of the output would find, and it does not produce a wrong answer under any input.

The reason it survives is that the two computations are usually in different places — one on each branch of a conditional — so the redundancy is not visible in a single line. Here they are rank0(lo), rank0(hi) in one expression and rank1(lo), rank1(hi) in the next, and the relationship between them is a fact about bit vectors rather than about the code.

The way to catch it is the way this collection catches everything of this kind: charge the operations, and assert an exact relationship between the charge and the structure. If the assertion is an inequality it will pass on a doubled cost; if it is an equality it will not.

What a rank actually is, and why two is the right unit #

The check counts bit-vector ranks, and it is worth being explicit about what one of those costs, because “two ranks a node” is only a meaningful unit if a rank is a meaningful thing.

A rank on a plain bit vector with a two-level directory is: one superblock counter read, one block counter read, and a scan of at most one block’s worth of bits. Three memory touches and a popcount, in the shape rank is the only thing it does measured, and constant in the vector’s length.

On a block-classed vector it is more: the same two directory reads, then a decode of the block from its class and offset before the popcount. Several times the work, which is the price of the compression.

So “two ranks a node” is a fixed number of a variable-cost operation, and the operation’s cost depends on the representation rather than on anything the descent does. That separation is why the count is worth taking: it is a property of the algorithm, and the representation multiplies it by a constant the algorithm has no opinion about.

A count that folded the representation in — “eleven memory touches a node” — would be a count about one representation, and every factor in this strand would have to be re-measured when the vectors changed.

What the identity costs #

Nothing, and it is worth saying because the alternative would be a trade.

Deriving rank₀ from the position and rank₁ is a subtraction of two integers already in registers. It requires no extra structure, no extra directory, and no change to the bit vector’s representation. A structure supporting rank₁ supports it.

The one situation where it would not be free is a representation whose rank₀ is cheaper than its rank₁ — a compressed vector storing zero-runs, say — where computing rank₀ directly might beat a subtraction. No representation in this collection has that property, and the check would notice: it requires exactly two ranks a node, so an implementation calling a cheaper rank₀ would fail it and would have to argue its case.

That is the right behaviour for a check. It is not there to forbid a better implementation; it is there to make anyone who writes a different one say so.

What it does to the strand’s numbers #

Every factor quoted in this strand assumes the identity, so it is worth stating what the numbers would be without it.

The census factors — 32 at one symbol present, 5.2 at thirty-two — would be 16 and 2.6.

The search factor on a twenty-symbol alphabet with one error — 7.0 — would be 3.5.

The DNA factor of 2.7 would be 1.35, which is close enough to nothing that the operation would be hard to justify on the alphabet the field mostly uses.

So the identity is not an implementation detail of a good operation; it is half the argument for the operation existing. An account of interval_symbols that does not mention it is describing something twice as expensive and with a much narrower range of usefulness.

Three things the equality would catch #

It is worth listing what the check would actually reject, because a check nobody can imagine failing is a check that has not been thought about.

A four-rank descent. The count comes out at four times the internal nodes and the equality fails immediately. This is the defect it was written for.

A descent that visits a node twice. An implementation memoising badly, or recursing on an interval it has already handled, spends more ranks than nodes entered — and the node count is taken from the same walk, so the two would still be in a two-to-one ratio unless the node count is taken independently. It is: the descent returns the nodes it entered and the counter records the ranks, and a doubled visit raises both. So this one is not caught, and saying so is more useful than implying it is.

A counter that charges the wrong thing. If the bit vector’s rank were charging two internally — a superblock read and a block read counted separately — the count would be four times the nodes and the equality would fail. That is the check doing its job on the instrument rather than on the algorithm, which is a use it was not designed for and is the one it has already served: the count is what pins down what a rank means.

The middle case is the honest gap. An equality between a cost and a shape catches a cost that is wrong for the shape, and it does not catch a shape that is wrong. Catching that needs the bound — k(1 + log(σ/k)) ancestors for k leaves — and this strand asserts the cost against the shape rather than the shape against the alphabet.

Where the count is quoted #

The strand quotes operation counts in three places and they are all this unit, which is worth saying once so a reader can compare them.

Asking about symbols that are not there quotes twenty-four ranks against two hundred and sixty for one interval. Proportional to the answer, not the alphabet quotes ten to sixty-two against a flat three hundred and twenty. The branches that find nothing quotes twenty-four thousand against a hundred and sixty-eight thousand on a search.

All three are bit-vector ranks, all three are two a node on the descent’s side, and all three would double without the identity.

The habit this is an instance of #

Three checks in this collection have the same form and it is worth naming the form.

A structural equality between a cost and a shape: ranks equal twice the internal nodes. A cost change with an answer held fixed: the unpruned walk returns the same symbols and costs more. And a two-ended requirement: the operation must be cheap where the claim says and expensive where it does not.

None of the three is a test of the output. All three are tests of the relationship between the output and what was spent producing it, which is the thing an operation count is for and which a correctness test cannot reach.

That is why this collection charges operations at all. A structure that returns the right answer is the easy half; a structure that returns it for the reason its account gives is the half that needs an instrument.