What a reordering costs to undo

The transform that emits nothing established that a permutation can lower a floor it cannot change. The Burrows–Wheeler transform outputs the characters it was given in a different order, so its zeroth-order entropy is identical to its input’s; put the output through a move-to-front pass and the entropy falls from 4.156 bits per symbol to 1.802, and the whole of the difference is in the order.

That result invites an obvious question and does not ask it. If clustering is what pays, why stop at the transform’s clustering? Sort the characters. A sorted string is perfectly clustered — one run per distinct symbol — and a move-to-front pass on it emits one non-zero rank per distinct symbol and zeroes for everything else. Its entropy is very close to nothing.

The answer is that the comparison was never between two streams. It is between two streams plus whatever each one costs to undo, and only one of those two numbers was on the plate.

The sort’s two bars are the page. It drives the stream to 289 bits — a saving of 99.1% against the untransformed text — and the total comes to 1.006 times the floor it started from.

Why the cancellation is exact #

This is not a coincidence about this text and it is not approximately true. It is a counting argument, and it is the same shape as the one under every floor in this field.

A sort sends every arrangement of a multiset of characters to the same string. To undo it, a decoder must be told which arrangement the text was, and there are

$$\frac{n!}{\prod_k n_k!}$$

of them, where $n_k$ is how many times the $k$-th symbol occurs. The number of bits needed to name one of them is the base-two logarithm of that count, and Stirling’s approximation puts that logarithm at $n H_0$ — the text’s own zeroth-order entropy — to within a term of order $\log n$. On these 8,192 symbols the exact logarithm is 31,827 bits and $n H_0$ is 31,931: the two agree to three parts in a thousand, and the gap shrinks as the text grows.

So the sort’s side information is the floor, up to a vanishing correction. A compressor that sorts and then codes has moved the entire cost from the stream into the description of the permutation, and gained nothing at all. It is the compression equivalent of the counting argument the bits a coder emits uses to establish the floor in the first place: there are only so many texts, and something has to distinguish them.

The same number, in another field #

That quantity has appeared before in a subject with no compression in it at all.

$\log_2 n!$ is the number of comparisons a comparison sort must average, and the floor under every comparison sort derives it by counting leaves: the answer is one of $n!$ orderings, each comparison has two outcomes, so no algorithm can average fewer. When the keys are not distinct the count of possible answers falls to $n!/\prod_k n_k!$, because arrangements that differ only by swapping equal keys are the same answer, and the floor falls with it.

That is the same expression, to the symbol. The bits a decoder needs to undo a sort are the comparisons a sorter needs to perform it, and they are equal for the same reason: both are the logarithm of how many arrangements the operation cannot tell apart. One field calls it a lower bound on questions and the other calls it side information, and there is one counting argument underneath.

The correspondence is worth following one step further, because it says something about the transform. A sort discards $\log_2(n!/\prod n_k!)$ bits and a sorter pays the same to produce them. The Burrows–Wheeler transform sorts too — its block sort is exactly a sort, of $n$ rotations, and it pays that price in comparisons — and then keeps the result in a form that discards nothing. So the transform is the case where the work of sorting is done and the information it establishes is retained rather than thrown away, and one run, four counts, four answers is the page about how much that work actually is.

Forty-five outputs for 6,561 strings is the collapse made visible, and it is why the enumeration is worth doing rather than trusting the formula: the rule the ledger applies is a claim about a family of inputs, and here every member of a family is checked.

The transform’s column of that plate is the result the rest of the page turns on. Six thousand five hundred and sixty-one strings, six thousand five hundred and sixty-one outputs: the transform is injective on strings of a fixed length, so nothing whatever has to be sent alongside it. Its inverse reads its own output and needs no other input.

There is one reading of the sort’s row that has to be closed off, because it is the reading that makes the result look like an accounting trick. The 289 bits are not fake and the 31,827 are not a penalty invented to cancel them. A decoder handed 289 bits and told they are a sorted string reconstructs the multiset and nothing else, and the multiset is genuinely almost free to describe — it is a list of twenty-one counts. What it cannot reconstruct is the text, and the 31,827 bits are the smallest description of the difference that exists. Both halves are real transmissions and the sum is what a receiver has to be sent.

