A bit for every bit

A deferral, recorded in one sentence: a permutation with structure has bit vectors with runs, and the plain vectors here charge one bit per bit.

The sentence is right about the runs and wrong about what follows, and this is the first of four essays working out why. It starts by asking what there is to take.

What the grid holds #

A rectangle over a permutation built it: the phrase boundaries of a parse have two orderings — by the text before them and by the text after — and a boundary’s pair of ranks is a point. Two orderings of one set is a permutation, and a permutation is the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.

On the collection this strand measures, that is 3,612 points, 12 levels, and 43,344 bits of payload — twelve bits a point, which is ⌈log₂ z⌉ as promised. The rank directories that make those bits answerable add 8,256, for 51,600 in total.

Those two numbers are the subject of the four essays. What can be taken off the first, and what happens to the second in the attempt.

The floor, which is computable exactly #

There are z! permutations of z things, so distinguishing one from another needs at least log₂(z!) bits. That number is not an estimate: for 3,612 points it is 37,485 bits, or 10.38 a point.

The grid’s payload is 43,344, which is 1.156 times the floor. Including the directory it is 1.377 times.

So the whole of what any compression scheme can win on the payload — over a permutation with no structure, over a permutation with all the structure in the world, over any permutation whatever — is sixteen per cent. The deferral asked for a compressed grid on the grounds that the vectors have runs. They do. There is not much room for them to be worth anything.

This is there is a floor applied to a structure rather than to an algorithm, and it is the cleanest instance of it in the collection: the floor is exact, the measurement is exact, and the distance between them is one number.

It is worth being precise about what the floor is a floor on. It bounds any structure that can distinguish one permutation from another — that is, any structure from which the permutation could in principle be recovered. The grid is such a structure: the wavelet tree’s levels determine the permutation exactly, which is why it can answer where every point is.

A structure that answered only counts — how many points are in this rectangle, never which — would not be bound by it, and could in principle be smaller. That is a real alternative and it is not what this strand is about, because the phrase index needs the points themselves: a rectangle’s answer is a list of phrase boundaries to propagate from, and a count of them is useless.

So the floor applies, it is exact, and it is 10.38 bits a point against the twelve the structure spends.

Where the sixteen per cent is #

⌈log₂ z⌉ per point is twelve bits and log₂(z!)/z is 10.38, and the gap has two causes worth separating.

The first is rounding. log₂ 3612 is 11.82 and the tree has twelve levels, because a level is an integer. That is 0.18 bits a point, or 1.5% of the payload, and no coding scheme recovers it — it is the cost of a balanced binary decomposition on a set whose size is not a power of two.

The second is Stirling’s term. log₂(z!) is z log₂ z − z log₂ e, and that second piece is 1.44 bits a point — 12% of the payload. It is the information a tree spends saying where the points are within each node, in a form that assumes every arrangement is equally likely.

Neither of those has anything to do with the data. A permutation drawn uniformly at random has exactly the same two gaps, which is what the plate above shows: the uniform control’s plain vectors are 51,600 bits too, to the last bit, because a wavelet tree over any permutation of 3,612 points is twelve levels of 3,612 bits.

Every level is half ones, by construction #

Here is why zero-order compression has almost nothing to work with, and it is a property of the tree rather than of the data.

A wavelet tree splits each node’s value range at its midpoint. A node covering values 0 to 63 sends the points whose value is at most 31 left and the rest right, and on a permutation every value occurs exactly once — so a node holding 64 points sends exactly 32 each way.

The number of ones in a level is therefore fixed by the shape of the tree, not by the data. Measured across the twelve levels: the zero-order entropy runs from 0.987 to 1.000 bits a bit, and the uniform control gives the same figures.

A coder that compresses to zero-order entropy is being handed the one input it cannot help. What little it does gain comes from the imbalance of individual nodes — a node holding an odd number of points, or a node whose value range is not fully occupied — and a block, a class and an offset measures that at a few per cent.

Why the vectors were expected to have runs #

The deferral’s reasoning was reasonable and it is worth reconstructing, because the place it fails is not where one would look.

The two orderings of the phrase boundaries are correlated. A repetitive text’s phrases are copies of earlier phrases, so a boundary and the boundary it copies from have similar text before and similar text after — so they sit near each other in both orderings, and the permutation should be close to the identity in patches.

