LZ77LZ78LZW

LZ77, LZ78, and LZW are foundational lossless data compression algorithms developed by Abraham Lempel and Jacob Ziv in the 1970s. They are related in concept—each uses prior data to encode repeats—but they differ in how they represent repetition and how dictionaries or references are built and used. They have influenced many later compression schemes and have appeared in various data formats and standards.

LZ77 uses a sliding window as a search buffer and a lookahead buffer to find the longest match of the upcoming data in the already-seen portion. The encoder outputs a token that typically consists of a distance and a length pointing to a previous occurrence, and often a literal next symbol if no adequate match exists. Decoding reproduces the match by copying from the referenced position in the output stream and then appending the literal symbol when present. No explicit dictionary is transmitted; references refer to the recovered data.

LZ78 builds an explicit dictionary of previously observed strings. Each input segment is encoded as the index of the longest match in the dictionary followed by the next symbol, and the matched string is added to the dictionary. Decompression mirrors this process by extending the dictionary with new strings formed from dictionary entries and the following symbol.

LZW, introduced by Terry Welch in 1984, combines ideas from LZ78 with a continuously growing dictionary but transmits only codes representing strings. It starts with a dictionary of single-character strings and, during encoding, builds longer strings from previously seen entries. Decompression uses the same growing dictionary and a special case handles codes that reference the next new entry. LZW became widely used in formats such as GIF, subject to historical patent considerations.

Together, these algorithms illustrate distinct approaches to exploiting redundancy: sliding-window back-references, incremental dictionary construction, and code-based string representation.