The count that was already there

A bit vector supports one operation and everything here is built on it: rank₁(i), the number of ones before position i.

rank₀(i) is not a second operation. It is i − rank₁(i), exactly, always, for arithmetic reasons that no representation can change: every position before i holds either a one or a zero.

That identity is the whole content of the compound operation, and it is why the operation is free rather than cheap.

The measurement #

An assertion that something costs nothing has to be measured on a counter rather than read off the code, because “no extra work” is exactly the kind of claim that is true of the version somebody wrote and false of the version that ships.

So: one wavelet tree, one operation counter, a hundred calls of rank and a hundred of rankAndLess at the same positions.

500 bit-vector ranks each. Five per call, which is the depth of a twenty-one-symbol tree. The compound walk performs no operation the plain rank does not.

That check is in the gate, and it fails if the two ever differ — which is the form this collection insists on: the check must reject, and a claim about an operation count is checked by counting operations.

Where the free count comes from #

Follow one level. The walk is at position p in a node’s bit vector, and the code says go right.

It needs rank₁(p) to move: that is the position in the right child. One operation.

The count of everything that went left at this level is rank₀(p), which is p − rank₁(p) — a subtraction of two numbers the walk is holding. Nothing is queried.

And if the code says go left instead, the walk needs rank₀(p), and the right-hand count is not wanted at all, because the symbols on the right are larger.

So at every level, one query, and the second child’s count is either free or unwanted. Over the whole descent that is ⌈log₂ σ⌉ operations, which is what a rank costs.

Why a loop was written instead #

Two reasons, and both are about how the question was phrased rather than about the structure.

The first: rank_c(i) is an operation the wavelet tree offers, and the smaller-symbol total is not. Faced with an interface that has one method on it, the natural implementation is to call it repeatedly. The tree exposes rank(c, i); the extension needs the sum of rank(d, i) over every symbol d below c; the loop writes itself.

The second: at the alphabet where this structure was first built, the loop is short. On DNA the tree is two levels deep and the loop is at most four terms, so an extension is 18 ranks rather than 6 — a factor of three, on an operation nobody had counted, in a search that was being measured in nodes explored rather than in bit-vector operations.

Two counts disagree is the theme this collection returns to most often, and it applies here in its usual form: the search was being counted in the unit that made it look uniform, and the unit that varies is one level down.

What “free” is not #

Three qualifications, because “costs nothing” invites more than it says.

It is not free of the tree’s shape. The walk’s cost is the code’s length, so a symbol with a long code costs more than one with a short code, on both operations equally. What is free is the second quantity, not the descent.

It is not free of the ordering condition. The subtraction gives the count of everything that went the other way; calling that “smaller” needs the leaves in the alphabet’s order, which costs a few per cent in size and is the subject of the tree the operation insists on.

And it is not free in cache terms. Two ranks at the same level of the same vector touch the same directory entry and probably the same cache line; a loop over σ symbols walks σ different paths and touches σ different lines at every level. So the machine-level saving is larger than the operation-count saving, and this collection does not measure machine-level anything — the cost model is an input, and the model here counts operations.

Where else the identity was available #

Once named, the same “the other count is a subtraction” shape turns up in three more places in this collection, and in two of them it was already being used without comment.

Select support. A structure answering select₁(k) — where is the k-th one — is built over the same directories a rank uses, and select is not rank backwards is the essay about why it nonetheless needs its own machinery. What it shares is the arithmetic: a block’s zero count is its width minus its one count, so a directory built for one answers both.

The document array’s complement. In a document index, the rows not belonging to a document are the rows minus the rows that do, which is why nothing here ever stores a complement.

And the interval width in a backward search. ep − sp is the occurrence count, computed from two numbers the search already holds — nobody has ever computed it by counting rows, and nobody would.

The third is so obvious that it makes the first two look strange. All three are the same identity, and only one of them was being used in the place this page is about.

What it changes about the earlier numbers #

One published measurement moves, and it moves by a factor.

An extension is not one rank: 16.5 ranks an extension on four symbols and 138.6 on twenty-six. That sentence stands as a description of the implementation it described. What it should not be read as is a property of a bidirectional index, because a bidirectional index whose tree has ordered leaves performs 6.0 and 10.0.