A permutation close to the identity has a level-zero vector with long runs: the first half of the points have small values and go left, the second half go right.

That is all correct. What it misses is that a wavelet tree reorders its points at every level. Level zero is the points in x order; level one is the points in x order within each of the two halves, which means the left half’s points have been gathered together and the right half’s after them. Whatever locality x and y shared is used up at level zero and destroyed for every level below it.

Measured: the mean run over the parse’s grid is 2.34 and a uniform permutation’s is 1.90. Longer, by 23%, which is the structure showing through — and a run coder needs a mean run of about six to break even, which the runs a permutation does not leave works out and measures.

What the reordering costs, seen once #

The clearest way to see the destruction is to compare the top level with the bottom.

Level zero splits all 3,612 points by whether their y value is in the lower or upper half, in x order. Its mean run is 2.05 — barely above chance, and already most of the structure is gone, because the correlation between x and y is loose enough that adjacent boundaries frequently fall on opposite sides of the midpoint.

Level eleven splits pairs of adjacent values within nodes of two points each. Its mean run is 1.33, which is very close to the 1.25 a fair coin gives — half the runs are of length one, a quarter of length two. There is nothing there at all, and there are 3,612 bits of it.

Six of the twelve levels are in the bottom half of the tree and hold half the payload, and every one of them is indistinguishable from noise. That is the arithmetic behind every result in the three essays that follow.

The directory, which does not shrink #

8,256 bits of the 51,600 are rank directories: 688 per level, being the two-level counters that turn a bit vector into a structure with a rank.

That number is a function of the vector’s length and of the block and superblock lengths, and of nothing else. Compress the payload by half and the directory is unchanged; compress it by a factor of thirty and the directory is most of what is left.

This is the shape of every over-claimed compression figure in this collection, and it has bitten this exact strand before. The structure paid for before the first query records the grid’s first implementation, which stored a bit vector per node rather than per level: the payload was identical and the structure came to 10,094 bits over a 7,644-bit index, six times its own payload, all of it directory floors that do not shrink with the vector.

What the grid costs the index #

It is worth keeping the target in view. The two grids together are 102,972 bits on a phrase index of 366,648 — 28% of the whole structure.

So even a compression scheme that took the theoretical maximum off the payload would take about 16% of 28%, which is four and a half per cent of the index. That is the ceiling on the whole idea, computed before anything is built, and it is worth having computed because it sets what “worth doing” would mean.

The measured answer, three essays from here, is 5.8% of the index — which is above that ceiling, and the reason is that the block coding also takes something off the directory by storing block classes more cheaply than block contents. That is a real effect and it is not what the deferral was about.

Two grids, and only one of them is a permutation #

There is an exception in the structure worth naming, because it is the one place a different answer might live.

A rectangle over a permutation built two grids. The first is the intersection grid, which is a permutation and is everything above. The second is the propagation grid — a phrase’s source against the end of its source — and its point set is not a permutation: several phrases can copy from the same region, and the y coordinates are ranks among the ends rather than a relabelling of the x coordinates.

In practice this collection builds it over a rank space too, so it is a permutation again by construction, and everything above applies. But a grid over a genuinely repeated point set would have a lower floor — the entropy of a multiset is below that of a permutation — and that is the one shape in this strand where a compressed representation has more than sixteen per cent to work with.

Nothing here builds it, and it is recorded as the deferral it is.

What a permutation is, as an object to compress #

There is a general point here that outlives this strand.

A permutation is the extremal case for a compressor. Every value occurs exactly once, so there are no frequencies to exploit; the zero-order entropy of any sensible encoding of it is maximal by construction. What structure a permutation has is entirely higher order — in the correlations between nearby entries — and those are the correlations a wavelet tree’s stable reordering destroys.

That means the right way to compress a permutation is not to compress the tree. It is to choose a different representation: encode the permutation as a sequence of displacements, or as a set of increasing runs, or by the moves of a sorting algorithm. Each of those is a real technique and none of them supports a rectangle query, which is what the grid exists for.

The structure is answering a question, and the question fixes the representation. That is the honest ceiling on this idea, and it was available before any of it was built — which is why this essay exists before the three that measure.

The number that would have settled it in advance #

It is worth asking why this essay is first rather than last.

