LZW
LZW is a lossless dictionary-coding method that replaces input strings with codes while the encoder and decoder reconstruct matching dictionaries.
The initial dictionary contains single-symbol strings. Encoding emits a code for the longest recognized string and adds that string extended by the next symbol; the extension symbol also starts the next parsing step. [1] [3]
A decoder derives new entries from prior output rather than receiving a complete learned dictionary separately. It must still follow the format's initialization, code-width, reset and packing rules. [1] [2] [3]
GIF packs codes least-significant-bit first. At a full table, clearing can be deferred: the decoder keeps the table unchanged until a Clear code arrives. Its End of Information code and data-sub-block terminator serve different layers. [2]
TIFF 6.0 packs LZW codes high-to-low regardless of TIFF byte order, restarts each strip and changes code width earlier than GIF. A GIF decoder is not a TIFF decoder merely by reversing bit order; the optional differencing predictor is a separate transform. [3] [2]
Relations
Citations
- Welch (1984): A Technique for High-Performance Data Compression, pp. 8-19
- CompuServe GIF89a: Appendix F and deferred-clear clarification
- Aldus TIFF Revision 6.0 (1992): sections 13-14, LZW compression and differencing predictor
Further reading
Sources & caveats
- Algorithm and format synthesis, not a decoder conformance test. Welch's paper is DOI 10.1109/MC.1984.1659158; GIF89a and TIFF 6.0 are separate contracts.