LZ78
LZ78 is a lossless dictionary-coding method that represents each new phrase by an earlier phrase index and an extension symbol.
Incremental parsing extends a known phrase, including the empty phrase, by one symbol to create a new dictionary entry. The final input phrase can be incomplete and need not be new; the encoded representation must handle that ending. [1]
Unlike a distance into a sliding history window, an LZ78 reference identifies a parsed dictionary phrase. LZW adapts dictionary construction to emit string codes after initializing single-symbol entries. These methods should not be treated as interchangeable bitstream formats. [1] [2]
Relations
Limitations
- The asymptotic finite-state coding result does not promise that every finite input becomes smaller. [1]
Citations
- Ziv and Lempel (1978): Compression of Individual Sequences via Variable-Rate Coding, pp. 530-536
- Welch (1984): A Technique for High-Performance Data Compression, pp. 8-19
Further reading
Sources & caveats
- Primary-paper synthesis. DOI 10.1109/TIT.1978.1055934 identifies the 1978 paper; no compression benchmark or new implementation is claimed.