The deferral proposed compressing the grid. The three measurements that follow build three codings and report what each is worth. Every one of those numbers is bounded above by the sixteen per cent computed here, and that bound needed nothing but the point count and a logarithm.

A ceiling computed before the work is worth more than a measurement taken after it, because it decides whether the work is worth doing. Sixteen per cent of a quarter of the index is four per cent of the index, and four per cent is close enough to nothing that the honest response to the deferral would have been to say so and move on.

The reason the work was done anyway is that the ceiling is not the answer — the measured saving turned out to exceed it, for a reason that has nothing to do with compressing a permutation and everything to do with how the directory is stored. That is worth knowing, and it is the kind of thing a ceiling argument cannot produce.

The sixteen per cent is a fact about this z #

The ceiling is computed exactly and then carried through four essays as though it were a property of the structure. It is not. Both of its two terms behave differently as the point count grows, and one of them is decided by arithmetic nothing about the collection controls.

Stirling’s term is a constant per point, forever. $\log_2(z!)/z$ is $\log_2 z - \log_2 e$ to within a vanishing correction, so the gap between a point’s $\log_2 z$ bits and its share of the floor is 1.443 bits at every size. What changes is what that is a fraction of: at $z = 3{,}612$ it is 12.2% of the payload, at a million points it is 7.2%, and at a billion 4.8%.

So the ceiling shrinks as the collection grows, and it shrinks in the direction that matters — a strand deferring compression on the grounds that there is only sixteen per cent to play for is understating its case on any collection larger than the one measured.

And the rounding term is luck. It is $\lceil\log_2 z\rceil - \log_2 z$, which is 0.18 bits here because 3,612 sits close under 4,096. Had the parse produced 2,100 phrases the same arithmetic would give 0.96 — five times as much — and the ceiling would read 22% rather than 16%.

Across the whole band between two powers of two at this scale the ceiling runs from 12.0% (a point count exactly a power of two, no rounding at all) to 22.1% (a point count one above one). The headline number is therefore not sixteen per cent; it is somewhere in a two-fold range, and where it lands is decided by where a parse’s phrase count happens to fall — a quantity no design controls and no reader should read as a property of the coding.

That sharpens rather than weakens the argument this page makes, because the two terms are not equally available. The rounding is unrecoverable by any coding, as the section above says: a balanced wavelet tree over a permutation needs $\lceil\log_2 z\rceil$ levels, every value is equally likely so no Huffman shape helps, and 0.18 to 0.96 bits a point is simply gone. What a compressor can chase is Stirling’s 1.443, which is 12.2% of the payload here and less on anything larger.

Put that beside what the strand goes on to measure and the case closes. A block, a class and an offset reports 7.6% off the grid, and none of it is payload — a fifteen-bit block holding seven ones costs a thirteen-bit offset and a four-bit class, seventeen bits to store fifteen, so the coding loses on the balanced levels that make up this whole structure. The entire measured saving comes from the directory, which is the part the structure paid for before the first query is about and which no floor argument bounds.

Which is the honest summary of the four essays in one line: the 12.2% a compressor could take is untouched, and the 7.6% it did take came from somewhere the ceiling was never about. A ceiling computed in advance decided correctly that the work was not worth doing, and was measuring a different quantity from the one the work turned up — both of which are worth saying, and only the first of which the ceiling could have told anybody.

What is checked #

Every coding answers every rectangle identically. Thirty random rectangles against three vector implementations, with the reported points compared as sorted lists rather than as counts — a structure that reports the right number of wrong points is a failure this collection has recorded before.

Every level is balanced, above 0.97 bits a bit, which is asserted rather than observed so that a change to the tree’s splitting rule would fail here rather than quietly making a later essay’s argument false.

And every vector’s rank and select agree with an honest scan over a deliberately clustered vector, at every seventh position and every eleventh one. The clustering matters: a balanced vector exercises none of the run machinery, and a check that only runs on the grid’s own levels would be checking the easy case.

What follows #

Three measurements, in the order they answer the deferral.

A block, a class and an offset builds the coding that works and finds it worth 7.6%, of which 2.6 points are available on a permutation with no structure at all. The runs a permutation does not leave builds the coding the deferral asked for and finds it 17.8% larger than the plain vector. And the level where compression stops paying asks whether choosing per level helps, and answers with a number that is not worth the apparatus.