Last modified: Thu Jul 23 15:07:09 UTC+0200 2026 © A. Tarpai
LZW decompression
The LZW decompressor is used in the GIF and TIFF decoder. The principles are perfectly explaned under Algorithm here on Wikiedia.
The beauty of LZW is that the Dictionary is build as the data is read. The Dictionary is not transferred in the compressed data. We don't have to analyze the source data before compression. As each byte read, the compressor 'remembers' strings in the Dictionary and emits codes. This the same for the decompressor: it reads a code and builds the same Dictionary. The decompressor is only one byte after the compressor:
compress decompress
X X X X X X X X -------------------> 011010011001001010101011101010 -----------------------------------> X X X X X X X X
| |
+------------+ +------------+
| | | |
+------------+ +------------+
| | | |
+------------+ +------------+
| | | |
+------------+ +------------+
| | | |
+------------+
| |
The compressor/decompressor has to only agree upon a few things to work, which also specifies variations of LZW:
- the source alphabet
- the size of the dictionary
- how codewords are packed in the compressed stream
- what special codes are
- what special codes mean
Variants of LZW
While the basic algorithm is nice and simple, problems come when certain implentations extend or change it a little, as in GIF and TIFF. For example:
- how many bits are the codewords
- endianness of codewords
- when to clear the dictionary
- and so forth
For GIF, the first codeword length is variable, while for TIFF it is always starts with 8.
... more