The bits a coder emits

This site has two floors already. The floor under every comparison sort says no comparison sort averages fewer than $\log_2(n!)$ comparisons. A floor on the bits says no structure answering approximate membership at a rate $\varepsilon$ uses fewer than $n\log_2(1/\varepsilon)$ bits of space.

Both are properties of the question. Sorting has $n!$ possible answers and that number does not care what anybody assumes; the membership bound counts the sets that must be distinguishable and neither does that.

The third floor is not like that, and the difference is the whole subject of this field.

What a coder is being measured on #

The seventh counter on this site counts bits emitted: a coder is written against a BitSink and cannot produce output without the output being measured.

That sounds like a technicality and it is the difference between this field and a recitation. Nothing here computes $-\sum \log_2 p$ and calls it a compression result. Every number on this page came out of a coder that wrote bits one at a time, and every coder here has a decoder that reads them back and is required to reproduce the input exactly. A compression ratio quoted from a coder that was never decoded is a claim about a program nobody has shown to work, and the failure mode is not a crash — it is a bit count that is too small, which reads as a better result.

The site has counted bits twice before and neither time was this. Coins counts bits consumed, a resource an algorithm spends, in the same way it spends comparisons. The Bloom filter bound is about bits stored. These are bits emitted: the coder’s output, the thing it exists to minimise.

The floor #

Shannon’s source coding theorem, in the form this page needs: a stream whose symbols are drawn independently with probabilities $p_i$ cannot be coded, on average, in fewer than

$$H = -\sum_i p_i \log_2 p_i$$

bits per symbol. The quantity $-\log_2 p$ is what a symbol of probability $p$ is worth: a symbol that happens half the time is worth one bit, one that happens a thousandth of the time is worth 9.97, and one that always happens is worth nothing.

For the hero figure’s stream — text built from a fixed vocabulary, 21 distinct characters — $H_0$ is 3.891 bits per symbol, or 63,749 bits for the whole stream, or 7,969 bytes for a stream of 16,384 characters.

The measured results:

• Arithmetic coding, adaptive: 3.898 bits per symbol. Seven thousandths of a bit above the floor.
• Huffman: 3.937. Forty-six thousandths above.
• LZSS: 2.113. Well below.
• LZ78: 3.147. Also below.

The first two are the ones the floor applies to and neither is under it. The last two are below a floor and nothing is wrong; the rest of this essay and the two after it are about why.

Why the symbol coders cannot get under it #

Huffman and arithmetic coding are both symbol-wise: each looks at one symbol, consults a probability for it, and emits accordingly. The floor for such a coder is the entropy of the distribution it consults, and it is a floor for an unimprovable reason — if a code assigned some symbols fewer bits than $-\log_2 p$ without assigning others more, the total number of distinct codewords available would exceed the number of distinct messages, and two messages would share a code.

That constraint has a name and an exact form. Kraft’s inequality: for any prefix code with lengths $\ell_i$,

$$\sum_i 2^{-\ell_i} \le 1$$

with equality when no bit pattern is wasted. Every Huffman code built here is checked against it, and the check is the most load-bearing one in the file: a sum under 1 means the code is spending bits it did not have to, and every gap-to-the-floor figure would be measuring the waste rather than the algorithm; a sum over 1 means the code is not decodable at all, and the decoder would discover it on an unlucky stream rather than on the test.

The rounding, and one symbol that gets a bargain #

The tree above is worth reading symbol by symbol, because it shows something the summary hides.

Most symbols are charged more than they are worth, which is the rounding, and it is what the 0.050-bit gap is made of. a is charged 2 for something worth 2.585 — a bargain, and h is charged 6 for something worth 6.977, a larger one.

That is the property that makes Huffman’s construction non-obvious. It is not rounding each symbol up; some symbols come out ahead and others behind, and the algorithm is optimal because the weighted total is minimal, not because any individual assignment is. A greedy rule that rounded each $-\log_2 p$ to the nearest integer would produce a code with a Kraft sum away from 1 and would be worse.

Huffman’s guarantee is that the mean sits in $[H, H+1)$: never under the entropy, never a whole bit above it. Both ends are checked in the gate, on the stream where the gap is widest, because a violation of the first would mean the entropy calculation is wrong and a violation of the second would mean the code is.

