The LZW algorithm
LZW is a lossless compression algorithm that replaces repeated sequences of data with short codes. Its key property: the dictionary of sequences is built during both compression and decompression, so it never has to be stored in the file.
The name
Abraham Lempel and Jacob Ziv described two dictionary compression methods in 1977 and 1978, LZ77 and LZ78. In 1984 Terry Welch simplified LZ78 into a form easy to implement in hardware and software. That became LZW, after all three authors.
The idea
The dictionary starts with every single symbol. The compressor reads the data and looks for the longest sequence already in the dictionary. It outputs that sequence's code and adds the sequence extended by the next symbol to the dictionary. The longer compression runs, the longer the sequences the dictionary knows, and the more data fits in one code.
Seven symbols became four codes. The step-by-step run is on the LZW compression and LZW decompression pages.
Why the dictionary need not be stored
The decompressor starts with the same dictionary as the compressor (single symbols) and adds entries by the same rule as it reads codes. After every step both dictionaries are identical. There is one exception: the compressor can emit a code that the decompressor only adds in that very step. That case, known as KwKwK, is covered on the decompression page.
Properties
- Lossless: decompressed data is identical to the original.
- Single pass: compression and decompression read the data once, start to finish.
- Adaptive: no prior statistics are needed; the dictionary learns them itself.
- Good for repetitive data: graphics with flat areas of color, text. Poor for photos and noise, where sequences rarely repeat.
- Bounded dictionary: in GIF at most 4096 entries (12-bit codes). When it fills up, it starts over (see LZW in GIF).
Where it is used
| Format | Notes |
|---|---|
| GIF | variable-width codes of 3..12 bits, special "clear" and "end" codes |
| TIFF | one of the compression methods, often with a differencing predictor |
| PDF, PostScript | the LZWDecode filter, now largely replaced by Deflate |
Unix compress | .Z files |
The patent
Unisys held a patent on LZW. In 1994 Unisys and CompuServe announced that software writing GIF files had to pay a license fee. In response the PNG format was created in 1995, with patent-free Deflate compression. The patent expired in the US in 2003 and in Europe and Japan in 2004. GIF has been free since then, but PNG had already replaced it in most uses other than animation.