Rank is the only thing it does

Backward search spends two rank queries per character of the pattern and nothing else. A six-character pattern costs twelve, whatever the text, and the flatness of that number is the whole case for the structure.

It is also a number in a unit nobody has priced. A rank query is not one operation. It is a small structure being consulted, and the structure has parameters, and the parameters move both its size and its cost by more than an order of magnitude each.

Twelve symbol ranks in the search at the top of the previous essay became forty-four rank queries on bit vectors — or sixty, with one option changed. And each of those bit-vector ranks reads between three and eighteen machine words, according to another option.

What a rank directory is #

The question is: given a bit vector of $n$ bits, how many ones occur before position $i$?

Scanning is $\Theta(n)$ and useless. Storing an answer for every position is $n\lceil\log_2 n\rceil$ bits, which is sixteen times the vector. The standard construction is two levels of counter and a scan of what is left:

• every $s$ bits, a superblock counter holding an absolute count — $\lceil\log_2 (n+1)\rceil$ bits each, $\lceil n/s\rceil$ of them;
• every $b$ bits, a block counter holding a count relative to its superblock — $\lceil\log_2 (s+1)\rceil$ bits each, $\lceil n/b\rceil$ of them;
• and the remainder inside one block, counted by popcounting $\lceil b/w \rceil$ machine words.

Three reads and some popcounts, none of which depends on $n$. That is what “constant time” means and it is true.

What it does not say is that the two levels cost bits, that the number of bits depends on $b$ and $s$, and that the number of words to popcount depends on $b$ in the opposite direction.

A factor of fifty-four in space against a factor of six in reads, and every point on that plot satisfies “constant time and $o(n)$ extra space”.

The first three rows read the same number of words, because a block of eight, sixteen or thirty-two bits all fit in one thirty-two-bit word. That flat stretch is where the space is free to be bought, and it ends exactly at the word size — which is a parameter of the machine rather than of the algorithm, and is the reason the word size is printed on every plate that uses one.

Why the directory is two levels and not one #

One level would be simpler and it does not work, which is worth a paragraph because the reason is the same arithmetic that runs the rest of this page.

A single level of absolute counters every $b$ bits costs $\lceil\log_2(n+1)\rceil$ bits each. Over a vector of 65,536 bits at a block of 64 that is 1,025 counters of 17 bits — 17,425 bits, against the two-level structure’s 13,614. The saving comes from the second level being relative: a block counter only has to reach the number of ones in its superblock, so at a superblock of 4,096 it needs 13 bits rather than 17.

Four bits per block does not sound like much until it is multiplied by the number of blocks, which is the largest count in the structure. And the same argument goes one level further — a third level of counters relative to the block would shave another few bits each — and stops being worth it because each level costs an extra read on every query. Two is where the arithmetic settles for the sizes anybody uses, and it settles somewhere else for other sizes.

That is the shape of every decision on this page: a saving per element multiplied by a great many elements, against a cost per query multiplied by a great many queries, with the crossover depending on numbers nobody writes down.

Select is the harder one #

Rank has an inverse — where is the $k$-th one — and it is not symmetric with it.

Rank is a lookup: the position names which superblock and which block to read. Select is a search: the count names nothing to look at, so the directory has to be binary-searched, and the constant-time constructions for select are considerably more elaborate than the one above.

This collection’s structures use select in one place only — turning a marked row into an index into the sample array — and the implementation here searches rather than pretending otherwise. That is a stated limitation rather than a measurement: nothing on these pages compares select constructions, and a plate that counted selects as though they cost what ranks cost would be reporting a number belonging to neither.

From one bit vector to an alphabet #

A bit vector answers rank for a bit. The transform is over an alphabet of twenty-two symbols, and the search needs how many of this symbol before this row.

The counter-array answer is one array per symbol, which is sixty-six times the text. The structure that does it in one vector’s worth of space is a wavelet tree.

Give every symbol a binary code. The root holds one bit per character of the sequence, saying which side of the alphabet split that character falls on. Its left child holds the same for the characters that went left, its right child for those that went right, and so on until each leaf is a single symbol.

A rank for symbol $c$ walks $c$’s code from the root, one bit-vector rank per level, each one narrowing the range in the child. Nothing is ever compared with anything; each step is a rank on bits.

