Most Compressors Stop Learning

Every compressor is up against a floor. Shannon showed that text from a random source can't be squeezed below its entropy, on average, no matter how clever you are. The textbook result for gzip's family of compressors is that they're universal: given enough data, they get down to that floor on any source, without being told anything about it.

"Given enough data" is doing a lot of work in that sentence. For real text you can't check how close a compressor gets, because nobody knows the entropy of English. But you can make up a random source where you know the entropy exactly, generate text from it, and measure how far above the floor each compressor lands, and how that gap shrinks as the text gets longer.

So I did that for gzip, bzip2, xz and zstd, each at its strongest setting, on six sources and up to 16 million characters. The short answer: gzip and bzip2 stop improving after about a megabyte and sit 14–60% above the floor forever. xz keeps improving, but slowly enough that the numbers are a little absurd. And a twenty-line counting model beats all four by a mile, as long as you tell it one thing.

The sources

Each source writes one letter per byte, which is wasteful on purpose: there's slack for the compressor to take up. The first three have no memory. Every letter is drawn fresh from a fixed set of odds: a fair coin (exactly 1 bit per letter), a 90/10 coin (0.47 bits), and 26 letters with uneven odds like a long-tailed word list (3.93 bits).

The other three have memory. The odds for the next letter depend on the last one, two or three letters, and each of those contexts gets its own random table of odds. "Memory 1" over 8 letters has 8 tables; "memory 2" over 26 letters has 676, which is a crude imitation of how English spelling depends on the letters just before. For a source like that, the entropy is the average uncertainty of the next letter given the ones before it, weighted by how often each context comes up. It takes a few lines to compute exactly.

Before trusting any of it I checked the generator: scoring the text with the true odds that made it gives the entropy back, to within 0.1% at a million letters on every source. The browser version and the one I ran the big batch with agree on the entropy to 13 decimal places.

What they managed

Size above the entropy floor at 16 million symbols, measured against what the true odds pay on the same text. gzip -9, bzip2 -9, xz preset 9, zstd level 19, headers and checksums stripped where the format allows. Counting model: ideal code length, which an arithmetic coder gets within a couple of bits of.

gzip and bzip2 forget

Look at the gzip and bzip2 lines in the chart: by a megabyte they're flat. gzip at one megabyte and at sixteen differ by less than a percentage point on every source. That's by design. gzip only looks back 32 KB for repeats, and bzip2 works in blocks of 900 KB and starts each block from scratch. Once they've seen a window's worth of text, more text teaches them nothing. Universal compression needs an unbounded memory, and these two bounded theirs on purpose, for speed and for streaming.

xz keeps learning, very slowly

xz is the one compressor here whose window (64 MB at its top setting) is bigger than the whole text, so it's the closest to the textbook. On the three sources with memory it does keep improving, all the way to 16 million. But look at how. On "8 symbols, memory 1", the gap above the floor times the number of doublings of text (log₂ n) is almost exactly constant from a million symbols on:

Gap in bits per symbol, xz preset 9, average of three samples.

So the gap shrinks like 1/log n, which is roughly the speed theory gives for this family of compressors. Doubling the text, from a million to two million symbols, cuts the gap by 5%. To get from 14% above the floor down to 1%, you'd need log₂ n ≈ 346, about 10¹⁰⁴ symbols. The observable universe has around 10⁸⁰ atoms. That's an extrapolation, and the other two memory sources drift a bit below the 1/log n line, so take the exponent loosely. But nothing in these curves looks like it gets to the floor in any amount of text that exists.

On the source with no memory at all, xz gets worse as it sees more: 3.9% above the floor at 256k symbols, 4.9% at 16 million. With a bigger window there are more accidental repeats to find, and every one it uses is a coincidence it pays to describe. On a fresh 16-million-symbol sample, xz with its window cut to 32 KB lands 4.0% above the floor; with the full window, 4.9%. On text with no memory, remembering more is pure cost.

zstd is the odd one out in the other direction. It codes each letter that isn't part of a repeat with a table built from the letter counts, so on the fair coin and the 26 letters with no memory, it gets within 1%. (Not the 90/10 coin: a table like that spends at least a whole bit per letter, and that coin carries less than half a bit.) But where it has to learn context, it does no better than xz.

The counting model, and the one thing it needs

The blue line is a model you can write in twenty lines. For each context (the last k letters), it keeps a count of what came next, and predicts the next letter in proportion to those counts, plus a half for every letter so nothing is ever impossible. Each prediction turns into bits with an arithmetic coder. It's a standard estimator from the 1980s (Krichevsky–Trofimov), and it gets within 1% of the floor after 16 thousand symbols on "memory 1" and within 0.01% by 16 million. You can watch it do that in the chart at the top.

The catch is that I told it k. Give it the wrong amount of memory and it falls apart in both directions:

Counting model with a fixed amount of memory, above the floor at one million symbols. Bold is the right amount.

Too little memory and it can never learn the structure: 51–110% above the floor, worse than gzip. Too much and it spreads the same text across too many contexts, each of which has to be learned separately: on the 26-letter source, memory 3 has 17,576 contexts and is still 11% above the floor at a million symbols. Knowing the right amount of context is most of the battle, and a general-purpose compressor doesn't get told.

bzip2 is the interesting middle case. Its core trick, the Burrows–Wheeler transform, sorts the text by what follows each position, which groups letters with the same context together. That's a context model in disguise, and on the 26-letter, memory 2 source it's the best of the four real compressors at 23%, ahead of xz at 34%. Its 900 KB blocks are what stop it going further.

What I take from it

"Universal" is a statement about the limit, and the limit is a long way off. On the textbook kind of source, the gap for the best of these closes like 1/log n, which in practice means it doesn't close. Real compressors get their wins elsewhere: long exact repeats, which real files are full of and these sources never have. Random text with memory is close to their worst case, and that's the point of using it: it shows what they can't learn rather than what they can copy.

Compressors that do learn context, the PPM and context-mixing families, work by blending counting models with several amounts of memory and letting the data pick the mix. That's the obvious next experiment.

The sources, entropy and counting model are in one small file. The big runs used three samples per source, 16 million symbols each, with the same models in Python and each compressor at its strongest standard setting.