Bits — the series
-
The bits a coder emits
A stream of 16,384 symbols with a zeroth-order entropy of 3.891 bits per symbol was coded by a Huffman coder into 3.937 and by an arithmetic coder into 3.898, and neither went under 3.891 because neither can. That floor is a third kind of limit, the first that is a property of a model rather than of a question, and the same stream has a different one under every model of it.
-
The optimal code that is beaten
Huffman's code is optimal, the proof is correct, and on a stream where one symbol arrives 99 times in a hundred it spends 1.030 bits per symbol against an arithmetic coder's 0.119. Both facts hold. The word "optimal" in the theorem has a precondition attached that almost nobody quotes with it, and everything interesting about coding lives on the other side of that precondition.
-
The model is the compressor
One stream of 32,768 symbols has an entropy of 3.886 bits per symbol, and 2.243, and 1.186, and 0.991, and 0.909. All five numbers are correct, all five are floors, and nothing about the data changed between them. The only thing that changed is how many preceding symbols the model was allowed to look at — which makes the entropy of a file a property of a decision rather than a property of a file.
-
The dictionary that builds itself
LZSS contains no probability, no frequency table and no entropy calculation. Its entire model is a window of recent text and its only move is to say "the next nine symbols are the ones that appeared 1,200 positions ago". On a stream whose zeroth-order floor is 3.89 bits per symbol it spends 2.11, and widening its window past 4,096 makes it worse rather than better.
-
The transform that emits nothing
The Burrows–Wheeler transform outputs exactly the characters it was given, in a different order. Its zeroth-order entropy is therefore identical to its input's, to fifteen decimal places, and by that measure it has done nothing at all. A Huffman coder handed the result spends 1.935 bits per symbol where the same coder on the same data spends 4.209, and the difference is entirely in the order.
-
What a reordering costs to undo
Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.
-
The order inside a tie
Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.
-
A result the size of its own noise
Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.
-
Where a context stops naming the letter before
A sort of rotations by their first k characters matters only where those k characters fail to decide the character before them, and that share of positions can be counted in one pass with no sorting. It was proposed as a replacement for sweeping k. Counted as proposed, it misses by a factor of four: on a stream of independent words 37% of positions are still ambiguous at four characters, where the sweep has already gone flat. Counted only where the context sits inside a word that goes on past it — the one place more context can still help — it lands within a step of the sweep on four sources of five.
-
The repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
-
The deepening the sort was already doing
A sort of rotations by their first k characters loses to the full Burrows–Wheeler transform where a longer string repeats, and a sort deepened only inside the ranges where contexts repeat was proposed to recover those bits at a fraction of the transform's reading. It recovers the bits: on sixteen streams every one lands within 0.006 bits a symbol of the transform, and the most repetitive goes from 0.129 bits worse to 0.001. It reads more characters than the transform, not fewer — 74.5 a symbol against 69.4 on technical writing — because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort. The characters a sort by k characters saves are exactly the ones the repeats needed.
-
The order the column cannot see
A sort of rotations by their first four characters leaves ranges that agree on those four, and the full Burrows–Wheeler transform reads deeper to order them. Given a budget of characters below the transform's, spending it on the ranges whose rotations are preceded by the most different characters was predicted to reach within a hundredth of a bit at two thirds of the transform's reading — and spending it on the longest agreements, as the transform does, to waste it. The price was impossible: the four-character sort alone reads 76% of what the transform reads. The ranking was right on average, and right for a reason that makes the budget unnecessary: a range whose rotations are all preceded by one character writes the same run into the output in any order. Skipping every such range writes the transform's column exactly, on all sixteen streams, and reads 11% less on technical writing — up to 19% on the stream with the longest repeats.