A block, a class and an offset

The previous essay computed a ceiling: sixteen per cent, being the distance between a wavelet tree’s twelve bits a point and the 10.38 that log₂(z!) allows. This one builds the coding that gets closest to it and measures what the result is made of.

The coding #

Cut a bit vector into blocks. Replace each block by two numbers: its class, being how many ones it holds, and its offset, being which of the C(b, c) arrangements with that many ones it is.

The class needs ⌈log₂(b+1)⌉ bits whatever the block holds. The offset needs ⌈log₂ C(b, c)⌉, which is zero for a block of all ones or all zeros and largest for a balanced one — so a vector whose blocks are lopsided costs less than one whose blocks are half and half.

Summed over a whole vector, that is exactly the zero-order entropy of the blocks plus the class field. It is the coding the index that is smaller than the text uses to make a self-index compressed, and this collection has had it since the index field opened.

It is worth noticing what the coding is not. It is not a model of the data: it makes no prediction about what the next bit will be, and it does not adapt. It is a change of alphabet — the same information written as a pair of numbers instead of as a run of bits — chosen so that the pair is usually shorter.

That makes it the cleanest kind of compression to reason about. There is no training, no context, and no case where it does badly for a reason that has to be explained. Its size on a vector is a formula: the sum over blocks of a class field and a binomial width, and that formula can be evaluated without compressing anything.

Compression is prediction is the theme this collection files most of its coding under, and this coding is the exception that makes the theme visible: it predicts nothing, and its saving is bounded by the entropy of a block rather than by the entropy of the source.

What it takes off the grid #

The plain grid over 3,612 points is 51,600 bits. With this coding it is 47,668 — a saving of 7.6%.

That is above the sixteen-per-cent ceiling’s implied bound on the payload alone, and the reason is worth having: the coding takes something off the directory as well. A class-and-offset vector’s directory holds one class per block and one pointer per superblock, and at the block length used here that is cheaper than the two-level counter array a plain vector needs.

So the saving has two sources, and only one of them is about the data.

The control, which is most of the essay #

Run the same coding over a permutation of the same size drawn uniformly at random — no parse, no repetition, no correlation between the two orderings.

It saves 2.6%.

So of the 7.6 points the coding takes off the parse’s grid, five are the data and 2.6 are the coding. A quarter of the plate is a description of what class-and-offset coding does to any vector of this density, and it would be there if the grid held nothing but noise.

That distinction is the whole reason the control is drawn. A saving reported without one is a number that cannot be attributed, and the attribution is what a reader needs: five per cent is what building this grid over this collection is worth, and it is the number that would change on a different corpus.

Two savings that must not be added up #

It is tempting to read “7.6% off the grid, 2.6% of it available on noise” as though the second were an error term to be subtracted once. It is not quite that, and the difference matters if the number is going to be reused.

The 2.6% is what the coding takes off a uniform permutation, which is the hardest case. A permutation with some structure gets at least that much from the same mechanism — the class field is cheaper than a counter array regardless — and some more from its own imbalances. The two are not independent quantities laid end to end; they are one measurement and a control on it.

What the control licenses is the statement that most of the saving is the data. It does not license attributing exactly five points to structure, because on a different collection the split would be different in both directions.

Where the five points come from #

Not from the levels, which the previous essay showed are balanced by construction. From the nodes.

A level is half ones because a wavelet tree splits each node’s values at their midpoint and every value occurs once. But a level is a concatenation of many nodes, and an individual node is only half ones if its point count is even and its value range is fully occupied. A node holding seven points sends four one way and three the other; a node whose value range is 96 to 127 but which holds only points with values above 110 sends everything right.

Block coding sees those imbalances, because a block usually sits inside one node. The zero-order entropy of a block is below one even when the entropy of the whole level is one, and the sum of those small deficits over sixteen thousand blocks is the five points.

That also says where it is largest. The top levels have the fewest nodes, so their blocks straddle fewer boundaries and the imbalance they see is the imbalance of a large node. The bottom levels are thousands of two-point nodes and every block is a mixture of them, which averages to exactly half.

The select the vector did not have #

There is an implementation note here that turned into a real gap.

A compressed bit vector in this collection has always answered rank, and a rank is all an index needs: a backward search descends a wavelet tree and never comes back up. A grid does come back up — every reported point is lifted to its column by a select at each level — so the coding needed a select and did not have one.

