The index that is smaller than the text

Build the index from the last essay over five different texts of sixteen thousand characters each and weigh it. Two of the five are English-like over the same twenty-one symbols; one of them is a text that repeats itself with occasional mutations, so its third-order entropy is 0.234 bits a character, and the other is ordinary prose at 0.975 — four times as much structure in the first as in the second.

The index is 6.29 bits a character on the first and 6.16 on the second.

A gap of two per cent, across a fourfold difference in how compressible the texts are. Whatever this structure is doing, it is not exploiting the thing the transform was introduced to expose.

Why not, in one sentence #

The transform is a permutation. It outputs exactly the characters it was given in a different order, which is how the compression field measured it — the zeroth-order entropy of the output is identical to the input’s to fifteen decimal places, and by that measure the transform does nothing at all.

A wavelet tree built of plain bit vectors costs the zeroth-order entropy of what it holds, near enough: each symbol contributes one bit per level of its code, the Huffman-shaped codes are within a bit of the entropy, so the whole tree is about $n H_0$ bits.

Put those two sentences together. $H_0$ of the transform equals $H_0$ of the text; the tree costs $n H_0$ of the transform; therefore the index costs $n H_0$ of the text, and no amount of order-3 structure in the text can change it, because the transform threw the order away when it rearranged the symbols and $H_0$ never knew about it in the first place.

The order is not gone. It is sitting in the output in a different form: as runs. A text where th is usually followed by e produces, in the transform, a stretch of the last column that is mostly t. That is what the transform converts context into, and it is exactly what a structure charging one bit per bit cannot see.

Class and offset #

The repair is to store the bit vectors in a form whose size depends on their contents.

Cut a vector into blocks of $b$ bits. For each block store two things:

• its class — the number of ones in it — which takes $\lceil \log_2 (b+1) \rceil$ bits;
• its offset — which of the $\binom{b}{\text{class}}$ blocks with that many ones it happens to be — which takes $\lceil \log_2 \binom{b}{\text{class}} \rceil$ bits.

The second number is the whole idea. An all-zeros block has $\binom{b}{0} = 1$ possibility and costs zero bits of offset. So does an all-ones block. A block that is half ones costs nearly $b$ bits, which is nothing saved, and that is honest: a balanced block genuinely carries a bit of information per bit.

A run therefore costs almost nothing and a coin-flip sequence costs everything. Which is precisely the property needed, because runs are what the transform produces.

What a run is worth, exactly #

The arithmetic is small enough to do by hand on one block, and doing it is what makes the mechanism concrete rather than plausible.

Take a block of fifteen bits. If it is all zeros, its class is 0 and $\binom{15}{0} = 1$, so the offset needs zero bits and the block costs four bits of class and nothing else — a fifteen-to-four saving. If it has one bit set, $\binom{15}{1} = 15$ and the offset needs four bits, so the block costs eight. Two bits set: $\binom{15}{2} = 105$, seven bits of offset, eleven in total. And at seven or eight bits set, $\binom{15}{7} = 6435$, thirteen bits of offset, seventeen in total — more than the fifteen bits it replaced.

That last case is why the compressed index over an incompressible text is larger than the plain one, which the five-text table below shows without apology. The encoding is not a compressor with a floor of zero; it is an encoding whose cost tracks the entropy of the block classes, and on a sequence of balanced blocks that entropy is the whole thing plus a class array.

The whole structure is that arithmetic repeated over every node of the wavelet tree, and the reason the transform matters is that it makes the blocks unbalanced.

Measured, on five texts #

Sort the table by $H_0$ and the fourth column is in order. Sort it by $H_3$ and the fifth column is in order. Neither is a coincidence and both are asserted on every build — including the third statement, which is that the plain index does not follow $H_3$, because a check that only confirmed the two positive claims would pass an implementation in which the compression had quietly stopped working.

The first and third rows are the pair to look at. Same alphabet, nearly the same $H_0$, four times the difference in $H_3$: 6.29 against 6.16 plain, and 1.48 against 2.25 compressed.

The block length is a number somebody types #

