The dictionary that builds itself

Every coder so far has had a probability in it somewhere. Huffman needs a frequency table; arithmetic coding needs an interval width; the context models of the previous essay need a distribution per context.

The coder that actually runs when a file is compressed has none of those. gzip, zip, PNG and every HTTP response with Content-Encoding: deflate are built on an algorithm whose whole model is one question: has this been seen before, and how far back?

What a token is #

LZSS emits a stream of two kinds of token, distinguished by a flag bit.

A literal is one flag bit plus the symbol: 9 bits, and it means “this symbol is new”.

A match is one flag bit plus an offset and a length: with a 4,096-symbol window and matches up to 18 long, that is $1 + 12 + 5 = 18$ bits, and it means “the next $\ell$ symbols are the ones that begin $d$ positions back”.

A match of 8 symbols costs 18 bits where 8 literals would have cost 72, which is where all the compression comes from. A match of 2 symbols would cost 18 bits where the literals cost 18, so the minimum match length is a threshold — 3 by default here, and in DEFLATE — below which a match is not worth emitting.

That is the whole algorithm and the whole model. There is no probability anywhere, and there is nothing that could be called an estimate of anything.

Worked, on eleven symbols #

Take abcabcabcab with a window wide enough to see all of it.

• Position 0: a is new. Literal, 9 bits.
• Position 1: b is new. Literal, 9 bits.
• Position 2: c is new. Literal, 9 bits.
• Position 3: the longest match starting here is abcabcab — eight symbols, beginning three positions back. Match, offset 3, length 8, 18 bits.

Forty-five bits for eleven symbols, against 88 for the literals alone.

The match at position 3 is worth a second look because it overlaps itself: it is eight symbols long and it refers three positions back, so it is copying from a region that the copy is still writing into. That is legal and is the standard way a run-length encoding falls out of a dictionary coder for free — a match of offset 1 and length 200 encodes two hundred copies of one symbol in eighteen bits. The decoder must copy one symbol at a time rather than block-copying, and the decoder here does, which the round-trip assertion is what checks.

And yet it is a predictor #

The previous essay’s framing survives this intact, which is the interesting part.

A coder spends $-\log_2 p$ bits on a symbol it gave probability $p$. LZSS gives the next eight symbols, jointly, a code of 18 bits — which is the same as giving that eight-symbol sequence a probability of $2^{-18}$ and every other eight-symbol sequence a share of the rest. It has predicted, and it has predicted using the only evidence it consults: that this sequence occurred recently.

Read that way the window is the model, and widening it is exactly what deepening a context model is. The context model says “the next symbol is likely given these three”; LZSS says “the next nine symbols are likely given that they appeared before”. Both are statements about repetition and neither is a statement about frequency.

The difference is what they cost. A context model of order $k$ over an alphabet of $\sigma$ needs $\sigma^k$ tables, which is why order 4 was already straining the data in the previous essay. A window of $w$ symbols needs $\log_2 w$ bits per token and no table at all — the “dictionary” is the text that has already been decoded, which both sides have.

That is why this is the algorithm that ships. Its model is free because the decoder reconstructs it as a side effect of decoding.

The window has an optimum #

The measurements across the sweep, on 16,384 symbols of text:

The minimum is at 4,096, and the largest window is worse.

The mechanism is arithmetic. A wider window finds longer matches — 9.62 symbols against 8.73 — but an offset into a 16,384-symbol window costs 14 bits where one into a 4,096-symbol window costs 12. Two extra bits on every one of 1,691 matches is 3,382 bits; the longer matches save fewer. Naming a position gets more expensive faster than the matches get longer.

That is a threshold with an optimum that can be found by sweeping it, which is exactly the shape the threshold somebody chose sets out for a library sort’s cutoffs. DEFLATE’s window is 32 KiB, and that number was chosen in 1990 against the memory of the machines of the day; whether it is optimal for any particular stream is a question with a measurable answer, and the answer is usually no.

The window can also be far too wide #

The periodic source makes the point without any interpretation needed. Its numbers are 9.000, 0.676, 0.787, 0.898, 1.009 across windows of 16 to 4,096 — a factor of thirteen between the best and the worst, on a stream where the algorithm’s behaviour changes not at all except in how many bits it spends naming positions.

Every match in it is 17.99 symbols long, which is the maximum the token format allows. Once the matches are saturated, a wider window is pure cost, and the four rightmost points are a straight line of slope $\log_2$ — one extra bit per doubling, spread over the same 910 matches.

What it does when there is nothing to find #

