LZ77 and LZW

Platon Karataev prays before sleep, and in the Maude translation the prayer is repeated twice in a row: “Lord Jesus Christ, holy Saint Nicholas, Frola and Lavra! Lord Jesus Christ, holy Saint Nicholas, Frola and Lavra!” An LZ77 packer writes it like this: Lord Jesus Christ, holy Saint Nic<14,3>as, Fr<8,3> and Lavra! <57,56>. The first half is letters as they are, with two short references back. The whole second half is one reference: go back 57 bytes and copy 56. A repeat costs almost nothing, and a new letter eight or nine bits. Below this can be seen on Part One of War and Peace in the original Russian: each letter is coloured by how many bits it costs in a real DEFLATE block.

No highlight means almost free. Names, forms of address, words that were already on the previous page cost one or two bits per letter: they fall into long references. The brightest is a Cyrillic letter written literally: two bytes of UTF-8 at eight or nine bits each, about 17 bits per letter. The strip below shows the whole text: at the start it is expensive, as the window has nothing in it yet and there is nothing to refer to, and further on it gets cheaper. Switch the level and the window. With a 4 KiB window Part One costs 5.78 bits per letter, with the 32 KiB DEFLATE window 4.67, with a 256 KiB window 4.11: distant repeats are repeats too, but a small window does not see them.

The idea

If a piece of data has been seen before, a reference can be written instead: how many bytes to go back and how many to copy. The decompressor simply copies; it does not need to think. All the work is the packer’s: at each position find the longest repeat in the window, the last few tens of kilobytes. Searching by brute force is expensive, so real packers keep an index by the first three bytes and check only the places that start the same way. How many such places to check is exactly the “compression level”.

References, the triples “back, how many, next character” and a simple search over a dictionary of triples are covered in the course chapter on compression. Here: how the search works in zlib, the library behind gzip, PNG and web page compression, why compression levels behave the way they do, and what an LZW dictionary should do when it is full.

Hash chains

zlib keeps two arrays. head[h] is the last place where a triple of bytes with hash h started. prev[i] is the previous place with the same hash as position i. Together they form, for each triple, a hash chain: from the most recent occurrence to older ones. Insertion is two writes into the arrays per byte, with no deletion at all: positions that have left the window simply stop being checked. The hash is computed as a rolling one, as in Rabin and Karp, as a comment in zlib’s source says, and takes 15 bits by default.

In the listing below the hash table is a dictionary over the exact three bytes, without collisions; in zlib a triple is folded into 15 bits, and other triples occasionally get into a chain, to be weeded out later by comparison. Tap a letter:

For “Antichrist” in its second mention the chain is short, and the best candidate is the first mention three dozen bytes earlier. Now switch to DNA. There are only 64 different triples of four letters, and each occurs on average every 64 bytes: in a 32 KiB window the chains grow to hundreds of links. The matches are short, because DNA hardly repeats. Level 9 honestly goes through up to 4096 links and gains almost nothing. The measurement below will confirm it: on a phage genome level 9 works dozens of times longer than level 1.

Lazy matching and levels

A greedy packer takes the longest repeat at the current position. But it happens that it finds, say, three bytes, while a repeat of twenty starts at the next position: by taking the short reference it swallows it. Lazy matching defers the decision by a step: having found a repeat at position i, look at what i + 1 gives. If it is longer there, a single letter is output at i, and everything repeats. zlib’s source says the idea belongs to Jan-Mark Wams and that the authors found it in the freeze packer by Leonid Broukhis.

A compression level in zlib is four numbers from the table configuration_table in deflate.c:

There are small rules too: at the lazy levels a three-byte repeat more than 4096 bytes back is discarded, since a reference to it costs more than three letters. The listing below repeats this logic for levels 1, 6 and 9.

Code

An LZ77 packer with hash chains and lazy parsing, a decompressor, and a computation of the size of a DEFLATE block with fixed Huffman codes, the ones set in the standard once and for all, without tables at the start of the block. Real zlib builds its own codes for each block from the frequencies, as in the article on Huffman coding, and comes out smaller still; its parsing into letters and references is the same.

On the first thirty thousand letters of the novel (51,749 bytes) level 1 went through 33,575 chain links and output 26,024 bytes. Level 6 went through 18 times as many links and compressed 27% harder: the references became longer on average, 8.4 bytes instead of 5.1, and fewer of them were needed. Level 9 doubled the work again and gained another one and a half per cent. This is the usual picture: the first steps of the search pay off, and after that each next one brings less and less.