The wider claim it supported — that the compound operation is the largest single term in an approximate search’s cost — is confirmed and quantified: on a twenty-six-symbol alphabet the search performs 225,400 bit-vector ranks with the loop and 16,140 with the walk, and every other cost in the search is unchanged.

The general lesson #

It is a small one and it is worth stating because it recurs.

When an interface offers one operation and a caller needs a related quantity, ask what the operation’s implementation already computed. A rank down a tree computes a partition at every level, and the partition’s other side was being recomputed by a loop over the whole alphabet.

The reason it survived so long is that both the loop and the walk are correct, both are fast enough at a four-symbol alphabet, and the unit that separated them was one nobody was counting. That is the shape of nearly every constant-factor result in this collection: not a wrong answer, a right answer computed in a unit that hid the cost.

What the identity does not give #

Three things it might be expected to give and does not, because a free count in one direction is not a free structure.

It does not give select. Knowing how many ones precede a position says nothing directly about where the k-th one is, and select is not rank backwards is the essay about why that needs its own machinery — a sampled directory over the ones, costing bits a rank directory does not.

It does not give the count of a set of symbols that is not a prefix of the alphabet. The walk partitions the alphabet around one symbol, so it answers “how many below c” for free. “How many between c and d” is two walks, and “how many in this arbitrary set” is a walk per symbol again.

And it does not give the distinct symbols present. A search branch would like to know which symbols actually occur in an interval, so that it does not try all σ of them; that is a different traversal — down every node the interval touches rather than down one path — and it costs proportionally to the number of distinct symbols. Named here, not built.

So the free count is exactly one quantity: the number of positions whose symbol sorts before the one being asked about. It happens to be the quantity a bidirectional extension needs, which is why this operation matters at all.

Why the counter is the check #

An operation count is the kind of claim that is easy to state and easy to get wrong in a way nobody notices, which is why this collection insists on counting rather than reading.

The failure mode is specific: a helper that looks like arithmetic but is a query. bv.rank0(at) is a method call on a bit vector, and it increments the counter, because it is an operation — a directory lookup and a popcount. Writing at - bv.rank1(at) instead is a subtraction of two numbers in hand. The two lines look almost identical and differ by one bit-vector query per level.

An implementation that used the first form would be correct, would return the same numbers, and would cost exactly twice what this page claims. Nothing about its output would say so.

That is why the check is a counter comparison rather than an output comparison. It fails if the two ever differ, so the sentence “the compound walk performs no operation a plain rank does not” is a thing the build can refuse.

What it is worth on the whole search #

The saving is per extension, and an approximate search performs thousands of them — 1,614 on a twenty-six-symbol alphabet for a fifteen-character pattern within two substitutions.

At 139.7 bit-vector ranks each that is 225,400 operations, and at 10.0 it is 16,140. Everything else about the search is identical: the same nodes, the same pruning, the same dead branches, the same answers.

So on the alphabet where it matters most, the compound walk removes about 209,000 bit-vector operations from one query. That is the largest single term in the cost of an approximate search on this structure, and it was arithmetic that had been performed and thrown away at every level of every descent since the index strand opened.

The habit worth keeping #

Two sentences, and they are about interfaces rather than about wavelet trees.

A structure’s operations are the ones somebody exposed, not the ones it can answer. A wavelet tree exposes rank(c, i) because that is what an FM-index needs. The partition of the alphabet around c is computed at every level of every rank and discarded, and it is only visible if somebody asks what the implementation already knows.

And a loop over an alphabet is a signal. Any time a caller iterates over the symbols to accumulate something the structure could accumulate during a single descent, there is a compound operation available. This collection now has two examples — the smaller-symbol count here, and the interval’s distinct symbols, which is named and unbuilt — and the second was found by looking for the same shape.

The scope of the identity, as a test with three cases #

The closing habit — a loop over the alphabet is a signal — can be sharpened into something a reader can apply without thinking about wavelet trees, because the identity has an exact scope and the scope is easy to state.

A descent partitions the alphabet at every level, and every partition is binary. So one descent determines, for free, the count of symbols below the target and the count above it, and nothing else. Any query that can be written as a count over a prefix of the ordered alphabet is answered by one walk; any query that cannot is not.

