LZ77, every back-reference drawn.

Note

The encoder keeps a window of the most recent characters it has already written. At each position it looks for the longest string in that window that matches what comes next. If the match is at least the minimum length, it emits a pair: distance back, then length. Otherwise it emits the next character as a literal and moves on by one. The decoder needs nothing but the token stream. It copies characters from its own output, which is why the scrubber above can rebuild the text one token at a time.

Try the one-letter sample. It becomes a single literal and then a copy with distance 1 and a length far greater than 1. The source overlaps the destination, so the decoder reads characters it has only just written. Copied one at a time from left to right, this works and turns LZ77 into run-length encoding for free. A block memory copy would get it wrong, and real decoders have to special-case it.

The bit counts use a plain fixed layout so the trade-offs stay visible: one flag bit per token, eight bits per literal byte, and for a copy as many distance bits as the window needs plus eight bits of length. That makes the window slider a real cost. Widening it finds more and longer matches, but every copy pays for the larger distance field and the search compares more characters. Random letters show the floor. Almost nothing repeats, every token is a literal, and the output is one bit per character larger than the input.

Greedy parsing takes the longest match at the current position. Lazy parsing, which gzip uses, first checks whether starting one character later would give a longer match, and if so emits a literal and takes that one instead. On the Dickens sample the two give exactly the same tokens. The Pinterest sample is built to catch greedy out. At the last word it grabs "pin" and then needs a second copy for "terest". Lazy sees that "interest" starts one letter later, spends nine bits on a literal p, and comes out twelve bits ahead.

What this page leaves out is the second half of DEFLATE. Gzip does not store these tokens at fixed widths. It feeds literals, lengths and distances to Huffman coders, so a common distance costs fewer bits than a rare one. The earlier Huffman piece in this playground is that half. The search here is brute force from nearest to farthest. Real encoders hash the next three bytes and follow a chain of earlier positions with the same hash, giving up after a set number of steps.