3.3.5 Dictionary Coding—Lempel-Ziv
Dictionary coding compresses data by substituting repeated symbol sequences with short reference codes that indicate their location in a dictionary. Unlike entropy coding, which exploits symbol probabilities, dictionary coding exploits repetition of symbol sequences. For example, a three-letter word encoded with one byte per character requires 24 bits. With 24 bits, however, we can represent 2²⁴ = 16,777,216 distinct dictionary addresses. Thus, if a language dictionary contained fewer than 16 million words, any word could be transmitted simply by sending its 24-bit dictionary index instead of its 24 bit-character sequence. In principle, a text document could be compressed by replacing each word with the binary index of its dictionary entry. If no match exists, the encoder can transmit the original word uncompressed. Even this rudimentary method would yield bit savings for typical documents where many words are reused.
Modern dictionary coders build the dictionary adaptively as data are processed. This approach, introduced independently by Abraham Lempel and Jacob Ziv, forms the basis of the LZ77 and LZ78 algorithms and their refinements such as LZW and LZSS.
To illustrate adaptive dictionary coding, consider a simplified example of the LZ78 approach. In this scheme, the encoder scans an input sequence symbol by symbol and builds a dictionary dynamically as new patterns appear. Each dictionary entry is assigned a numerical index. When a new pattern is encountered, the encoder outputs a pair consisting of the index of the longest existing prefix already in the dictionary and the next symbol that follows that prefix. The decoder reconstructs the data by repeating the same dictionary-building process.
Suppose the input message is the sequence of characters A B A B A A B B A. Initially, the dictionary is empty (except for index 0 representing the null string). The encoding process proceeds as shown in Figure 3.18.
After encoding, the output stream is the sequence of index–symbol pairs:
(0, A), (0, B), (1, B), (1, A), (2, B), (3, A).
Each output pair requires fewer bits than transmitting the raw characters individually, especially as the dictionary grows. The decoder reconstructs the sequence by initializing an identical empty dictionary and following the same steps, inserting each newly decoded string into the dictionary as it proceeds. Because both encoder and decoder build the same dictionary in the same order, lossless reconstruction is guaranteed.
This example demonstrates how dictionary-based methods exploit repetition of symbol patterns rather than probabilities of individual symbols. As the input length increases and recurring substrings appear, the average number of bits per symbol approaches the theoretical limit imposed by the source entropy.
Modern dictionary encoders derived from LZ78 include LZW and DEFLATE, which combines LZ77 sliding-window compression with Huffman entropy coding for use in ZIP and PNG file formats. These methods adapt dynamically to source statistics without requiring pre-defined dictionaries, making them widely applicable to text, images, and binary data.
Back to reading