How the tree gets built, and why the greedy rule is right #

The construction is three lines and its correctness is the surprising part.

Put every symbol in a bag with its frequency as a weight. Repeatedly take the two lightest items, join them under a new node whose weight is their sum, and put that node back. When one item remains, it is the root, and each symbol’s depth is its code length.

The reason it is optimal is an exchange argument. In any optimal code the two least frequent symbols must be siblings at the deepest level — if they were not, swapping one of them with whatever is down there would not increase the total, since the deeper symbol is at least as frequent. So joining them first cannot be wrong, and the remaining problem is the same problem with one fewer symbol.

That is the whole proof, and it is worth having on the page because it is a proof about a greedy algorithm being globally optimal, which is rare enough that the ones that hold are worth collecting. This site has one other: building a heap from the bottom, where taking the cheap local step in the right order gives a linear total rather than a linearithmic one.

There is a caveat the implementation had to handle. A Huffman code is not unique. Ties in the weights can be broken either way and produce codes with the same mean length and different individual assignments. The construction here breaks ties by symbol order and by insertion index rather than by whatever the sort happens to do, so the code is the same on every machine and the figures above reproduce byte for byte — which is not an aesthetic preference on a site whose figures carry numbers in their captions.

The check that the bits are real bits #

The gate runs every coder in this file and requires each one to decode.

assertEveryCoderRoundTrips codes 2,048 symbols with the Huffman coder, the adaptive arithmetic coder, LZSS and the Burrows–Wheeler transform, then reads each back and compares against the input character by character. It is the least interesting check in the file to read and the one most likely to catch a real defect, because every plausible bug in a coder makes it emit too few bits rather than too many.

A code with a Kraft sum of 1.02 compresses better than any correct code and does not decode. A rolling model that updates before coding rather than after compresses better and does not decode. An arithmetic coder whose precision has silently overflowed compresses better and does not decode. Each of those would draw a figure showing an unusually good result, under a caption written as though it were true, and none of them would fail an assertion about bit counts.

The decoders are therefore not extras. They are the check, and they are why the coders in this file are written with both halves rather than with the half the figures use.

The floor moves, and that is the new thing #

On a uniform source the floor is 3.000 and Huffman hits it to four decimal places. On a skewed source the floor is 0.759 and Huffman spends 1.289 — 70% above it. Same coder, same guarantee, wildly different distance to the floor.

And on a source that is genuinely predictable but not skewed at all — an order-1 Markov chain whose symbols are uniform when taken one at a time — the floor as computed above is 3.000, Huffman spends 3.000, and a dictionary coder spends 1.567.

That last measurement is the one that breaks the framing, and it is worth stating flatly: the dictionary coder went to 1.567 bits per symbol on a stream whose entropy is 3.000, and Shannon was not violated. The entropy of 3.000 is the entropy of a model that looks at symbols one at a time, and the Markov source has all of its structure in its pairs. A model that looks at pairs assigns that stream an entropy of 0.936, and 1.567 is comfortably above it.

Which is why every plate here names its model #

The convention this field adopts is the one the external-memory field adopted for $B$ and $M$, and for a stronger reason. Those parameters change what a number means. This one changes what the floor is.

“This stream compresses to 2.1 bits per symbol against a floor of 3.9” is a different claim under a zeroth-order model and a third-order one, and both are true of the same stream. So every figure in this family prints the order its floor came from, and a quoted entropy without a stated model is not a quantity.

That has a consequence worth stating as bluntly as it deserves. A compressor that beats the entropy floor has not beaten Shannon. It has used a better model. Every result in this field is of that form, and the discipline is saying which model a floor belongs to.

The relationship to the floor the site already had #

The floor when the values repeat computes an entropy already, and it is important that it is not this one.

Take 256 values drawn from eight distinct ones. That essay computes 1,684 bits of permutation entropy — the floor for sorting them as though they were all distinct — and 738.7 bits of multiset entropy, which is the floor that actually applies to sorting them, and finds merge sort 2.3 times above it.

