LZ78

LZ78 is a lossless data compression algorithm introduced by Abraham Lempel and Jacob Ziv in 1978 as part of the LZ family. It is a dictionary-based method that builds a dynamically growing dictionary of substrings (phrases) found in the input stream as it is processed.

Encoding and decoding are performed in tandem. The encoder searches for the longest substring of the input that already exists in the dictionary and outputs a pair consisting of the code for that substring and the next symbol that follows it. The encoder then adds a new dictionary entry formed by the matched substring plus that next symbol. The decoder mirrors this process: for each encoded pair (code, symbol), it outputs the dictionary entry corresponding to code concatenated with symbol and adds this new string to the dictionary. Initially the dictionary contains the individual symbols from the input alphabet.

The encoded stream is a sequence of pairs, with the dictionary entries assigned codes in the order they are created. As the dictionary grows, the number of bits required to represent codes can increase, so practical implementations often use variable-length codes or predefined code widths.

LZ78 is one of the earliest practical Lempel-Ziv algorithms and influenced subsequent variants such as LZW (Lempel-Ziv-Welch). Compared with later schemes, LZ78 relies on explicit dictionary entries and their indices in the output, which can lead to large code lengths for data with many unique substrings but can be effective for data with recurring phrases.

Applications and influence: LZ78 laid the groundwork for many dictionary-based compressors and helped shape the design principles of later methods used in various archival and communication systems.