That figure is not a failure and it is worth being explicit about why.

No compressor can shorten every input. There are $2^n$ strings of $n$ bits and only $2^n - 1$ strings shorter than $n$ bits, so any injective encoding that shortens one input must lengthen another. A compressor is a bet that the inputs it will see are not uniform, and on an input that is uniform the bet loses by exactly the amount the bet cost.

That argument deserves to be recognised as one this site has made before. It is the counting argument of the floor under every comparison sort — there are $n!$ orderings and a decision tree of depth $d$ has $2^d$ leaves, so $d \ge \log_2(n!)$ — applied to encodings rather than to comparisons. Both are pigeonhole arguments about how many distinct outputs a procedure can produce, both are proofs about every possible algorithm rather than about any one, and both are among the small number of results in this subject that genuinely close a door.

For LZSS the cost is visible in the token format: one flag bit per token, whether or not a match is found. On a stream with no repetition that is one bit of pure overhead per symbol, plus the wasted match tokens for coincidences, and 5.111 against 2.999 is the arithmetic of that.

The gate asserts this case as well as the compressing one, because a figure that asserted “the best window beats the floor” without qualification would be asserting the pigeonhole principle away.

The other half of the algorithm, which is a search problem #

Nothing above has said how the longest match is found, and that is where a real implementation spends its time.

The implementation here searches naively: for each position, try every start in the window and keep the longest agreement. That is $\Theta(w)$ per position and it is unusable at a 32 KiB window on a real file — but it is the right choice here, because this file is measuring the code rather than the search, and a faster search finds the same matches and produces byte-identical output.

Real implementations use a hash chain: hash the next three symbols, look up a list of recent positions with that hash, and walk it. And here is the part that connects this essay back to the first half of the field — finding the longest match at a position is a text-index query. It is exactly the question the index that is the text answers, and the strongest compressors do use a suffix structure for it rather than a hash chain.

The consequence is the parameter every compression tool exposes and almost nobody reads the definition of. A compression level is a search budget. gzip -1 and gzip -9 produce output in the same format, decodable by the same decoder at the same speed; what differs is how many chain entries the encoder is willing to walk before settling for the match it has. A higher level finds longer matches, spends more time, and produces a smaller file — with no change to the model, the token format or the window.

That is a threshold family of exactly the shape the threshold somebody chose sets out, and it has the same property: the shipped values minimise nothing in particular, they were chosen against the hardware of a particular decade, and each one is a point on a curve that can be measured.

LZ78, and why the two differ #

LZSS refers back to positions. LZ78 refers back to phrases it has already named: it maintains a numbered dictionary, and each token is a dictionary index plus one new symbol, which together define a new entry.

On the text source, LZ78 spends 3.147 bits per symbol against LZSS’s 2.113, in 2,783 tokens averaging 5.89 symbols each. On the periodic source it spends 0.739 against LZSS’s 1.009 — it wins.

The reason for the split is in what each one’s cost per token does. LZSS pays $\log_2 w$ for an offset, fixed by the window. LZ78 pays $\log_2 |D|$ for an index, and the dictionary only grows — so its tokens get more expensive as the stream goes on, and it never forgets anything.

On a stream whose statistics are constant, never forgetting is an advantage and LZ78’s dictionary accumulates exactly the phrases that recur. On a stream whose statistics change, a window that forgets is the better model, because the entries LZ78 is paying index bits for are ones it will never use again.

Neither is uniformly better, and what actually ships is the first. DEFLATE, LZ4, Zstandard and Snappy are all LZ77 variants with a sliding window; LZ78’s descendant LZW survives mostly in GIF and in the compress format, both of which predate the patent expiries that let the others win.

#The optimum is a property of the text and its length together, which is easiest to see by holding the source fixed and giving the coder four times as much of it.

So the best window is not a number a coder can be shipped with. It is a number that moves with the length of what is being coded, which is why the parameter exists at all.

What the two dictionaries measure #

The LZ78 numbers are worth reading beside its phrase lengths, because they say what the dictionary has actually learned.

On the text source: 2,783 tokens for 16,384 symbols, so a mean phrase of 5.89 symbols and 2,782 dictionary entries by the end. On the periodic source: 729 tokens, a mean phrase of 22.47 symbols, and 728 entries.

The periodic case is the one that shows the mechanism. Each new entry extends an old one by a symbol, so a stream that repeats builds phrases that grow steadily longer — the dictionary is, by the end, holding entire multiples of the seventeen-symbol period. That is why LZ78 beats LZSS there despite paying a growing index: its phrases have grown past the eighteen-symbol ceiling LZSS’s token format imposes.