The same 256 values have a zeroth-order symbol entropy of 764.0 bits, and a Huffman coder spends 768 bits reproducing them.

Two numbers, 738.7 and 764.0, from the same data, and they are floors on different resources. The first bounds the comparisons needed to put the values in order. The second bounds the bits needed to reproduce the sequence. They are close because both are counting roughly the same information, and they are not equal because ordering a multiset is a slightly easier job than reproducing it — the sort does not need to know which of the identical values went where, and the coder does.

No compressor makes everything smaller #

There is a fourth floor available here, it needs no model at all, and it is the one that makes the model-dependence of the third floor tolerable rather than alarming.

A compressor is an injective map from inputs to outputs — injective because it must decode. There are $2^n$ strings of exactly $n$ bits and fewer than $2^{n-k+1}$ strings of at most $n-k$ bits, so at most one in $2^{k-1}$ inputs of a given length can come out $k$ bits shorter. Fewer than one in five hundred can be shortened by ten bits; fewer than one in a million by twenty.

That is a counting argument of exactly the kind this collection’s floors are made of, it applies to every compressor that has ever been written or ever will be, and it says something the entropy floor does not: compression is not a property of an algorithm, it is a transfer. Every input a compressor shortens is paid for by inputs it lengthens, and the reason a compressor is useful is that the files anybody wants to store are a vanishing subset of all files.

Set that beside the section above and the two fit together exactly. The entropy floor moves with the model because a model is a claim about which inputs are likely, and the counting floor says that any such claim must be a claim about a small set. A model that put appreciable probability on every string would predict nothing and its entropy would be the full $n$ bits; a model that puts almost all of its probability on a tiny set can have an entropy near zero, and it is wrong about everything outside that set — where the compressor duly makes the file bigger.

So “this compressor beat the entropy floor” and “this compressor makes some files bigger” are the same statement about the same choice. The dictionary coders in the plates above are not smarter than the symbol coders. They have bet on repetition, they win on streams that repeat, and on a stream of independent uniform symbols they spend more than the three bits a fixed-length code would — which the uniform plate shows without comment.

A floor on an average, and a code chosen first #

One more clause hides in the theorem and it is the one most often dropped when a compression figure is quoted about a particular file.

The entropy bounds the expected length over the distribution, for a code fixed in advance. It says nothing whatever about any individual message. Any given string of a million bits can be coded in one bit, by a code that maps that string to 1 and everything else to something longer — and such a code is perfectly decodable and perfectly useless.

Which means a compression result is only a result if the decoder is counted. A program that reproduces a specific file and contains that file is a compressor achieving zero bits of output, and the only thing wrong with it is an accounting boundary drawn in the wrong place. Every claim about compressing one file is a claim about the pair (output, decoder), and where the line falls between them is a choice somebody made.

This collection’s coders are on the right side of that line by construction rather than by promise: each is a general procedure that codes any stream over its alphabet, the decoder is the same procedure run backwards, and neither holds anything about the streams the plates are drawn on. The learning cost plate is the visible edge of the same accounting — a coder that must transmit or learn its model pays for the model, and a floor computed from a stream’s own frequencies has quietly assumed the model arrived free.

The honest form of every number in this essay is therefore conditional twice over: bits per symbol, under a stated model, with the model’s own cost measured separately and shown to amortise. Both conditions are printed on the plates, and neither is in the phrase “compresses to 2.1 bits per symbol”.

What the counter is for #

Three floors now, and the third has a property neither of the others has.

$\log_2(n!)$ is fixed by $n$. The membership bound is fixed by $n$ and $\varepsilon$. The entropy floor is fixed by a choice, and every choice gives a correct answer.

That could be read as making it weaker, and it is the reverse: it is what makes the field productive. A floor that cannot move gives an algorithm designer one number to approach and nothing else to do. A floor that moves with the model turns the whole problem into a different one — not how does a coder get closer to the floor, which arithmetic coding settled to within a hundredth of a bit, but what model puts the floor lower.

Every essay in the rest of this field is an answer to the second question. Contexts, dictionaries and transforms are three different answers, they are measured against three different floors, and each of them is correct about a stream that has not changed at all.