So the cost of one symbol rank is the length of that symbol’s code, and the total size is one bit per symbol per level, which is $n$ times the average code length.

Both of those are the same quantity, and that quantity has a name.

The entropy, as an operation count #

Shape the tree with fixed-length codes and every symbol’s code is $\lceil\log_2 \sigma\rceil$ bits. Shape it with Huffman codes — the same lengths a coder would assign — and each symbol’s code is about $-\log_2 p$ bits.

Measured over the transform of sixteen thousand characters of English-like text, twenty-two symbols:

The mean number of bit-vector rank queries one access performs is 3.944 against a zeroth-order entropy of 3.892. Within a bit, because a Huffman code is within a bit of the entropy and that is the only slack there is.

The same quantity that bounds what a coder may emit turns up here as the number of operations a query performs. Not as an analogy — as the same arithmetic, applied to the same code lengths, counted in a different unit.

The mean is not the worst #

The Huffman shape’s worst-case depth is eight where the balanced tree’s is five. A rank for a rare symbol costs 60% more than the balanced tree would charge, and a query is a sum over the pattern’s characters rather than an average over the alphabet.

That is the distribution-not-average point in a place it is easy to miss. A pattern of common characters beats the mean; a pattern of rare ones loses to the balanced tree outright. On the search measured earlier — a six-character pattern of ordinary letters — the ratio came out at 3.67 bit ranks per symbol rank, below the text’s own entropy, because the pattern is made of frequent symbols.

Where the shape stops helping #

A Huffman-shaped tree is not free of trouble, and two of its costs are worth naming beside its saving.

The shape has to be stored. Every symbol’s code length has to be somewhere, which is an alphabet-sized table, and the tree’s node structure has to be navigable. On twenty-two symbols that is a few hundred bits against seventy-seven thousand and it does not matter; on an alphabet of a hundred thousand — words rather than characters — it is no longer a footnote.

And the shape is fixed when the structure is laid out. A balanced tree over a known alphabet needs nothing measured; a Huffman-shaped one needs the symbol frequencies of the transform, which means one pass over it before the structure can be laid out. For a static index that is free, since the transform is computed anyway. For anything that grows, it is the same problem a static Huffman coder has: the shape is right for the text it was measured on and drifts as the text changes.

Neither cost changes any number above. Both are the reason the balanced shape is still what a general-purpose library ships.

Two counts, again #

There is a temptation to add the numbers up: 12 symbol ranks, 44 bit ranks, 44 × 3 words. It is worth resisting, and the reason is this site’s oldest theme.

A symbol rank, a bit-vector rank and a machine-word read are three different acts. The first is what the algorithm asks for; the second is what the structure performs; the third is what a machine touches. They are related by two multipliers, each of which depends on a parameter, and summing them produces a number that describes no level.

What this buys over the obvious structure #

It is worth putting the whole chain beside the thing it replaces, because the chain has a lot of parts and the alternative has none.

The counter-array index answers a symbol rank in one read. No tree, no levels, no directory, no popcount. It is the fastest structure on any of these plates and it will remain so.

It is 5,407,710 bits over sixteen thousand characters, against 36,804.

So the wavelet tree’s whole purpose is to convert a factor of a hundred and forty-seven in space into a factor of a few in time, and every parameter in this essay is a dial on that conversion. The mean depth decides how many bit ranks a symbol rank becomes; the block length decides how many words a bit rank touches and how much directory is carried; the shape decides whether the multiplier is the alphabet’s logarithm or the text’s entropy.

Four dials, and not one of them appears in the sentence “an FM-index searches in $O(m)$ time and $n H_k + o(n)$ space”. That sentence is true. It is also the sentence somebody reads before deciding whether the structure fits in the machine they have, and every number that decides the answer has been dropped from it.

The two ranks are one descent #

Backward search asks for $\mathrm{rank}_c(sp)$ and $\mathrm{rank}_c(ep)$ at every step — two ranks, same symbol, two positions. Counted as two symbol ranks they become two full descents of the wavelet tree, which is what the multiplier above assumes.

They need not be. The two queries name the same symbol, so they follow the same code, so they visit the same nodes in the same order. One descent carrying two positions performs two bit-vector ranks per node instead of one and visits each node once instead of twice.

