The level where compression stops paying

Two codings have been measured. One takes 7.6% off the grid and one adds 17.8%, and the per-level plate shows that neither is best at every level — the run coder wins at levels one, two and four of the twelve, and loses everywhere else.

That invites the obvious move. The levels are independent bit vectors; nothing requires them to be stored the same way; choose the best coding for each.

The answer #

Choosing per level comes to 47,642 bits. The best single choice is 47,668.

Twenty-six bits. Five hundredths of one per cent.

A structure that recorded which coding each level used would need a few bits a level to say so, and twelve levels at two bits is twenty-four — so the saving very nearly pays for the flag that makes it possible, and pays for nothing else.

It is worth stating what would have counted as a good answer. The strand’s whole saving is 7.6% of a structure that is 28% of an index. A per-level refinement worth ten per cent of that saving would be 0.76% of the grid and 0.2% of the index — already too small to justify a flag. To be worth having, per-level choice would need to be worth several per cent of the grid, which is most of the saving again.

So the bar was high before the measurement, and the measurement came in three orders of magnitude under it.

Why so little #

Because the levels where the run coder wins, it barely wins.

Look at the plate. At level one the run vector is 101 bits against the block coder’s 110 on a small collection, or a few per cent on a larger one; at the levels where it loses, it loses by twenty per cent. A per-level choice therefore collects a handful of small wins and avoids no large losses that the single best choice was not already avoiding.

That is the general shape of this kind of optimisation, and it is worth stating as a rule: choosing per part is worth something only when the parts differ in kind. Here they differ in degree — every level is a permutation’s level, balanced by construction, with a mean run between 1.3 and 3.2 — and a set of things that differ in degree has one best answer for nearly all of them.

The bits the choice would have to be recorded in #

There is a cost on the other side and it is small but not zero.

A structure that stores its levels differently has to say which is which, and it has to say it in a place a reader of the structure can find without decoding anything — a header of a couple of bits a level. Twelve levels is twenty-four bits.

Against a saving of twenty-six, the flag is nearly the whole of it. That is not the reason to reject the idea — twenty-six bits is already nothing — but it is a reminder that an optimisation has a fixed overhead as well as a variable saving, and that the fixed part is what decides the smallest optimisation worth making.

What would have made it worth something #

It is easy to imagine a structure where it would be. Suppose the top three levels of a grid were genuinely run-structured — mean runs in the tens — and the bottom nine were noise. Then the run coder would win by a large factor at the top and lose by a fifth at the bottom, and a per-level choice would collect a real saving.

That structure exists. It is not a permutation.

A wavelet tree over a text — the one the index that is smaller than the text is built on — has exactly that shape: the top levels split the alphabet’s frequent symbols from its rare ones, and on a repetitive text those levels have long runs while the bottom ones do not. The index that stores the runs is the structure that exploits it, and there a per-level choice is worth having.

The difference is what the tree is over. A permutation’s levels are all the same kind of thing, and a text’s are not.

The deferral, answered #

The deferral read: a compressed grid, since a permutation with structure has bit vectors with runs, and the plain vectors here charge one bit per bit.

The answer is no, and the strand’s four measurements are why.

The payload is 16% above the information-theoretic floor for any permutation whatever, so nothing can win more than that. The runs are 2.34 against a break-even of six, so coding them loses. The block coding wins 7.6%, of which 2.6 points are available on noise. And choosing per level is worth 0.05%.

Put on the index the grids sit in, the best of that is 5.8% of the whole structure, with no change to any answer and no measurable change to the descent.

It is worth noting that this collection has met the mirror image of this result too. The fold that minimises the wrong thing records a case where the parts genuinely differ in kind — a merge whose levels charge differently — and there the per-part decision is the whole content of the structure. The two together make the rule usable: look at whether the parts differ in kind before building the apparatus to choose between them.

The quantity that decides it, and where it was already written down #

The 26 bits are not an accident of these twelve levels, and the general form is worth having because it is computable from a plate this strand already had.

