LZ78
LZ78 is the dictionary compression algorithm proposed by Lempel and Ziv in 1978; it builds an explicit dictionary and encodes data as (dictionary index, literal) pairs.
Purpose
It achieves universal lossless compression through an explicit dictionary and is the direct predecessor of LZW.
Mechanism
Maintain a dictionary numbered from 1; while scanning the input, find the longest prefix already in the dictionary, output (index, next character), and insert that prefix plus the character into the dictionary. The dictionary is built online and never needs to be transmitted.
Use cases
- Foundation of the LZW algorithm
- General-purpose compression
- Theoretical analysis and teaching