It is also the property that gives LZ78 its theoretical standing. The phrase length grows without bound on any stationary source, and the bits per symbol converge to the source’s entropy rate — LZ78 is asymptotically optimal for any stationary ergodic source, without being told anything about it. That is a genuinely remarkable result and it is worth stating exactly what it is not: an asymptotic statement, about the limit, with a convergence slow enough that on 16,384 symbols of text it is at 3.147 bits per symbol while the fourth-order entropy is 0.909. A limit is not a prediction applies here as sharply as anywhere on this site.

When a doubling pays, exactly #

The window’s optimum is not a shape to be found by sweeping. It is a marginal condition, and the sweep’s own columns satisfy it to the bit.

The bill is two terms. Literals cost 9 bits each and matches cost $1 + \log_2 w + 5$. At $w = 4{,}096$ that is $9 \times 118 + 18 \times 1{,}864 = 34{,}614$ bits over 16,384 symbols, which is 2.113; at $w = 16{,}384$ it is $9 \times 111 + 20 \times 1{,}691 = 34{,}819$, which is 2.125. Both measured figures, recovered exactly from the token format and the two counts.

Now differentiate. Doubling the window adds one bit to every match token and removes some matches, so the change is

$$\Delta = M_{\text{new}} - t \cdot (M_{\text{old}} - M_{\text{new}})$$

where $t$ is the bits a match token costs. A doubling pays exactly when it cuts the match count by more than $1/t$ — with $t = 18$, by more than 5.6 per cent.

That is the whole explanation of where the optimum sits. From 4,096 upward the match count falls 1,864 to 1,691 over two doublings, about 4.7 per cent each, which is just under the threshold — so the first doubling past 4,096 is very slightly a loss and every later one is a larger loss, because the reduction keeps shrinking while the bill per match keeps growing. The curve turns by six tenths of a per cent over a fourfold change in $w$, which is exactly what a marginal condition crossing zero looks like from a distance.

Two consequences worth having.

Every window has a finite optimum, always. The match count is bounded below by the number of distinct things the stream has to say, so its reduction per doubling tends to zero, while the cost per match rises by one bit per doubling without limit. The condition therefore fails eventually on any stream whatever, and the only question is where. The periodic source is that argument at its limit: its matches saturate at 910 and never fall again, so $\Delta = M$ at every step and the bill rises by exactly 910 bits a doubling — the straight line of unit slope the plate shows, which is the marginal condition with its first term set to zero.

And the threshold is set by the token format rather than by the data. A coder with a cheaper match token has a stricter condition and a smaller optimal window; one that spends more per token tolerates more matches and grows its window further. So the window and the token width are one decision rather than two, and tuning either alone is tuning half of a ratio — the same coupling choosing a growth factor finds between an allocator’s factor and its copy cost, where the parameter that looks free is bound to the one nobody swept.

It also says what the sweep is actually for. The optimum cannot be computed in advance because $M(w)$ is a property of the stream, but the condition can be checked from two adjacent points of a sweep with no third — which is a cheaper instrument than a curve and the one a deployment tuning a real compressor should reach for.

The part this file does not implement #

Real deflate does not emit the tokens above as fixed-width fields. It runs a Huffman coder over the tokens — one code for literals and match lengths, another for offsets — because the tokens themselves are not uniformly distributed: short matches are commoner than long ones, and small offsets are commoner than large ones.

That is a genuine second stage and it is worth perhaps 20–30% on top of everything measured here. It is not implemented here, and the omission is stated rather than hidden: every number on this page is for a coder with fixed-width tokens, which is a real coder and is not the one in gzip.

Both halves of that combination are on this site now, which makes the shape visible: a dictionary coder finds the repetition and a symbol coder prices what is left. The first stage changes the model; the second stage spends optimally under whatever model the first stage produced. They are not competitors and DEFLATE uses both, which is the answer to the question the last three essays have been circling — the way to compress is not to code better, since arithmetic coding settled that to within a hundredth of a bit, but to hand the coder a stream whose floor is lower.

The next essay does that a third way, with a transform that emits no bits at all.

One number is worth carrying into it. On this site’s text source the best dictionary coder reaches 2.113 bits per symbol, and the fourth-order conditional entropy of the same stream is 0.909. The dictionary coder is still more than twice its own data’s floor under a model that is not especially deep, so there is a great deal left on the table — which is exactly what the modern compressors that beat gzip by 30% are collecting, and exactly why the subject did not stop in 1990.