That is a small family. There are $2^\sigma$ subsets of the alphabet and $\sigma + 1$ prefixes of it, so the free queries are a vanishing fraction of the possible ones — and the quantity a bidirectional extension needs happens to be among them, which is the whole reason this operation exists rather than a general principle about wavelet trees.

The family is closed under differences, though, and that gives the middle case. A count over an interval $[c, d)$ is the prefix count at $d$ minus the prefix count at $c$: two descents, or $2\lceil\log_2\sigma\rceil$ bit-vector ranks. A loop over the same interval costs $(d-c)\lceil\log_2\sigma\rceil$, so the walk wins whenever the interval holds more than two symbols — which is nearly always, and is a saving nobody would notice was available.

So the test has three cases and each has a price.

A prefix of the alphabet — one walk, $\lceil\log_2\sigma\rceil$ operations, free alongside the rank the caller wanted anyway.

A union of $k$ intervals — $2k$ walks, and worth taking over the loop as soon as the intervals hold more than two symbols each.

An arbitrary set, or a property that is not about order at all — the loop is unavoidable, and the right response is a different traversal rather than a cleverer descent. Counting the distinct symbols in an interval is the standing example: distinctness is not a prefix property, no descent computes it, and the operation that does costs $O(d\log(\sigma/d))$ by walking every node the interval touches.

Which explains the three cases this page already lists without a rule between them. The smaller-symbol total is a prefix; the between-$c$-and-$d$ count is an interval; the arbitrary set is neither. The rule is the same one every time: ask whether the quantity is a prefix count in the order the structure sorts by, and if it is, the descent already computed it.

That also says why the identity turns up so often in a bit vector and so rarely elsewhere. A bit vector’s alphabet is two symbols, so every subset of it is a prefix or a complement of one, and the free count is total. A wavelet tree inherits the identity one level at a time and loses most of it, keeping exactly the prefix queries — which is every child at once’s operation and no more. Select is not rank backwards is the boundary from the other side: a query about where rather than how many is not a count over any subset, so no partition answers it and the machinery has to be built.

Where this sits in the strand #

Every child at once is the operation and what it saves. This page is why the saving is total rather than partial. The tree the operation insists on is what it costs, and a factor of fourteen, for four per cent puts both on one plate.

The structure underneath all four is the one the index that is smaller than the text builds, and the operation it reduces to is the one rank is the only thing it does is named for.

A last note on units #

This collection counts three things where a published account counts one, and this page is a good place to say why all three are kept.

Symbol ranks — what an account of backward search counts. Two per character of the pattern, and it is the right unit for describing what the algorithm does.

Bit-vector ranks — what a wavelet tree performs. The symbol rank times the code’s length, and it is the unit this page’s whole result lives in.

Memory accesses — what a machine performs. A bit-vector rank is a directory read, a word read and a popcount, so it is several, and this collection does not count them because the model here is operations rather than cycles.

Three units, each right for a different question, and the failure mode is always the same: a claim made in one and read in another. The unit of cost is not one is the theme, and it has now produced a factor of five between the first two units on the same operation.

Why the check is on the counter and not the clock #

One more note about method, because this collection makes the same choice everywhere and it is worth defending once.

The claim is that the compound walk performs no operation a plain rank does not. That could be checked by timing both and finding them equal, and timing would be the wrong instrument: two implementations performing the same operations can differ by a factor of two on wall-clock for reasons about layout and branch prediction, and two performing different numbers of operations can time identically when one of them is memory-bound.

An operation counter answers the question actually being asked. It is exact, it is reproducible on any machine, and it fails loudly if a future edit introduces a query where there was arithmetic.

What it cannot say is whether the saving is felt. That is a different question with a different instrument, and this collection’s cache work is where it lives — two counts disagree exists precisely because an operation count and a machine’s behaviour are two measurements that rank algorithms differently.

Here the two agree in direction and almost certainly in magnitude: one walk down a tree touches one directory entry per level and a loop over σ symbols touches σ of them, so the cache behaviour is better by about the same factor as the operation count. That is an argument rather than a measurement, and it is labelled as one.