The counted arithmetic is unchanged — forty-four bit ranks are still forty-four bit ranks — and everything else about the query improves. Half as many node lookups, half as many directory structures brought into play, and, on any machine with a memory hierarchy, two ranks on the same bit vector at two positions rather than the same pair spread across two separate walks. The second of a pair frequently lands in a superblock the first has already touched, which the counted model cannot see and a processor certainly can.

This is worth stating precisely because it is the kind of improvement the site’s own unit is blind to. The operation count does not move and the work does, so a plate counting bit-vector ranks would show the two implementations as identical, and the essay’s standing refusal to report durations means nothing here can say by how much they differ. What can be said exactly is the structural fact: the pair of ranks in every step of a backward search is a pair on one vector, and an implementation that computes them independently has thrown that away.

The same observation generalises to the interval as a whole. Every operation this family performs takes a range of rows rather than a row, so every rank in the search comes in pairs by construction — which means the pairing is not an optimisation for a special case but the normal shape of the workload.

A vector per node, or a vector per level #

The tree above has one bit vector per internal node, and over twenty-two symbols that is twenty-one vectors of steadily decreasing length. Each of them needs its own directory, and a directory has a floor: at least one superblock counter, at least one block counter, whatever the vector’s length.

On this alphabet that floor is invisible. On an alphabet of a hundred thousand — words rather than characters, which is a real way to build one of these — it is not. Such a tree has a hundred thousand internal nodes, the deepest of which hold a handful of bits each, and a directory costing tens of bits over a vector of nine is overhead of several hundred per cent. The structure whose whole justification is that it is smaller than the alternative has spent its saving on bookkeeping about vectors too short to need any.

The standard repair changes the layout rather than the algorithm. Instead of one vector per node, keep one vector per level: the concatenation, in order, of every node’s vector at that depth. There are $\lceil \log_2 \sigma \rceil$ of them, each exactly $n$ bits, and each needs exactly one directory. A hundred thousand tiny vectors become seventeen large ones.

Navigation survives the rearrangement because the mapping is arithmetic. A node at a level occupies a contiguous stretch of that level’s vector, and where the stretch begins is recoverable from a per-level count of zeros plus the ranks already computed on the way down — so a descent is still one bit-vector rank per level, on a vector that happens to be shared.

Two things about that are worth having beyond the structure itself.

The payload is identical. The same bits in the same order, regrouped; nothing is compressed differently and no query answers differently. What changed is the number of directories, from $\sigma - 1$ to $\log_2 \sigma$, and that is a change to a term the size formula in every description of this structure leaves out.

And it is another instance of the essay’s own complaint. “One bit per symbol per level” is a true description of both layouts, it is the sentence everybody writes, and on a large alphabet the two structures it describes differ enormously in size. The bits it counts are the bits nobody was worried about.

What is deliberately not measured #

Three things, and each of them would change the constants without changing anything above.

Broadword tricks. A real rank implementation counts the bits of a word with a handful of multiplies and shifts rather than a loop, and the good ones interleave the directory with the payload so that one cache line holds both. Those change what a “read” costs by a large factor. Nothing here models a cache line or an instruction, so nothing here can say by how much.

Compressed vectors’ rank. The class-and-offset vectors of the compressed index answer rank by decoding rather than popcounting, which is more work per query. Both are charged one rank here, which is the right unit for comparing an index against a suffix array and the wrong one for comparing plain against compressed — and the essay that compares them says so rather than borrowing this one’s unit.

Select constructions. Named above and not built.

Naming those three is not throat-clearing. Each one is a place where somebody could reasonably say the numbers here understate or overstate a real implementation, and the honest position is that they would be right and that this collection has no measurement to offer either way. A figure showing a rank at some number of nanoseconds would be a figure about one machine on one day, which is the thing the counting field opened by refusing to produce.

What is measured is exact, reproducible and machine-independent: how many rank queries a search performs, how many bit-vector ranks each of those becomes, how many words each of those touches under a stated word size, and how many bits the directories that make it possible occupy. Four numbers, four parameters, and a phrase — “constant time and $o(n)$ extra space” — that is true of every combination of them and names none.