A permutation the inverse can compute #

That property is not shared by clustering permutations in general, and it is worth saying exactly what it is.

The rows of that table are the rotations of the text, sorted. The first column is the sorted characters — which is precisely the permutation this page has been pricing — and the last column is the transform. They are two columns of one table, and the difference between them is everything.

The first column throws away which rotation each character came from. The last column keeps it: a character in the last column is the one preceding a rotation, and the rotations are in a known order, so the last column records both the characters and enough about their positions to walk the text backwards. That is the LF mapping, and it is why a decoder needs nothing but the output.

Put the other way round: the transform’s output is a description of the permutation as well as of the characters, and the sorted column is only a description of the characters. The bits the sort has to send separately are bits the transform has already sent inside its own stream.

That also explains why the transform clusters less. It cannot cluster perfectly, because a perfectly clustered output would be the sorted string, which is not invertible. The 1.802 bits per symbol is what is left after the output has been made to carry its own inverse, and the gap between 1.802 and 0.035 is the price of that.

What the shuffle is for #

The third row of the ledger is a control and it pays for its place twice.

A shuffle fixed by a stated seed costs nothing to undo — encoder and decoder agree on the seed in advance, so the permutation is common knowledge and there is no side information at all. By the accounting of this page it is free. And it makes the stream worse: 34,418 bits against 34,020 for the untransformed text.

So being free to undo is not sufficient, which is the half of the argument the transform’s success might otherwise hide. A permutation has to be both computable by the decoder and useful to the coder, and the two conditions pull against each other: the permutations that cluster hardest are the ones that discard the most, and what they discard is exactly what the decoder needed.

The shuffle also says something about move-to-front that the previous page could not. Applied to the untransformed text, move-to-front raises the cost from 31,931 bits to 34,020 — it is a loss of 6.5% on text it cannot exploit. It is not a neutral recoding; it is a model, one that assumes a symbol seen recently will be seen again soon, and on a stream where that is false it charges for the assumption. That is the same observation the dictionary that builds itself makes about a sliding window — a structure with no probabilities in it is still a claim about what the data looks like.

On a Markov chain the move-to-front pass is worth 29% by itself, and the shuffle’s 24.6k is the measurement of what it was exploiting: destroy the order and the pass goes back to charging exactly the zeroth-order floor. That is a cleaner statement of what move-to-front is than the previous page’s, which could only say what it did after the transform.

Two sources where none of this works #

The ledger is a fair instrument only if it can report a failure, so here are two.

That is the case the whole apparatus has to get right and it does: four different routes, one number, and the number is the floor. A measurement that reported a saving here would be measuring itself.

Here the transform is a loss of 51%, and the reason is that the move-to-front pass is the wrong model for a stream that is already skewed. The rank stream it produces is dominated by zeroes either way, and the ranks carry less structure than the original symbols did — the same failure the optimal code that is beaten records for Huffman codes on skewed sources, arriving from a different direction. A compressor that applied this pipeline unconditionally would make such a file half again larger, which is why real ones measure and choose.

A reader might reasonably ask whether the skewed case is an argument against move-to-front rather than against the transform, and the ledger separates them. On that stream the untransformed text after move-to-front costs 9.3k and the transform costs 9.4k, so the pass is losing 3.1k on its own and the transform is adding a further 0.1k. The pass is the larger fault. But the transform cannot be run without something to turn its clustering into skew, and a pipeline is priced as a pipeline: a code word is at least one bit is the page about what happens when a stage’s floor is a floor of its own rather than of the data.

How the numbers move with the block #

One parameter has been held fixed throughout and it is the one a real compressor tunes.

The sort’s line is the counting argument converging: at a thousand symbols the side information is a few per cent above $n H_0$ because of the correction term, and by sixteen thousand it is within a fraction of a per cent. It approaches the floor from above and never reaches it.

