dictionarycodering

Dictionary coding, or dictionary-based coding, is a family of lossless data compression methods in which a dictionary of phrases is constructed from the input data. The encoder replaces occurrences of phrases by references to the dictionary, typically using a code that identifies a dictionary entry and may include a following symbol. The dictionary is built progressively as data are processed, and the decoder reconstructs the original stream by following the same dictionary updates in the same order. The approach exploits redundancy by reusing previously seen sequences.

The most influential forms are LZ77, LZ78, and LZW, named after their developers. LZ77 uses a sliding window to reference matches that occur in already processed data, emitting pointers and match lengths. LZ78 builds a growing dictionary of phrases and outputs a dictionary index for each input symbol, effectively encoding new phrases as pairs of (index, next symbol). LZW combines these ideas by expanding the dictionary online and transmitting codes without separators, so the decoder can update the dictionary identically. These methods are adaptive and require no fixed probability model of the data.

Dictionary coding is widely used in practical compression systems. It underpins many schemes found in software and formats, such as GIF images and the deflate family used in ZIP and PNG, often with additional entropy coding layered on top. Advantages include strong performance on repetitive data and straightforward implementation, while limitations involve memory usage and dictionary management, especially for long streams or highly random data.