The runs a permutation does not leave

The deferral said it in one clause: a permutation with structure has bit vectors with runs, and the plain vectors here charge one bit per bit.

This essay builds the coding that clause asks for. It makes the grid 17.8% larger, and the reason is arithmetic that could have been done first.

What coding a run costs #

A bit vector is a sequence of alternating runs. Store their lengths and one bit saying what the first run holds, and the vector is recoverable.

A length is a positive integer of unbounded size, so it needs a self-delimiting code. Elias gamma is the standard one: write ⌊log₂ L⌋ zeros, then L in binary, for 2⌊log₂ L⌋ + 1 bits.

That is 1 bit for a run of 1, 3 for a run of 2 or 3, 5 for a run of 4 to 7, 7 for 8 to 15. Set against the L bits the run replaces:

The coding first breaks even at six. Below that it costs more bits than the run it replaces, and a vector of short runs comes out larger.

It is worth being clear that gamma is not a bad code. It is within a constant factor of optimal for an integer of unknown magnitude, and any self-delimiting code has the same shape — a prefix saying how long the number is, then the number. A code that spent one bit on a run of one would have to spend more somewhere else.

What the table above says is not that this code is inefficient. It is that coding runs is the wrong idea for a vector whose runs are short, whatever code is used, because the length is the information and a short length is almost as much information as the bits it describes.

What the grid’s runs actually are #

Measured over the twelve levels: mean run 2.34.

A uniform permutation of the same size gives 1.90. So the parse’s grid is more ordered than chance, by a factor of 1.23 — the deferral was right that the structure is there. It is a fifth of the way to being worth coding.

The distribution across levels is worth reading. The top level is 2.05, the middle levels reach 3.19, and the bottom two are 1.65 and 1.33. The last of those is very close to the 1.25 a fair coin gives, and there are 3,612 bits of it.

That distribution is itself the answer to whether a per-level choice helps, and the level where compression stops paying is the essay that measures it. The short version is visible already: the best level here is at 3.19, which is still below break-even, so no level of this grid is worth run-coding.

Why the middle is the longest #

The shape of the curve is not what the argument predicts, and it is worth stopping on.

One would expect the top level to be the most ordered — it is the one where x and y are still in their original correlation — and every level below it to be worse, as the stable reordering destroys locality.

What happens instead is that level zero is 2.05 and levels four to six are around 3. The reason is that the top level’s split is by value, at the midpoint of the whole range, and a boundary’s y rank is only loosely tied to its x rank: adjacent boundaries often fall on opposite sides of a midpoint that is far from either of them. Further down, a node’s value range is narrow and the points in it are a set of boundaries that genuinely resemble each other, so consecutive ones do fall the same way.

The effect then collapses at the bottom, where a node has two points and there is nothing left to resemble.

The number chance gives #

It is worth deriving 1.90 rather than only measuring it, because a control one can predict is a control one can trust.

A vector of independent fair bits has a run ending at each position with probability one half, so its runs are geometric with mean two. A permutation’s level is not independent bits — it has exactly as many ones as zeros — and sampling without replacement makes runs very slightly shorter than two. At 3,612 bits that correction is small, and the measured 1.90 is a little below two for exactly that reason.

So the number to beat is two, near enough, and the grid gives 2.34. Everything in this essay follows from those two numbers and from the break-even of six.

The measurement #

Plain: 51,600 bits. Run-coded: 60,805.

Broken into parts, the coding does what it says on the payload: 43,344 bits of plain payload become 45,973 — which is already a loss, because the mean run is below break-even — and the directory goes from 8,256 to 14,832.

The directory is the larger half of the damage, and it is worth saying why it grows — the same asymmetry a bit for every bit records for the plain vector, working the other way. A plain vector’s directory is a counter every 64 bits; a run vector’s is a sampled entry every 32 runs, and at a mean run of 2.34 that is an entry every 75 bits. More samples, each holding a position and a count.

Where the 17.8% actually came from #