The block cannot be very short, because every block costs a class whatever is in it. It cannot be very long, because $\lceil\log_2\binom{b}{c}\rceil$ approaches $b$ as the block lengthens and a long block is rarely uniform.

So there is an interior minimum, and it is not where the textbook parameter suggests.

The default here is sixty-three, and it is sixty-three because that sweep says so rather than because it is a round number. It is worth being explicit that this makes the plates on this page tuned: a compressed index reported at the wrong block length is off by up to 65%, which is larger than most of the differences anybody argues about, and a size quoted without its block length is not reproducible.

One implementation detail is worth a sentence because it nearly went wrong. At a block of sixty-three the middle binomial is $\binom{63}{31} \approx 9.16 \times 10^{17}$, which is past what a double-precision float holds exactly. That number is the payload of the structure, so computing it approximately would mean computing the index’s size approximately. The binomials here are exact integers of arbitrary precision, and the bit widths are read off their binary representations.

Half the index is bookkeeping, and the block length decides how much #

Here is the finding this essay would rather not have.

The standard statement about a compressed self-index is that it occupies $n H_k + o(n)$ bits. Both halves of that are true of the structure measured here. The question is what the second half weighs, and the answer depends on a number in a header.

At the block length the sweep chose, on English-like text:

Two things in the last row.

The payload behaves better than advertised. At a quarter of a million characters it is 0.89 bits a character against an $H_3$ of 0.995 — under the floor it is supposed to approach. That is not a contradiction: $H_3$ is a floor for a coder that conditions on three preceding symbols, and the class-and-offset encoding of the transform’s runs is not one. It conditions on however much context the run it sits in was produced by, which on this text is more than three symbols’ worth.

And the index is twice the payload. Directory 30%, sampled positions 16%, sample marks 3%, the $C$ table a rounding error — half of the structure is accounting, and the accounting does not shrink when the text becomes compressible.

Run the same sweep at the block length the textbook parameter suggests, fifteen, and the split moves a long way:

The payload is smaller — shorter blocks are more often uniform — and the directory is nearly three times larger, because there are four times as many blocks each needing a class. Net, the index is bigger. At one block length a quarter of the structure is bookkeeping and at another three-fifths of it is, and the choice between them is one integer.

Both directories are $o(n)$ in the sense the notation means: the rate is $\Theta(n \log\log n / \log n)$, which does go to zero relative to $n$. It goes there through eleven decades of nobody’s data. This is a fourth instance of the shape what O-notation does not say collects, and the sharpest of them, because the discarded term is not merely non-negligible — at the parameter most descriptions imply, it is the majority of the object.

What “smaller than the text” means #

The claim in this essay’s title is now measurable, and it is measurable in at least five ways — which is the difficulty rather than an incidental detail. The text is not one quantity: it is the file on disk, the same characters packed into as many bits as the alphabet needs, and three different entropies each computed under a different model of what a character depends on. An index can be smaller than some of those and larger than others at the same moment, and it is.

On English-like text at sixteen thousand characters the compressed index is 2.25 bits per character. So:

• smaller than the file (8 bits/char) by 3.6 times — true;
• smaller than the packed text (5 bits/char) by 2.2 times — true;
• smaller than $n H_0$ (3.89) — true;
• larger than $n H_1$ (2.24), by a hair;
• larger than $n H_3$ (0.975) by 2.3 times.

Every one of those is correct. A claim of “smaller than the text” that does not say which is a claim about nothing, and the honest form of the sentence is the last three lines together: the index is smaller than the text at any encoding a person would actually store it in, and larger than the entropy it is named after.

Both integers, then, are in a header somewhere, neither appears in any description of the structure, and between them they move the index by more than a factor of two in size and by an unbounded factor in locate time. A reported index size is a point in that two-dimensional space and not a property of the algorithm, which is the same complaint this collection makes about every constant it has had to go and measure.

What is not measured here #

Two things, and both would move the numbers.

Query cost. A compressed vector’s rank is not free — it reads a class, decodes an offset and counts within a block, where a plain vector reads a directory entry and popcounts. The structures here are counted in rank queries, which charges both the same, and that is the right unit for comparing an index against a suffix array and the wrong unit for comparing plain against compressed. Nothing on this page says the compressed index is as fast; it says it is smaller, and it says so in bits.

