LZ77 Compression Visualizer

Writing repeats itself. So do program files, spreadsheets, web pages and the rows of a picture. A compressor earns its keep by saying each repeated thing once and then referring to it.

The hard question is what to refer to. One answer is a dictionary agreed in advance, a list of common words that both ends keep. It works until the text is in another language, or is not text at all.

In 1977 Jacob Ziv and Abraham Lempel published a method that needs no agreed list. Their paper called it a universal algorithm for sequential data compression, and the word universal was the point: nothing about the source has to be known beforehand. The dictionary is simply whatever has already gone past.

The mechanism fits in a sentence. When the next stretch of input has been seen before, do not send it again; send two numbers instead. One says how far back the earlier copy begins. The other says how many symbols to copy. The pair amounts to the statement that each of the next so many symbols equals the symbol exactly that distance behind it.

Both ends keep only the most recent data, a few thousand bytes or a few tens of thousands. That stretch is the sliding window, and it gives the method its other name, sliding window compression. The encoder searches the window for matches. The decoder keeps the same window so that it can follow the pointers. Nothing else is shared between them.

A year later the same two authors published a second scheme that builds an explicit list of phrases as it reads. The two are known as LZ77 and LZ78, and between them they stand behind a large family of later formats. In 2004 the pair of algorithms was named an IEEE Milestone.

What the tokens look like

The 1977 article sends everything three values at a time: a distance, a length, and the one symbol that follows the match. When nothing in the window matches, the distance and length are zero and the triple carries a single new symbol. It is tidy, and it is wasteful. A symbol that matched nothing still pays for two numbers that say nothing.

In 1982 James Storer and Thomas Szymanski described compression as replacing repeated strings with pointers to a common copy, in a general model with many variants. The scheme now called LZSS takes two practical steps from that work. It puts a one bit flag in front of each item to say whether a plain byte or a pointer follows. And it leaves out any pointer that would take more room than the bytes it replaces, the break even point.

That second step matters more than it looks. Suppose the window holds 32 bytes and a match may be 3 to 18 bytes long. A pointer then needs a flag bit, five bits of distance and four of length, ten bits in all. A plain byte needs nine. A match of one byte would cost more than the byte itself, while a match of two already saves eight bits.

Here is an example you can reproduce in the tool above. Take three short sentences made of the same few words: the cat sat on the mat, the cat sat on the hat, the hat sat on the cat, each ending in a full stop. That is 71 bytes, or 568 bits. With a window of 32 bytes, a look-ahead of 16 and no pair shorter than 3, the encoder sends 18 plain bytes and 8 pairs.

Those 26 tokens come to 242 bits in the simple layout just described: eighteen literals at nine bits and eight pairs at ten. So the measured change is 568 to 242 bits, on this text, with these settings. The first sentence goes out almost byte by byte. After it, nearly everything is a copy from 24 bytes back, because each sentence is 24 bytes long. Change one word and the numbers move.

A copy that reads its own output

The oddest feature of the method is also one of the most useful. A pair may ask for more bytes than its distance. Go back four and copy ten sounds impossible, since only four bytes lie between the source and the place being written.

It works because the decoder copies one byte at a time. By the time it needs the fifth byte, it has already written the first, and that is exactly the byte the pointer now reaches. The copy feeds on its own output. In effect the instruction means: take what is there and repeat it until the length is used up. The DEFLATE specification spells out the same case. If the last two bytes decoded were X and Y, a pair with length 5 and distance 2 adds X, Y, X, Y, X. A run of ten identical bytes becomes one literal byte followed by one pair of length nine at distance one.

So an older idea, run-length encoding, which stores a repeated value once with a count, comes free with the sliding window. Take a laugh written as ha and a space, ten times over, then an exclamation mark: 30 bytes. With a look-ahead of 32 it is four literals and 1 pair that goes back three and copies 26. A decoder that copied from a saved snapshot of its output, instead of byte by byte, would get this wrong, and the tool shows that failure next to the right answer.

Greedy, or willing to wait

Which match should the encoder take? The obvious rule is greedy: at each position, take the longest match the window offers. It is not always best. Sometimes a short match now blocks a longer one that starts a byte later. The DEFLATE specification describes a remedy it calls lazy matching. After finding a match of some length, the compressor looks for a longer match starting at the next input byte. If it finds one, it cuts the first match down to a single literal byte and emits the longer match.

The zlib library’s own notes describe the same deferral and add that the process then begins again, so a real encoder may wait more than once. They also admit to a shortcut: very long search chains are cut off, so the encoder does not always find the longest possible match. Lazy matching is a rule of thumb, and on some inputs it loses. On the three cat sentences, the lazy choice spends 250 bits where greedy spends 242.

How DEFLATE finishes the job

Pointers and plain bytes are still not evenly likely. Some byte values turn up far more often than others, and short distances more often than long ones. DEFLATE, the format Phil Katz designed for the second version of his PKZIP archiver and later written down as RFC 1951, adds a second stage that spends fewer bits on the common cases.

It limits a pair to a length of 3 to 258 bytes and a distance of 1 to 32,768 bytes. Literal bytes, an end marker and the length codes share one alphabet, coded with one Huffman code; distances have a second code of their own. A decoder can keep the two apart because a distance only ever follows a length.

Each block can carry codes built for its own contents, or use a fixed code that the specification defines so that no table need be sent. In the fixed code a literal costs eight or nine bits and a distance code five, plus extra bits for the larger values. The cat example comes to 270 bits that way, more than the 242 of the plain layout, because a fixed code built for a window of 32,768 bytes has no reason to suit a window of 32.

DEFLATE is the layer underneath a good deal of everyday software. The zlib and gzip formats are thin wrappers around it that add a header and a checksum. PNG images use it, with a window of at most 32768 bytes. Browsers expose it to web pages through the Compression Standard, which is what lets this page ask the browser for a real DEFLATE stream and then read that stream back token by token. The window has grown since. Brotli, a later format built on the same combination of LZ77 and Huffman coding, allows sliding windows from about one kibibyte up to about 16 mebibytes.

What does not shrink

Everything above depends on repetition that falls inside the window. Text with no repeated string of useful length gains nothing. Every literal then carries its flag bit, and the output is longer than the input. A pangram of 37 bytes costs 333 bits as literals with flags, against 296 as it stands.

Nor can this be fixed by a better method. A simple counting argument shows that no lossless compressor can shrink every possible input: there are fewer short files than long ones, so some input must come out at least as large as it went in. The DEFLATE specification says the same and bounds its own worst case at five bytes of growth per block of roughly 32,000 bytes, by storing such a block as it is.

A sliding window also cannot see far. A repeat that lies outside the window is invisible, however exact it may be. And the method reads bytes, not meaning. Two paragraphs that say the same thing in different words share nothing it can use.

What it can do has been enough for nearly half a century. Say it once, remember a little of what you said, and point back.