The argument so far is a mean against a break-even: 2.34 against 6, therefore a loss. That argument predicts the sign correctly and its magnitude is wrong by a factor of eight, and the discrepancy is worth chasing because it says which of the two numbers above is load-bearing.

Take the break-even arithmetic at the mean. A run of 2.34 costs $2\lfloor\log_2 2.34\rfloor + 1 = 3$ bits and replaces 2.34, so the payload should come out 1.47 times larger. It comes out 1.061 times larger — 45,973 against 43,344.

The gap is the distribution. Gamma’s cost grows as the logarithm of a run’s length while the bits it replaces grow linearly, so evaluating a concave cost at the mean overstates what the coder actually spends: a vector whose runs are mostly of length one, with a tail of longer ones, pays one bit for each of the cheap majority and the mean never sees it. The mean run is the wrong statistic for the payload, in exactly the way expected is not average sets out — a single number standing in for a distribution, in a place where the function applied to it is not linear.

So the payload loses six per cent, not forty-seven, and the headline is 17.8. The rest is the directory, and the directory is where the mean run is exactly the right statistic.

A run vector’s directory samples every 32 runs, so its size is the run count divided by 32, and the run count is $n/\mu$. That is linear in $1/\mu$ with no concavity to soften it, and at $\mu = 2.34$ the structure is sampling every 75 bits where a plain vector’s counter sits every 64. The directory goes from 8,256 bits to 14,832 — an increase of 6,576 against the payload’s 2,629, so the directory is 71 per cent of the damage and the coding of the runs themselves is a quarter of it.

Two things follow, and neither is visible from the break-even table alone.

The first is that the hybrid sketched below would recover less than it looks like it should. Storing short stretches verbatim fixes the payload, which was never the expensive half; unless it also reduces the number of entries the directory has to sample, the 6,576 bits stay. A coding that eliminated the payload loss entirely would still leave this grid about twelve per cent larger than the plain vector.

The second is a correction to how this measurement should be read against a bit for every bit. That essay’s finding is that a rank directory is a fifth of a plain bit vector and is the part nobody counts. Here it is a quarter of the run vector and three quarters of its loss. The technique changed, the payload changed, and the part that decided the outcome was the same part both times.

The shuffle, which is the control #

The claim under test is that the ordering carries information. The way to check it is to destroy the ordering and see whether the number moves.

Shuffle the top level’s bits. Its length is unchanged, its number of ones is unchanged, and its zero-order entropy is unchanged to the last bit. Its runs are destroyed.

Run-coded, the ordered vector is 5,296 bits and the shuffled one is 5,369: a difference of 1.4%.

That is the finding. Whatever ordering the parse’s grid has, a run coder can extract 1.4% of a vector’s worth of it — and it charges 22% for the attempt.

Why the control is the right one #

A control has to hold fixed everything except the property under test, and this one does: the shuffle preserves length, density, and therefore every zero-order statistic. What it changes is exactly the arrangement, which is what a run coder reads.

That makes it a sharper control than the uniform permutation a block, a class and an offset uses. A uniform permutation differs from the parse’s grid in its provenance; a shuffled level differs from its own unshuffled self in nothing but order.

A run is a property of the input is where this collection first insisted on the distinction, about a sort’s runs rather than a vector’s. The rule is the same: a measure that does not move when the thing it claims to measure is destroyed is measuring something else.

The one thing it is better at #

There is a column where the run vector wins, and it is not size.

On the descent — ranks only, which is what every rectangle pays whatever its answer — the run vector inspects 100,156 bits over sixty rectangles against the plain vector’s 112,532. It is cheaper to read.

The reason is that 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 a sample every 32 runs the walk covers about 75 positions in 32 steps. Fewer steps than 64 bits.

That is a real property and it is a fragile one, because it is the only cost in this strand that follows the data. A plain vector’s rank scans a fixed block whatever the block holds; a run vector’s cost rises as the runs shorten. Measured across a divergence sweep: 13.9 bits inspected per rank at exact copies, 19.6 at five per cent changed, 22.3 at forty — a rise of 1.60, against the plain vector’s flat 24.8, 22.6, 21.3.