Let each level $i$ cost $A_i$ under one coding and $B_i$ under the other, and let $A$ be the better of the two totals. Choosing per level costs $\sum_i \min(A_i, B_i)$, so the saving is

$$\sum_{i\,:\,B_i < A_i} (A_i - B_i)$$

— the winner’s total regret on the parts it loses, and nothing else. Every level where the overall winner also wins contributes zero, however large its margin; only the flipped levels contribute, and only by the size of the flip.

Two consequences drop straight out.

The first is that the strand’s second assertion — per-level is never worse than the best single choice — is a tautology rather than a test. A sum of minima cannot exceed a minimum of sums, so the only thing that check can catch is a bookkeeping error, which is what the essay says it is for, and it is worth being clear that it can never find a finding.

The second is the useful one. The regret is readable off the per-level plate, which existed before any per-level apparatus was written. Three levels flip; each flips by single-digit bits against level totals in the thousands; the sum is twenty-six. That is a subtraction over twelve pairs of numbers already drawn on a figure at the top of this page, and it answers the question completely.

So this strand contains its cheap prior measurement twice over, in the same shape. The run coder’s break-even was two lines of arithmetic against one linear pass, and the per-level saving was a subtraction over a plate already drawn. In both cases something was built to find out what a subtraction would have said.

The regret formulation also gives the criterion the flag turns into a rule. The header costs about two bits a part, so per-part choice is worth building only when the regret exceeds $2p$ for $p$ parts — twenty-four bits here, against a regret of twenty-six. That is not a close call dressed up as one; it is a case where the saving and its own overhead are the same size, and the shape of the answer would be identical at any collection size, because both scale with the number of levels rather than with the number of bits.

And it says exactly when the idea is worth pursuing, in a form that does not require the parts to be measured first: the regret is large when the two codings’ rankings disagree by large margins, which happens when the parts differ in kind. A wavelet tree over a text has frequent-symbol levels and rare-symbol levels and they are genuinely different objects; a permutation’s levels are twelve instances of one object. The rule stated above — look for a difference in kind — is the qualitative reading of a quantity that can simply be computed, and a threshold somebody chose is the reminder that the flag’s two bits a level are a decision too, not a constant of nature.

What a negative result costs to produce #

Four essays and five hundred lines of structure to establish that an idea is worth five per cent. It is worth asking whether that was a good trade, because this collection will face the question again.

Two things came out of it that a shorter answer would not have produced.

The floor — log₂(z!) against a wavelet tree’s ⌈log₂ z⌉ per point — is a general statement about grids over permutations and it bounds every future version of this idea. That is worth having and it took one logarithm.

And the select the compressed vector did not have. A block-coded bit vector in this collection had answered rank since the index field opened and had never been asked for a select, because a backward search descends and does not come back up. A grid comes back up. That gap was found by building this, and it would have stayed open otherwise.

And a control this collection did not previously have #

The shuffle test in the runs a permutation does not leave is the third thing worth keeping. It holds a vector’s length, density and zero-order entropy exactly fixed and destroys nothing but the arrangement, which makes it the sharpest available control on any claim about ordering.

Every earlier compression claim in this collection was controlled against a different text — an incompressible one, a uniform one — which controls for the wrong thing: two texts differ in their statistics as well as in their order. A shuffled copy of the same vector differs in order alone.

That control now exists and is cheap, and the claims it could be pointed at are not all in this strand.

The measurement that was cheap and would have settled it #

The mean run is one linear pass over a vector. The break-even is two lines of arithmetic. Together they say, before anything is built, that a run coder will lose on this structure.

That measurement was available and was not taken. The deferral was written from a picture — a grid over a repetitive collection’s boundaries looks like a thickened diagonal — and a picture that looks like a line is a vector that looks like noise, because the band’s thickness is what decides the runs and the band is a few per cent of the range wide.

This collection’s habit of building rather than arguing is right more often than it is wrong. The table the links already knew records a case where building overturned a published conclusion by a factor of two hundred. The habit worth adding is narrower: when the idea has a break-even, compute the break-even first.