Adding it is not difficult and it is not free either. The directory that makes rank cheap counts ones, and a select for zeros has to be answered by subtracting: the zeros before a block are its start minus its ones, so the search is over an expression rather than an array. That is the same asymmetry select is not rank backwards is about, met again one structure down.

A structure that has only ever been asked one question can be missing the other one entirely, and nothing reports it until something asks. This collection’s plain bit vector had the same gap until the grid strand needed it.

It is a small instance of a pattern this collection has hit three times now. The structure paid for before the first query records a grid whose first implementation stored a vector per node, which was correct and six times too large. The candidates a filter cannot avoid records a rectangle whose descent lost points at the last level because the single-value nodes were not created. Each of those was found by asking the structure a question it had not been asked before, and each was invisible until then.

What it costs to read #

The descent through a grid is ranks only, and in bits inspected the three codings are within a tenth of each other: 112,532 for the plain vector against 105,953 for this one, over sixty rectangles.

That is a surprise worth stating plainly. The compressed vector is not slower on the descent — it reads slightly less, because a rank over class-and-offset walks a class array of one small number per block where a plain rank scans the block’s bits.

What it does not do is answer a select as cheaply. Selects are where compressed vectors are expensive, and they are what a reported point costs — so a query returning many points pays for the coding and a query returning few does not.

What it comes to on the index #

The two grids are 102,972 bits of a 366,648-bit phrase index — 28% of the structure. Coded this way they are 81,799, which is 23.7%, and the index comes to 345,475.

5.8% off the whole structure, for a change confined to how eleven bit vectors are stored, with no change to any answer and no measurable change to the descent.

That is a real saving and it is not a large one. Whether it is worth having depends on what else is available, and the honest comparison is with the other things this collection has measured on the same index: a depth cap costs phrases and buys bounded reads; a different sampling rate trades locates against bits by a factor of thirty. Against those, five per cent is a rounding.

What this says about the deferral #

The deferral asked for a compressed grid on the grounds that a structured permutation has runs. This coding does not look at runs at all — it looks at how many ones a block holds — and it is the one that works.

That inversion is the useful result. The property the grid actually has is a slight imbalance in its nodes; the property the deferral named is a slight lengthening of its runs; and the coding that exploits the first is worth 7.6% while the coding that exploits the second is worth −17.8%.

Both properties are real and both are small. What separates them is what the coding charges for the property being absent: a class field costs a fixed few bits a block whether the block is lopsided or not, and a gamma-coded run length costs more than the run it replaces whenever the run is short. One degrades gracefully and the other does not.

The block length, which is a parameter nobody sweeps here #

One number was chosen and not tuned: the block length, at fifteen.

It matters in both directions. A shorter block means more classes, and the class field is paid per block whatever the block holds — at a block of four, the class costs three bits for four bits of payload and the coding is a loss on any vector. A longer block means fewer classes and a larger table of binomial widths, and the offsets grow because a longer block is more likely to be balanced.

The index that is smaller than the text swept it on a different structure and found an interior optimum, which is the expected shape. It is not swept here, and the reason is that this strand is comparing three codings rather than tuning one — a coding measured at its best block length against two measured at an arbitrary one would be measuring two things.

What the sweep would be worth is a deferral, and on the evidence from the index strand it is one or two points rather than five.

The block length is not arbitrary, and the sweep is worth more than a point #

Fifteen is not a round number and it is not a careless one, which the formula shows without any sweeping. The class field costs $\lceil\log_2(b+1)\rceil$ bits a block whatever the block holds, so a block one below a power of two is where that ceiling is tight: fifteen costs four bits, and sixteen costs five for one more bit of payload. Per bit of vector the class is 0.267 at $b = 15$ and 0.313 at $b = 16$ — seventeen per cent worse for being one longer.

That much recommends the choice. Evaluating the whole formula at a balanced block recommends changing it, and says by how much.

A block of fifteen holding seven ones has $\binom{15}{7} = 6{,}435$ arrangements, so its offset is thirteen bits. Add the four-bit class and the coding spends seventeen bits to store fifteen — a payload penalty of 13%. At $b = 31$ a balanced block is a 29-bit offset and a five-bit class, 34 bits for 31, a penalty of 9.7%. At $b = 63$ it is 60 and 6 for 63, 4.8%.

