Two bits a value, and what undoes them

A structure quoted at “2n + o(n) bits” is quoted at its payload. The second term is the subject of this essay, and on every size drawn here it is several times the first.

The shape a range question is about got as far as a sequence of 2n parentheses and a rule for reading an answer out of it. The rule needs two things the sequence does not provide: a way to get from an array index to its own parenthesis, and a way to find the lowest excess between two points without walking the whole range. Both are structures, both cost bits, and one of them is where the encoding choice from the previous essay stops being a curiosity.

The bill #

Over sixty-five thousand values the parentheses are 131,072 bits. The rest comes to 651,800, so the whole structure is 782,872 — five times its own payload.

That is not a scandal and it is not an implementation failure. It is what o(n) looks like at a size anybody runs. A term that grows more slowly than n is eventually smaller than n; sixty-five thousand is nowhere near eventually. An index larger than what it indexes made the same observation about a self-index and it holds here with a different constant: the asymptotic statement is true, the structure is smaller than what it replaces, and the ratio it is smaller by is not the ratio the notation suggests.

The comparison that matters is with the segment tree the document listing was measured against, which is 2n values of ⌈log₂ n⌉ bits — 2,228,224 at this size. The succinct structure is 2.85 times smaller, which is a real saving worth building for. It is not the seventeenfold saving 2n against 2n⌈log₂ n⌉ invites.

It is worth putting that ratio beside the one the strand it serves already has. An index larger than what it indexes measured a plain suffix array at nearly four times its own text, and a compressed index at a fraction of it; the interesting number in both cases was never the leading term. The same is true here, and this strand differs only in that the leading term is small enough to be quoted as the whole thing.

The map, which is where the encoding choice lands #

The rule needs, given index i, the position of i’s opening parenthesis. There are two ways to have it.

Write it down. An array of n entries, each a position in a sequence of 2n, is n⌈log₂ 2n⌉ bits. At this size that is 1,114,112 — eight and a half times the payload, and half the segment tree, spent on the one part of the structure nobody quotes.

Compute it. If the openings are in index order — which is exactly what the stack construction gives and what an Euler tour does not — then index i’s opening is the (i+1)-th one, and finding the k-th one is a select. Support for that over the same sequence is 115,712 bits.

A factor of 9.6, from a decision about what order to write the parentheses in. Both encodings are correct. Both give a balanced sequence of exactly 2n bits. One of them makes the structure 782,872 bits and the other makes it 1,781,272, which is only 1.25 times smaller than the segment tree it was supposed to replace.

This is why the previous essay spent a section on which order the pushes happen in. The whole of the difference between “a succinct range minimum” and “a segment tree with extra steps” is that one line.

What select support costs, and why it is not free either #

Support for finding the k-th one in a bit vector is a structure in its own right, and select is not rank backwards is the essay that prices it. The short version is that rank’s directory is indexed by position and select’s answers are indexed by rank, and the ones are not evenly spaced — so a fixed block length bounds one and bounds nothing about the other.

Here the vector is half ones by construction: a balanced parenthesis sequence has exactly n of each. That is the easy case for select support, and it is worth saying so, because the same support over a sparse vector costs more per one rather than less. The 115,712 bits is a structure operating in its best regime.

There is a second reason the parenthesis sequence is a kind vector to support: its ones are spread evenly. A run of a thousand closings cannot happen — the excess would go negative — so the gaps between ones are bounded by the tree’s height, and the sparse case that costs select support most of its bits never arises. That is a property of what the vector is, not of the data it came from, and it is the sort of thing worth checking rather than assuming, because a vector with the same density and clustered ones costs measurably more.

The other term: two layers of blocking #

The rule’s second need is the lowest excess between two positions, and answering it without walking is a second structure.

The excess is cut into blocks of about half a logarithm. A block’s minimum is stored; a table over the block minima answers any span of whole blocks. That is the classical construction, and the table that fits inside a block is about the part inside a block. This essay is about the part above it, because that is where a second surprise lives.

One layer of blocking is not o(n). A table over every block, answering any span of them in constant time, has (N/b)·log₂(N/b) entries of ⌈log₂ N⌉ bits. At the block length that keeps the in-block table small, that comes to 3,605,987 bits at this size — larger than the segment tree the whole structure was replacing, by a factor of 1.6.

That is not a subtle point and it is routinely elided. The structure described as “linear space” is linear in words, and a word is a logarithm of bits. On an array of machine integers that distinction is invisible, because the input is words too. On a structure whose whole claim is that it holds two bits a value, it is the difference between a claim and its opposite.

The second layer #

The fix is a second level of grouping. Blocks are gathered into superblocks of about a logarithm of them; a table over the superblock minima answers spans of whole superblocks, and a table over the blocks inside one superblock answers the rest — with its entries being offsets within a superblock rather than positions in the whole sequence, so each is a logarithm of a logarithm rather than a logarithm of n.

Every term is then o(N), and the measured overhead falls from 3,605,987 to 651,800: a factor of 5.5, for a query that touches about twice as many tables.

Both versions are exact, both are constant-time, and the choice between them is bits against lookups with nothing else in it. That is the cleanest trade in this strand and it is the one nobody is offered, because the one-layer version is what gets described and the two-layer version is what gets shipped.

It is also the reason this collection reports both. A structure that is smaller and slower and a structure that is larger and faster are two answers to a question the reader is asking, and printing only the one that flatters the strand’s argument would be the constant the notation drops committed on purpose.

The table that belongs to nobody #

One term is reported separately and deliberately not summed into the total: the in-block lookup table.

