LZW compression: a dictionary of seen phrases

The idea: a dictionary that grows as it reads

LZW (Terry Welch, 1984, built on Lempel and Ziv's LZ78 from 1978) replaces each phrase of the input by a code: a number that points into a dictionary. The dictionary starts with the 256 single bytes (codes 0–255). Every time the encoder outputs a code, it adds one new phrase to the dictionary, so a phrase that comes back is covered by one code, and the phrases it learns get longer and longer.

The dictionary is never sent. The decoder starts with the same 256 bytes and rebuilds every entry from the codes it reads. That is the whole trick, and the reason LZW was used in Unix compress, GIF images, TIFF and early PDF.

The encoder loop

At the current position the encoder reads the longest phrase w that is already in the dictionary. The next character c is the first one that would make an unknown phrase. Then it:

1. outputs the code of w;
2. adds w + c as the next free code (256, 257, …);
3. goes on at c.

In "TOBEORNOTTOBEORTOBEORNOT" the first nine phrases are single letters, because nothing is known yet; they add TO, OB, BE, EO, OR, RN, NO, OT and TT. Then "TO" is known: the encoder outputs 256 and adds TOB as 265. Later "TOB" is known and it outputs 265 and adds TOBE. (Demos: one code at a time; TOBEORNOT….) A dictionary of growing phrases is a trie, and real encoders store it as one: each step walks one edge down.

On a run the phrases grow by one character each time: "aaaaaaaaaaaaaaaa" (16 a's) is a aa aaa aaaa aaaaa a, six codes. (Demo: aaaa….)

The decoder rebuilds the dictionary

The decoder reads a code, looks it up and writes out its phrase e. Then it adds the previous phrase + the first character of e. That is exactly the entry the encoder added one step earlier: the encoder's c was the first character of the next phrase. So the decoder's dictionary is always one entry behind the encoder's, and ends up equal to it.

Being one behind causes the one tricky case. The encoder can use an entry right after it made it. In "abababababab" the encoder adds 258 = aba and outputs 258 at once. The decoder gets 258 while its own next free code is 258: it has not made it yet. But the entry it is about to make is "previous phrase + its first character", and the previous phrase was "ab", so 258 must be "ab" + "a" = "aba".

This happens whenever the input has the shape c w c w c. Runs hit it on every code: in "aaaa…" codes 256, 257, 258 and 259 all arrive before the decoder has made them. (Demos: abab…; aaaa….)

Code width and a full dictionary

A code has to be able to name any entry, so it is wider than a byte: 9 bits for codes up to 511, then 10, 11 and at most 12 bits (4096 entries) in compress and GIF. Every input on this page stays below 512, so every code costs 9 bits.

input	raw	codes	LZW
TOBEORNOTTOBEORTOBEORNOT	192 bits	16	144 bits
abababababab	96 bits	6	54 bits
aaaaaaaaaaaaaaaa	128 bits	6	54 bits
abcdefghij	80 bits	10	90 bits
TOBEORNOT…, only 4 new codes	192 bits	20	180 bits

Without repeats every byte becomes its own 9-bit code and the output is bigger than the input (Demo: no repeats). Short inputs gain little: LZW has to see a phrase once before it can reuse it, so it needs kilobytes of text to reach its usual 40–60% of the original size.

When the dictionary is full it can no longer learn. On this page it simply freezes (Demo: dictionary full): the encoder keeps using the entries it has, and the decoder stops adding at the same point, so they still agree. compress freezes too, but watches the ratio and sends a clear code (256) to start over when it gets worse; GIF reserves 256 as clear and 257 as end of information, so its new entries start at 258.

LZW and LZ77

	LZ77 (DEFLATE, gzip)	LZW (compress, GIF)
refers to	a place in the last 32 KB: (distance, length)	an entry in a dictionary: one code
what it remembers	the raw text of the window	the phrases it has parsed, each extended by one character
a repeat of 11 bytes	one token, the first time it comes back	several codes; it only learns one more character per use
after the symbols	Huffman coding	none: fixed-width codes

LZW is simple and fast and needs no search, but it adapts slowly and has no entropy coder after it, so DEFLATE (LZ77 + Huffman) compresses better. The LZW patent (Unisys, until 2003–2004) also pushed people away from GIF and compress towards PNG and gzip. See LZ77 and DEFLATE for the window approach and Huffman Coding for the entropy coder LZW lacks.

What the page leaves out

Codes wider than 9 bits and the exact point where compress and GIF widen them (GIF switches one code "early"); the clear code and end-of-information codes and the ratio check that triggers a reset; the bit packing (GIF packs codes least-significant bit first, compress and TIFF differ); storing the dictionary as a trie or hash table of (prefix code, character) pairs; and variants such as LZMW and LZAP that add longer entries per step.

References

Welch, A Technique for High-Performance Data Compression (IEEE Computer, 1984)

Ziv and Lempel, Compression of individual sequences via variable-rate coding (IEEE Trans. Inf. Theory, 1978)

GIF89a specification, Appendix F: variable-length-code LZW compression (W3C)

Lempel–Ziv–Welch (Wikipedia)