What the descent says, which is the one surprise #

There is one result in this strand that no amount of arithmetic would have predicted, and it runs the other way.

The descent through a grid is ranks only, and in bits inspected the three codings are within twelve per cent of each other — 112,532 for the plain vector, 105,953 for the block coder, 100,156 for the run coder, over sixty rectangles. The run vector, which is the largest of the three, is the cheapest to read.

That is because a plain rank scans up to a block of bits and a run rank walks runs from a sampled position, and at a mean run of 2.34 with samples every 32 runs the walk covers about 75 positions in 32 steps.

So the whole difference between these three structures is size, and the descent does not care what its vectors are made of. That was not obvious and it is the sort of thing only a measurement produces.

The one cost that follows the data #

That line is worth a paragraph of its own, because it is the only cost in this strand that the data can move.

A plain vector’s rank scans a fixed block whatever the block holds, so its cost is a property of the block length. A run vector’s rank walks runs, so it costs more the shorter the runs are: 13.9 bits inspected per rank on exact copies, 19.6 at five per cent changed, 22.3 at forty — a rise of 1.60 across a sweep on which the plain vector goes 24.8, 22.6, 21.3, which is drift rather than trend.

A structure with a data-dependent query cost is a structure whose worst case is set by its input rather than by its design, and that is a property worth knowing about before shipping one. Nothing here is fast enough or slow enough for it to matter; on a vector whose runs collapsed it would.

What a reader should take away about grids #

Three things, and only the first is about compression.

A wavelet tree over a permutation is already near its floor. Twelve bits a point against 10.38, which is 16%, and that bound holds for every coding and every collection. Anyone proposing to compress one should start there.

The interesting size in a grid is its directory, not its payload. The structure paid for before the first query records a version of this grid that was six times its payload in directory alone, and the fix was a layout change rather than a coding one. Layout beat coding by a factor of six; coding is worth 7.6%.

And a grid’s cost to a reader is not its size. It answers no query on its own — it accelerates an index’s intersection — so the number that matters is its share of the structure it is bolted to, which is 28%, and the number this strand moves is 5.8%.

What is checked #

Every coding answers every rectangle identically, as sorted lists of points — the check a rectangle over a permutation established when the structure was built, run again against three implementations of its vectors.

Choosing per level is never worse than the best single choice — asserted, because the mixed figure is a minimum over the same numbers and a mixed total above the best single one would mean a bookkeeping error rather than a finding.

And the per-level saving is under five per cent, asserted in that direction so that a change making it larger would fail here rather than quietly turning this essay’s conclusion around.

Where the strand sits beside its neighbours #

It is worth placing this result against the other three deferrals taken up alongside it, because they came out very differently and the differences are instructive.

The succinct range minimum was named as a structure that would move a crossing “to a handful”. It moved it by a factor of three — less than hoped, and a real result, because the structure it replaces was measurably worse on both size and query cost.

The bidirectional index was named as a structure that would stop an index doubling. It does not: the structure that was supposed to halve measures the doubling at exactly two and finds the structure worth having for an entirely different reason.

The linear-time parse was named because a quadratic construction was setting every sweep size in its ladder. It works, and it moved those sweeps by a factor of thirty.

And this one was named on an intuition about runs, and the intuition was wrong in a way a one-pass measurement would have caught. Four deferrals, one clean success, two useful retractions and one negative result — which is a reasonable distribution, and a better one than four confirmations would have been.

What this strand leaves #

A grid that is stored the way it was, plus an option worth 5.8% for a reader who wants it. The plain vector remains the default, because the block-coded one costs a select implementation and buys a twentieth of an index.

And one deferral, sharper than the one it answers. The floor computed here — log₂(z!) — applies to a structure that can recover the permutation. A structure answering only how many points are in a rectangle, never which, is not bound by it and could in principle be smaller. The phrase index needs the points, so that structure is no use here. Whether it is smaller enough to be worth having for some other query is not measured, and nothing in this collection asks that question yet.