Run-length encoding the transform directly. Storing the transform as (symbol, run length) pairs is the other route to the same structure, gets closer to the run-length entropy, and is what the indexes built for highly repetitive collections actually do. It is a different structure with a different rank mechanism and it is not built here — so this collection has no measurement of it, and quoting one would be quoting.

The part of the index that does not compress #

The two tables above are usually read as a warning about a badly chosen block length. They say something stronger, and it survives every choice of block length: there is a term in this structure that does not know what text it is indexing, and below it no amount of compressibility helps.

Sort the index into the parts that depend on the text and the parts that do not.

The payload — the offsets — is the only part that reads the data. It falls with the runs, it fell to 0.51 bits a character on the text that repeats itself, and at a quarter of a million characters of the same source it fell to 0.10. Nothing here is a floor; a more repetitive text makes it smaller without limit.

The class array is a function of the number of blocks, which is a function of the text’s length and the block length and nothing else. The superblock directory is the same. The sample marks are one bit per sampled row. The sampled positions are $\lceil\log_2 n\rceil$ bits each, times however many rows are sampled. Not one of those four consults a single character of the text.

So the structure has an asymptote. On English-like text at the tuned block length the accounting is a quarter of the index and looks like overhead; on the repetitive text it is nine-tenths of it and is the index. The reason is not that the accounting grew — it is identical in both cases — but that the thing it was accounting for went away.

That reframes the title’s claim once more. The index is smaller than the text, and how much smaller has a ceiling that is set by the bookkeeping rather than by the entropy: past a certain compressibility, indexing a more repetitive text produces an index of nearly the same size. A collection of a thousand near-identical genomes does not index a thousand times more cheaply than one genome; it indexes at the rate its directories charge.

This is exactly the gap the run-length route named at the end of the previous section is built to close, and it closes it by attacking the right term. Storing the transform as runs makes the number of blocks fall with the runs rather than with the length, so the accounting shrinks alongside the payload instead of sitting underneath it. That is a different structure and it is not built here — but the reason it exists is legible from these tables alone, which is worth more than a quoted figure would be.

The sample rate is the other integer #

The block length is the parameter this essay swept. There is a second one in the same structure and it is doing something quite different, so it is worth separating them before either is defended.

A backward search returns a range of rows, not positions in the text. Turning a row into a position means walking backwards through the transform until a row is reached whose position was stored, and the sampling rate $s$ decides how many are stored: one row in $s$, at $\lceil\log_2 n\rceil$ bits each, plus a bit vector marking which.

Both halves move with $1/s$. Halving the rate halves that part of the index and doubles the expected number of steps a locate performs, and the expected walk is about $s/2$ steps because a row is on average half a sample away from one. So this dial trades index size against query time, where the block length traded index size against index size. They look alike in a size table and they are not comparable at all: one has an interior optimum that a sweep can find, and the other has no optimum, only a rate at which a reader is prepared to wait.

That is why the sweep in this essay holds the sampling fixed. A size quoted with the sampling rate left out is not merely unreproducible in the way a block length left out is — it is a size that can be made arbitrarily small by making locates arbitrarily slow, down to the limit where nothing is sampled and every occurrence costs a walk the length of the text.

The counting rows in the tables here are unaffected by any of this, and that is the cleanest way to see the split. Counting how many times a pattern occurs needs the transform and its rank structure and no samples whatever, which is why the text does not have to be kept is a statement about counting and why locating is where an index starts paying rent again. A structure sized for counting and then asked to locate is the shape of a great many disappointing benchmarks.

The sentence to keep #

The transform emits nothing, compresses nothing, and changes no symbol’s frequency. Every measurement in the compression field said so.

What it does is convert context into adjacency, and whether that is worth anything depends entirely on whether the structure reading it charges by the bit or by the block. Plain vectors charge by the bit and see nothing. Class-and-offset vectors charge by the block and see everything, at 1.48 bits a character on a text whose third-order entropy is 0.234.

The transform did not become useful. The thing reading it did.