It is indexed by a block’s bit pattern, so it depends on the block length and on nothing else. Two range minima with the same block length share it; a collection holding a hundred of them pays for it once. At the block length used here it is nine thousand four hundred and eight bits — a real cost, and one that is charged to the wrong structure if it is charged to any single one of them.

Reporting it inside the total would make a lone structure look worse than it is and a hundred structures look nine hundred times worse than they are. Reporting it not at all would let the phrase “constant time” be bought with an exponential table nobody mentions, which is the exact shape of the error the operations a candidate count leaves out records for a different structure. So it is printed beside every total and summed into none of them.

What this changes about the thing it was built for #

The document listing holds five parts: the suffix array, the text, the document array, the chain of previous occurrences, and the range minimum over the chain. The first two answer where; the last three answer which.

With a segment tree those last three come to 2.40 times the first two. That number is why the essay that measured it called the listing apparatus “the largest single structure in the strand and the one least like its published form”.

With the succinct structure they come to 1.47 times. The range minimum itself falls from 62% of the listing apparatus to about a third of it, and the chain and the document array — neither of which this strand touches — become the larger half.

That is the difference between a structure a reader would think twice about bolting on and one they would simply build. It is also the point at which the interesting question moves elsewhere: the chain is n⌈log₂ n⌉ bits and nothing here makes it smaller.

What a size like this is checked against #

Every number above is computed from a structure’s shape rather than from what a language allocates, which is this collection’s rule everywhere and matters more here than usual: a bit vector held as one byte per bit would report eight times these figures and answer every query identically.

Three checks stand behind the numbers.

The parts must sum to the total, and the total must be what is compared. A size that omits a directory is the shape of every over-claimed compression figure in this collection, and the structure paid for before the first query records what it did to a different structure’s headline.

Both encodings must answer identically. The select-mapped and array-mapped structures are run against the segment tree on four hundred random ranges and required to return the same position — not merely the same value, since a tie makes those different claims.

And the shared table must be shared. Two structures of the same block length are built and required to report the same shared figure and to be holding the same table object. A per-structure table would be correct and would make the o(n) claim false, silently, at exactly the sizes where the exponential in the block length starts to bite.

Where the remaining bits actually are #

It is worth breaking the 651,800 down, because the shape of it is not what the words “block minima” suggest.

The superblock minima and the table over them are small — a few tens of thousands of bits between them, because there are only about a thousand superblocks. The block minima are 147,000: one entry per block, and there are sixteen thousand blocks, each entry an offset inside its superblock rather than a position in the whole sequence.

The largest single term is the tables inside the superblocks — a table over each superblock’s blocks, at 409,000 bits, which is 63% of all the overhead. Each of its entries is small, and there are a great many of them: one per block per level of the within-superblock table.

That is the term a further layer would attack, and the reason there is not one here is that the returns fall off sharply. A third layer would replace log log N entries per block with log log log N, which at any size that exists is the difference between five and three. The published structures instead attack it from a different direction — by giving up the block minima entirely and answering within a superblock from the parenthesis sequence itself — and that is a different structure rather than a further layer.

The other thing that breakdown makes visible is how little of the overhead has anything to do with the range minimum. The select support is a sixth of it, and select support is the price of the encoding rather than of the query. Take the map away — pretend for a moment that an index arrives with its parenthesis position already known — and the structure is 667,160 bits, of which 131,072 is payload. The question this structure answers costs about four times its own payload to be able to answer; the question of where to start asking costs the rest.

How the last sixty-three per cent is removed #

The breakdown ends by naming the within-superblock tables as 63% of all the overhead and saying that the published structures attack it from a different direction. That direction is worth setting out, because it is the same move this collection has already measured in a completely different subject.

The tables exist so that a span of blocks inside one superblock can be answered without looking at the parentheses. Remove them and the query has to find the lowest excess in that span by reading the parenthesis sequence directly — which sounds like giving up the constant-time guarantee and is not, provided the span is short enough.

Choose the superblock so that it spans a number of parentheses that fits in a machine word. Then the whole span is one load, and the lowest excess within it is computed by a fixed sequence of word operations — the running excess of a bit pattern is a prefix sum of ±1, and a prefix sum over a word’s worth of bits is a handful of shifts, masks and a population count. A bounded number of word operations is a constant, and it is a constant with no table behind it.

That is the column computed in machine words arriving in a structure that has nothing to do with strings: a per-element loop replaced by a fixed number of operations on a register, with the register’s width setting how much can be replaced. The two cases even fail the same way — the technique works while the object fits in a word and steps to a second word when it does not.

Three consequences are worth having.

The bits genuinely go. Sixty-three per cent of the overhead is a table that a word operation replaces, so the structure drops from five times its payload to under two — which is the difference between an accounting curiosity and a structure that is nearly what it is quoted as.

The constant moves onto an axis this collection does not measure. A table lookup and a sequence of shifts are both “constant time” and are not the same constant, and which is faster depends on the same cache-against-arithmetic ratio that decided every other trade of this shape here. What can be said is that the table is bits and the word operations are not.

And it explains why the two-layer structure is what gets described. The version with tables is the one that can be analysed by counting entries; the version with word tricks needs a word size in the statement, which is a parameter an asymptotic result would rather not have. The published bound describes the analysable structure and the shipped code is the other one, which is the same gap the threshold somebody chose records between a pseudocode and a library.

The number to carry #

2.85 times smaller than a segment tree, and five times its own payload. Both halves of that sentence are the essay.

The first half is why the structure is worth building, and where a crossing moved to is what it does to the method it was built for. The second half is why “2n + o(n)” should be read as a statement about a limit rather than as a size — and why every plate in this strand draws the payload and the overhead as separate bars.