Two things fall out, and the first reframes the control.

On the payload alone this coding is a loss on any balanced vector, at every block length. So the 2.6% the control saves is not a small residual saving on the bits — it is the directory saving something larger than the payload loses. The decomposition the essay offers is right and the split is sharper than partly in each: at fifteen the payload is 13% against the coding on balanced data, and the class array is beating the two-level counter array by more than that.

And the penalty falls fast with the block length. Going from fifteen to thirty-one takes it from 13% to 9.7%, and to sixty-three from 9.7% to 4.8% — three and five points of payload, on a structure whose grids are 28% of the index. That is not one or two points; it is the same order as the whole result this strand reports.

The direction is unambiguous because both terms move the same way. A longer block has a proportionally smaller class field and a proportionally smaller offset — the offset’s saving against a raw block is about $\tfrac12\log_2 b$ bits however long the block is, so spreading it over more bits is pure gain. Nothing in the size arithmetic argues for a short block at all.

What argues for one is everything the size arithmetic does not count. A rank inside a block has to reconstruct the block from its class and offset, which is a walk of up to $b$ steps rather than a masked word; the binomial table is $O(b^2)$ entries; and an offset of sixty bits stops fitting in a machine word. The descent measurement above — 105,953 bits inspected against a plain vector’s 112,532 — is the number that would move, and it would move against the coding.

So the deferral is real and its shape is now known rather than guessed: the sweep is a size-against-decode trade with a monotone size axis, not a search for an interior optimum in size. The index that is smaller than the text found an interior optimum because its vectors are imbalanced, which puts a data-dependent term into the offset that this grid’s balanced levels do not have. On a grid, where the offsets are as expensive as they can be, the size curve has no interior optimum to find — which is a better reason to leave it at fifteen than the one given, and a worse one for believing the sweep is cheap. The runs a permutation does not leave is the other coding measured against the same balance, and it fails for the mirror-image reason.

Where else this coding is already in use #

It is worth pointing out that nothing about this coding is new to the collection, which is part of why it was the first thing tried.

The index that is smaller than the text uses it on the wavelet tree of a Burrows-Wheeler transform, where the vectors it codes are not balanced — a transform’s levels have whatever imbalance the text’s symbol frequencies produce — and there it is worth far more than seven per cent. The collection decides which index is small measures the same coding across five texts and finds its saving ordered exactly as the texts’ entropies are.

So the same object appears twice in this collection with two very different results, and the difference is entirely in what it is applied to. A transform’s vectors carry the text’s statistics; a grid’s vectors carry nothing but the tree’s own balance rule.

A compression technique has no size of its own, and quoting one — “class-and-offset coding saves a third” — is quoting a measurement about somebody else’s data.

What is checked, and what must fail #

Every coding answers every rectangle identically, as sorted lists of points rather than as counts.

Rank, select-one and select-zero agree with an honest scan on a deliberately clustered vector — clustered because the grid’s own levels are balanced, and a check that only ran on those would exercise none of the run machinery in the vector this coding is compared against.

And two things must fail. A size that omits the directory reports the run-coded vector 1.32 times smaller than it is; that ratio is the check. And a class array read as if it were the vector’s contents — the defect a compressed vector is most exposed to, since the classes are the only part a rank consults — is caught by the scan comparison at every seventh position.

What a reader deciding should weigh #

Two numbers, and neither of them is 7.6%.

Five per cent of the grid is what the collection’s own structure is worth. That is the number that would change on different data, and it is the number to re-measure before assuming this result transfers.

Five point eight per cent of the index is what the change buys. That is the number a reader is actually choosing about, and it is small enough that the decision is dominated by whether the coding costs anything else — which, on the descent, it does not, and on selects, it does.

The clean summary is that this is a change worth making if the vectors are already there and not worth building a strand around. The strand exists because the deferral asked a question, and the answer to a question is worth having even when the answer is “about five per cent”.

What this leaves #

A coding that works, is worth five points of data and 2.6 of encoding, and costs nothing on the descent.

The deferral asked for something else — a coding of the runs — and the runs a permutation does not leave is what happens when that is built. It is the essay in this strand where a measurement comes out in the opposite direction to the sentence that asked for it.