The transform’s line falls because the sorted rotations get longer, so the contexts that decide the order get more specific and the clustering improves. That is the reason bzip2 sorts blocks of 900 kB rather than of 9 kB, and it is also the reason it cannot simply sort the whole file: the block sort’s cost grows faster than the block does, which the transform that emits nothing priced — and which is why the transform’s afterlife is in the index that is the text, where the cost of constructing it is amortised over many queries, rather than in a compressor that reads its input once.

What is claimed and what is not #

Every number here is a floor, not a file size. The stream is charged at its own zeroth-order entropy, which is what an arithmetic coder with a perfect model of the symbol frequencies would spend, and no coder is run. A real pipeline also pays for a frequency table, for block headers and for the run-length stage between move-to-front and the coder. Those are constants of a few hundred bits and none of them changes a ranking here.

The side information is counted as if it were sent optimally. Naming one arrangement of the multiset takes $\log_2(n!/\prod n_k!)$ bits only if the arrangements are equally likely and coded together; a decoder given the sorted string knows the multiset, so this is the right count for that decoder. A different decoder — one already holding a model of the text — would need fewer, and then the sort would be a saving rather than a wash. The argument is about what a zeroth-order decoder needs.

Move-to-front is doing part of the work and is not the only choice. Run-length coding the transform’s output, or applying an order-1 model to it directly, reaches different numbers, and the previous page’s 1.802 and this page’s 14,760 bits are both statements about the transform with this pass after it. What is not sensitive to the choice is the sort’s ledger, since the sort’s stream is near zero under any reasonable pass and its side information does not depend on the pass at all.

And injectivity was checked at one length over one alphabet. The enumeration covers every string of eight characters over three letters. The transform is injective on strings of a fixed length for every length and alphabet — the standard argument is that the sorted-rotations table is recoverable from its last column — but that argument is not what this page measured.

What to take from the ledger #

Three things, in the order a reader is likely to need them.

A preprocessing step is priced by its total, and the total includes its inverse. That sounds obvious written down and the literature is full of transforms reported on the stream alone — which is the number that makes a full sort look like a 99% saving. The check is cheap: ask how many inputs produce this output, and if the answer is more than one, the logarithm of it is a cost that has to appear somewhere.

A transform that is a function of its own output is in a different class from one that is not, and it is the class worth looking for. The transform, a shuffle with an agreed seed and the identity are all in it; the sort is not. What makes the transform interesting is that it is the only member of that class here which also clusters, and the previous page’s whole result is the measurement of how much.

And none of it is unconditional. The two failing sources above are not edge cases constructed to embarrass the method — a uniform stream and a heavily skewed one are both ordinary — and on one of them the pipeline costs half again what doing nothing costs. The model is the compressor is the page that says why: every number in this field is a floor under a model, the move-to-front pass is a model, and a model applied to data it does not fit charges for the misfit. The ledger’s job is to make that charge visible, and a plate that drew only the stream would hide it.

Still open: the permutations between the two #

The sort and the transform are the two ends of a range that this page has left empty. Sorting the rotations by their whole following context gives the transform; sorting the characters with no context at all gives the sort. Between them is sorting the rotations by their first $k$ characters — a shorter context, a coarser sort, and a transform that keeps less of the order.

The prediction from this page is that such a transform costs something to undo, since a shorter context leaves ties and the ties are exactly the information the inverse is missing, and that the amount grows as $k$ falls until at $k = 0$ it is the whole multinomial. If that is right, then the transform and the sort are one family with a parameter, and the parameter buys clustering with side information at a stated exchange rate.

The measurement that follows implements the order-$k$ sort for $k$ from zero upwards, enumerates the preimages at small lengths to count what each one costs to undo rather than assuming it, and asks whether any $k$ short of the full context comes out ahead — since a shorter sort is cheaper to compute, and the block sort’s cost is the reason the transform lost its place in compression.