The window

A reference in DEFLATE reaches at most 32 KiB back: that is how the format is defined, the distance is encoded as a number up to 32,768. zlib leaves room for the read buffer and refers at most 32,506 bytes back. Everything farther away is as if never seen, for the packer. The scene at the start of the article shows what this costs on Part One of the novel: with a 4 KiB window, 5.78 bits per letter, with the DEFLATE window 4.67, with a 256 KiB window 4.11. The characters’ names and turns of phrase repeat at the distance of chapters, not paragraphs.

So the descendants of DEFLATE widened the window first of all: in Brotli it is up to 16 MiB (RFC 7932), and zstd and xz allow megabytes and more. A large window is paid for with the memory of the packer and decompressor and with longer chains; it is one more knob that the compression level turns.

What it costs

Insertion into a chain is O(1) per byte. The search at a position is at most chain links, each with a comparison of up to 258 bytes, so the worst case is O(n · chain · 258), while on ordinary data the comparison almost always breaks off at the very first byte: zlib, like the listing, first checks the byte that would make the match longer than the one found. Decompression is O(n) and does not depend on the level: the decompressor searches for nothing. The measurement is real zlib in Python and the Go standard library’s own DEFLATE on four kinds of data: Part One of the novel, the source code of this catalogue’s scenes, a table of earthquakes and the genome of the phage lambda.

On prose level 9 in Python is twelve times slower than level 1 and gives 28.6% of the original size instead of 38.9%. Almost the whole gain is collected by level 6, and the last levels cost a lot. On DNA the picture is worse: level 9 is thirty times slower than level 1 and compresses only from 33.0 to 29.6%, and on this genome level 6 is even slightly better than level 9. The reason is the chains: four letters give only 64 triples, the chains are long, the matches short, and level 9 dutifully goes through up to 4096 links in vain. Go is built differently, with its own implementation and its own level parameters, but the overall shape is the same.

LZW: a dictionary instead of a window

LZW does not refer back. It keeps a dictionary of phrases: at the start, 256 single bytes, and then each phrase output, extended by the next byte, becomes a new phrase with a new number. The decompressor builds the same dictionary itself, so it need not be transmitted. Numbers are written with 9 bits at first, then 10, 11 and so on up to a limit: 12 bits in GIF, 16 by default in the compress program. How the dictionary grows on a tongue-twister and how the story of the LZW patent ended is told in the course chapter. Here: what to do when the dictionary is full.

There are three options. You can freeze the dictionary and go on using what is there: the GIF specification requires the decompressor not to change a full dictionary until a reset code arrives. You can reset it as soon as it fills up. Or you can, like compress, keep the full dictionary but check the compression ratio every 10,000 bytes and reset the dictionary if it has dropped. The difference shows on a file that changes in the middle, say, an archive where text lies after a genome:

A twelve-bit dictionary frozen on the genome turns the whole Russian text into codes of one byte each: each byte becomes a 12-bit code, and the file comes out bigger than the original, almost 11 bits per byte. Resetting when full saves the day: 3.19 bits per byte. Resetting when the ratio drops, as in compress, is better still, 3.01: the dictionary lives while it is useful. With 16 bits the dictionary holds almost all of Part One, and the compression is 2.63 bits per byte.

History

Jacob Ziv and Abraham Lempel published LZ77 in 1977, and a year later LZ78, with a dictionary of phrases instead of a window. In 1982 James Storer and Thomas Szymanski noticed that there is no need to append the next character to every reference; a flag “letter or reference” is enough, and almost all descendants of LZ77 work this way. In 1984 Terry Welch simplified LZ78 to LZW, and soon the compress program appeared on its basis; among its authors named in the source are Spencer Thomas, James Woods and Joe Orost. DEFLATE was devised by Phil Katz for PKZIP, and in 1996 Peter Deutsch described it in RFC 1951. Its most widespread implementation, zlib, was written by Jean-loup Gailly and Mark Adler. A comment in zlib’s code says that a former version of this file searched for repeats with the more complex algorithm of Fiala and Greene, linear but slower on average, memory-hungry and patented; it was abandoned in favour of hash chains.

Problems

In the first problem you have to decompress LZW with dictionary resets and not trip over a number that does not exist yet. In the second, compute the Lempel–Ziv complexity of a string, the very measure of 1976 that LZ77 grew out of, quickly, with a suffix array.