What a coding that degraded gracefully would look like #

There is a design that would have avoided this outcome, and naming it is useful because it is what a careful implementation ships.

Code a run only when it is long enough to pay, and store short stretches verbatim. That is a hybrid — a flag bit per stretch, then either a gamma-coded length or a literal — and its size on a vector of short runs is the vector plus a flag, rather than the vector times 1.06.

It is not built here, and the reason is the strand’s comparison. Three codings measured on one structure, each in its published form, is a comparison a reader can check against other people’s numbers. A hybrid tuned until it does not lose is a fourth thing, and its result would be “a coding that was designed not to lose does not lose”.

What it would be worth is a deferral, and the arithmetic says it is worth approximately nothing: a hybrid on this grid would land within a per cent of the plain vector, which is what “does not lose” means here.

Where run coding does work #

It would be wrong to leave this reading as a verdict on the technique, because this collection has a structure where the same coding is the whole point.

The index that stores the runs is a Burrows-Wheeler transform kept as its runs — the measure a floor under a run count puts an exact floor beneath — and there the mean run on a repetitive collection is in the tens or hundreds — a transform of eight copies of a text has runs proportional to the base text rather than to the collection. That is far above the break-even, and the structure is smaller than the text by a large factor.

The difference is what is being coded. A transform’s runs come from repeated contexts, which repetition creates directly. A wavelet tree level’s runs over a permutation come from a correlation between two orderings, filtered through a splitting rule that reorders the points at every level.

The same coding, applied to two structures, differs by two orders of magnitude in what it is worth. Repetition is not entropy is the theme; this is the sharpest pair of instances in it.

What could have been computed first #

The break-even is six. The mean run needed to be known.

Measuring a mean run is one linear pass over a vector and costs nothing, and it would have settled the question before any coding was written: 2.34 against a break-even of 6, on a structure whose payload is 16% above the information-theoretic floor for any permutation at all.

This collection’s habit is to build the thing rather than argue about it, and that habit is right more often than not — the table the links already knew records a case where building it overturned a published conclusion. It is worth recording the other side too: a one-pass measurement and a two-line arithmetic would have produced this essay’s answer without the structure, and the structure’s value is that the answer is now a number rather than an expectation.

What the deferral was actually seeing #

It is worth reconstructing the intuition once more, because it was not foolish and the failure is specific.

A repetitive collection’s phrase boundaries genuinely do cluster. Boundaries that come from the same region of the base text sit near each other in the prefix ordering and near each other in the suffix ordering, so the permutation has patches where it is nearly the identity. Plotted as points, the grid looks like a thickened diagonal with noise, and a thickened diagonal is exactly the shape whose top-level bit vector is a long run of zeros followed by a long run of ones.

The top level’s mean run is 2.05.

The gap between the picture and the number is the thickness. A diagonal band of width w produces, at level zero, alternating stretches whose length is about the number of consecutive x positions that stay on one side of the midpoint — and with a band even a few per cent of the range wide, that is a handful of positions. A picture that looks like a line is a vector that looks like noise, and there is no contradiction between the two.

What is checked, and what must fail #

Rank, select-one and select-zero agree with a scan on a deliberately clustered vector — clustered, because the grid’s own levels have almost no runs and a check on them would exercise none of this machinery.

Three things must fail, and the third is the one this essay depends on.

A directory that samples positions rather than ones leaves rank right and select wrong: 287 of 287 selects wrong, and 309 ranks wrong once the counts are gone. A size that omits the directory reports the structure 1.32 times smaller than it is.

And a run vector that forgets which value its first run holds is one bit, produces exactly the complement of the right answer, and reports an identical size: 324 of 334 ranks wrong, with the payload unchanged to the bit. That is the check that guarantees the sizes above are sizes of a working structure.

What this leaves for the last essay #

Two codings measured, one worth 7.6% and one worth −17.8%, and a per-level plate showing that neither is best everywhere.

That invites the obvious question — choose the best coding for each level — and the level where compression stops paying is what that is worth. The answer is a number small enough to end the strand.