LZ77 and LZ78 Compression

LZ77 and LZ78 are two foundational lossless data compression algorithms published in 1977 and 1978 by Abraham Lempel and Jacob Ziv. They operate by replacing repeated occurrences of data sequences with references to a single copy of that sequence existing earlier in the uncompressed data stream. This approach, known as dictionary coding or textual substitution, forms the basis for the vast majority of general-purpose data compression tools used in modern computing.^[28]

Prior to the introduction of these algorithms, data compression largely relied on statistical methods like Huffman coding, which required prior knowledge of the data probabilities or necessitated two passes over the file. Lempel and Ziv introduced a universal approach that adapts dynamically to the data as it is processed. By building a dictionary of sequences on the fly, their algorithms achieve near-optimal compression ratios for any stationary ergodic source without requiring a pre-calculated probability model.

The historical impact of LZ77 and LZ78 is massive. They spawned a large family of derivative algorithms, including LZW, LZSS, DEFLATE, LZMA, LZ4, and Zstandard. These derivatives are the underlying mechanisms for ubiquitous file formats and protocols, ranging from ZIP archives and PNG images to HTTP web traffic compression and transparent file system compression. The theoretical framework and practical implementations of the Lempel and Ziv algorithms remain central to computer science and information theory.

Definition and Problem Statement

Lossless data compression is the process of encoding information using fewer bits than the original representation, with the strict requirement that the exact original data can be perfectly reconstructed from the compressed data. This contrasts with lossy compression, which discards some data to achieve smaller file sizes, a technique acceptable for audio or video but catastrophic for text documents or executable binaries.

The core problem in lossless compression is identifying and exploiting redundancy within a data stream. In the decades following Claude Shannon's formalization of information theory in his 1948 paper "A Mathematical Theory of Communication"^[1], researchers sought efficient ways to approach the Shannon entropy limit. Shannon entropy defines the theoretical maximum compression possible for a given data source based on the probability of its symbols.^[29] Early solutions, such as Shannon-Fano coding and Huffman coding, assigned variable-length codes to individual symbols based on their frequency of occurrence. Frequent symbols received short codes, while rare symbols received long codes.

However, these statistical methods suffered from a significant limitation. They required a probability model of the input data. To compress a file optimally using pure Huffman coding, the compressor either needed a pre-agreed dictionary of probabilities, which was inflexible, or it had to read the entire file first to count symbol frequencies, construct a tree, and prepend this tree to the compressed file. This two-pass requirement made streaming compression difficult and added overhead to small files. Furthermore, basic Huffman coding only compressed individual symbols, failing to capture higher-order redundancies like repeated multi-character words or phrases unless complex and memory-intensive Markov models were employed.

The theoretical limits of compression are also described by Kolmogorov complexity, a concept formalized in algorithmic information theory. As detailed in the Stanford Encyclopedia of Philosophy^[2], the Kolmogorov complexity of a string is the length of the shortest possible computer program that can output that string. While Kolmogorov complexity represents the absolute mathematical limit of data compression, it is a proven uncomputable function. Therefore, practical compression algorithms must rely on heuristic approximations to find patterns and reduce the representation of the data.

Lempel and Ziv sought a universal source coding algorithm to approximate these limits practically. A universal algorithm does not require prior knowledge of the statistical properties of the source data. Instead, it learns the properties of the data dynamically as it reads the stream. The specific mechanism they formalized to solve this problem is textual substitution. Instead of encoding single symbols based on frequency, textual substitution algorithms encode entire sequences of symbols by pointing to previous instances of the exact same sequence. If the string "compression" appears multiple times in a document, the algorithm stores the text once and replaces subsequent occurrences with a short reference, such as a pointer indicating a backward distance and a length. This approach naturally captures higher-order redundancies, such as common words, phrases, or repeating binary patterns, which single-symbol statistical coders miss.

Discovery and History

The algorithms were developed at the Technion, the Israel Institute of Technology in Haifa, by two researchers: Jacob Ziv, an electrical engineer, and Abraham Lempel, a computer scientist. Their collaboration merged rigorous information theory with practical algorithmic design, creating a paradigm shift in how computers handle data storage and transmission. During the 1970s, computer memory was extremely expensive and network bandwidth was severely limited, making the need for efficient, low-memory compression paramount.

In May 1977, Ziv and Lempel published their first major paper on the subject, titled "A Universal Algorithm for Sequential Data Compression"^[3], in the IEEE Transactions on Information Theory. This paper introduced the algorithm that would become known as LZ77. The authors demonstrated mathematically that their sequential algorithm could achieve a compression ratio that uniformly approaches the lower bounds of compression attainable by any block-to-variable-length coding scheme. This proved its asymptotic optimality for any stationary ergodic source. A stationary ergodic source is a statistical model of data where the statistical properties do not change over time and where the behavior of a single long sequence represents the behavior of the entire model. The finding that a single-pass algorithm could reach this theoretical limit was later expanded upon in the 1994 paper "The sliding-window Lempel-Ziv algorithm is asymptotically optimal"^[4].^[30]

The following year, in September 1978, they published a second paper in the same journal, titled "Compression of Individual Sequences via Variable-Rate Coding"^[5]. This paper introduced LZ78. While LZ77 used a sliding window of recently processed data to find matches, LZ78 took a different approach by constructing an explicit, ever-growing dictionary of previously seen phrases.

The publication of these two papers shifted the direction of data compression research. Prior art in textual substitution existed in various niche applications, but Ziv and Lempel provided the first rigorous mathematical foundation proving that such adaptive dictionary methods were universally optimal. Their work showed that a single-pass algorithm could match the theoretical limits of compression without needing a prior statistical model.

In recognition of their contribution, the Institute of Electrical and Electronics Engineers dedicated a Milestone plaque for Lempel-Ziv Data Compression in 2004^[6], located at the Technion. The IEEE noted that the algorithms paved the way for efficient data transmission over the internet and became the basis for formats like GIF, PNG, and ZIP. Both authors received numerous accolades for their work. Jacob Ziv did not receive the National Medal of Science in 2007 (it was awarded to Andrew Viterbi); Ziv received other awards such as the IEEE Medal of Honor in 2021^[7]. Abraham Lempel went on to found HP Labs Israel and continued to contribute to computer science until his passing, leaving behind a legacy that fundamentally shaped the digital age.

How LZ77 Works

LZ77 achieves compression by using a sliding window over the input data stream. The algorithm replaces repeated sequences of characters with a reference to a previous occurrence of that sequence within the window.

The sliding window is conceptually divided into two parts. The first part is the search buffer, which contains the data that has already been read and compressed. The second part is the lookahead buffer, which contains the upcoming data that needs to be compressed. As the algorithm processes the data, the window slides forward, moving characters from the lookahead buffer into the search buffer, and dropping the oldest characters from the back of the search buffer.

At each step, the algorithm searches the search buffer for the longest sequence of characters that perfectly matches the prefix of the lookahead buffer. When a match is found, the algorithm outputs a token consisting of three elements:

1. The distance (or offset) from the current position back to the start of the match in the search buffer.
2. The length of the match.
3. The next symbol in the lookahead buffer immediately following the match.

If no match is found, the distance and length are set to zero, and the token simply contains the uncompressed literal symbol. Including the next symbol in every token ensures that the algorithm can always make progress, even when encountering entirely new characters.

Consider the compression of the string "abracadabra" with a small sliding window.

1. The algorithm starts at index 0. The search buffer is empty. The lookahead buffer contains "abracadabra".
2. The algorithm looks for "a" in the search buffer. No match is found. It outputs the literal "a" (represented as a token with zero distance and zero length, followed by "a"). The window slides forward by one.
3. The search buffer contains "a". The lookahead buffer contains "bracadabra". The algorithm looks for "b". No match. It outputs the literal "b". The window slides forward.
4. The search buffer contains "ab". The lookahead buffer contains "racadabra". The algorithm looks for "r". No match. It outputs the literal "r". The window slides forward.
5. The search buffer contains "abr". The lookahead buffer contains "acadabra". The algorithm looks for "a". It finds a match at a distance of 3. However, the next character in the lookahead is "c", which does not match the "b" in the search buffer. The match length is 1. The algorithm outputs a token indicating a distance of 3, a length of 1, and the next symbol "c". The window slides forward by 2.
6. The search buffer contains "abrac". The lookahead buffer contains "adabra". The algorithm looks for "a". It finds a match at distance 2 (the second "a"). The next character is "d". It outputs distance 2, length 1, next symbol "d".
7. The search buffer contains "abracad". The lookahead buffer contains "abra". The algorithm looks for "a". It finds a match at distance 7 (the first "a"). It checks the next characters. "b" matches "b". "r" matches "r". "a" matches "a". The entire string "abra" matches a previous occurrence. The algorithm outputs a token indicating a distance of 7, a length of 4, and a null or end-of-file symbol.

A notable feature of LZ77 is that the match length can exceed the distance. This occurs when the matching sequence overlaps with the lookahead buffer. During decompression, the decoder simply copies bytes one by one from the specified distance. If the length exceeds the distance, the decoder will end up copying bytes it just wrote, effectively replicating a repeating pattern like "ABABAB" using a single short token. This overlapping capability allows LZ77 to efficiently encode run-length data.

The time complexity of a naive LZ77 implementation is O(n * W), where n is the length of the input data and W is the size of the sliding window, because finding the longest match requires scanning the entire search buffer. However, modern implementations use advanced data structures to find matches. As detailed in the 1981 paper "Linear Algorithm for Data Compression via String Matching"^[8], using a suffix tree reduces the time complexity for string matching to O(n). Hash chains are also commonly used in practical implementations to achieve near-linear time by mapping short sequences of bytes to their previous locations in the window. The space complexity is O(W) to store the sliding window and the associated search data structures. Because W is typically a fixed constant (for example, 32 kilobytes in standard DEFLATE), the space requirement is strictly bounded, making LZ77 highly suitable for streaming data.^[31]

How LZ78 Works

While LZ77 relies on a spatial sliding window, LZ78 relies on a logical dictionary.^[32] LZ78 parses the input data stream into distinct phrases and builds a dictionary of these phrases as it goes.

The algorithm starts with an empty dictionary (or a dictionary containing only a null string at index zero). It reads symbols from the input stream and accumulates them into a current string. It continues appending symbols to the current string as long as the resulting string already exists in the dictionary.

When the addition of a new symbol creates a string that is not in the dictionary, the algorithm stops. It then outputs a token consisting of two elements:

1. The dictionary index of the longest matching prefix (the string without the newly added symbol).
2. The newly added symbol that caused the string to be unique.

After outputting the token, the algorithm adds this new, unique string to the next available index in the dictionary. It then resets the current string and begins reading the next symbols from the input.

For example, if the input is "ABBCBCB", the algorithm processes it as follows:

1. The algorithm reads "A". The current string "A" is not in the dictionary. It outputs the token (0, 'A'), where 0 represents the empty prefix. It adds "A" to the dictionary at index 1.
2. The algorithm reads "B". The current string "B" is not in the dictionary. It outputs the token (0, 'B'). It adds "B" to the dictionary at index 2.
3. The algorithm reads "B". The string "B" is already in the dictionary at index 2. It reads the next character, "C". The current string becomes "BC". "BC" is not in the dictionary. It outputs the token (2, 'C'), pointing to the prefix "B" at index 2 and adding the new character "C". It adds "BC" to the dictionary at index 3.
4. The algorithm reads "B". "B" is at index 2. It reads "C". "BC" is at index 3. It reads "B". The current string becomes "BCB". "BCB" is not in the dictionary. It outputs the token (3, 'B'), pointing to the prefix "BC" at index 3 and adding the new character "B". It adds "BCB" to the dictionary at index 4.

By the end of this short sequence, the dictionary contains "A", "B", "BC", and "BCB". If the sequence were to continue with another "BCB", the algorithm would match the entire three-character phrase in a single step, demonstrating how the dictionary adapts to capture increasingly longer repeating patterns.

The time complexity of LZ78 is O(n) if the dictionary is implemented using a Trie (prefix tree), where each node represents a character and paths from the root represent phrases. The algorithm simply walks down the Trie as it reads characters, taking O(1) time per character. The space complexity is O(D), where D is the maximum allowed size of the dictionary.

Unlike LZ77, which forgets data once it falls out of the sliding window, LZ78 remembers phrases indefinitely, provided the dictionary has enough memory. However, practical implementations must handle the case where the dictionary fills up. Strategies include freezing the dictionary and continuing with existing phrases, clearing it entirely and starting over, or using a least-recently-used eviction policy. Each strategy presents different tradeoffs between compression ratio and memory consumption.

Important Variants and Refinements

The original LZ77 and LZ78 algorithms provided the theoretical foundation, but they contained inefficiencies that were resolved by subsequent researchers. These refinements created the practical algorithms used today.

LZSS (Lempel-Ziv-Storer-Szymanski)

In 1982, James Storer and Thomas Szymanski published "Data compression via textual substitution"^[9] in the Journal of the ACM. They identified a flaw in LZ77: outputting a three-part token is inefficient when no match is found, as it forces the encoder to use multiple bits to encode a zero distance, a zero length, and a single character. LZSS introduced a one-bit flag to distinguish between literal characters and match references. If the flag is 0, the next data is a literal byte. If the flag is 1, the next data is a (distance, length) pair. This modification eliminated the next_symbol from the token, significantly improving compression ratios. Almost all modern LZ77 derivatives actually use the LZSS token structure.

LZW (Lempel-Ziv-Welch) and the Patent Controversy

In 1984, Terry Welch, working at the Sperry Research Center, published "A Technique for High-Performance Data Compression"^[10] in IEEE Computer. Welch modified LZ78 to eliminate the explicit output of the next_symbol. LZW initializes the dictionary with all 256 possible single-byte characters. Because every single character is already in the dictionary, the algorithm never encounters a completely unknown symbol. Consequently, the encoder only needs to output the dictionary index of the matched phrase. The decoder, knowing the initialization state and the deterministic rules for adding new phrases, can perfectly reconstruct the dictionary on the fly.

LZW became highly popular due to its simplicity and speed, and was patented under US Patent 4558302A^[11]. This patent led to a significant historical controversy. In the late 1980s, CompuServe designed the Graphics Interchange Format (GIF) using LZW compression, unaware of the patent. In 1994, Unisys, the company that acquired Sperry, announced it would enforce the patent and demand royalties from software developers implementing GIF. As documented by the Free Software Foundation^[12], this sparked outrage in the open-source and web communities. The threat of litigation directly motivated the creation of the Portable Network Graphics (PNG) format, which utilized the unpatented DEFLATE algorithm. The LZW patents eventually expired between 2003 and 2004, but the event permanently shaped the development of open web standards.

DEFLATE

Developed by Phil Katz in the early 1990s for the PKZIP utility, DEFLATE is a hybrid algorithm.^[32] It first applies the LZSS variant of LZ77 to replace duplicate strings with distance and length pairs. It then applies Huffman coding to the resulting sequence of literals, distances, and lengths. By combining dictionary compression (which handles repeating strings) with entropy coding (which handles the uneven frequency of the resulting tokens), DEFLATE achieves excellent compression. It was formalized in 1996 as RFC 1951^[13].

LZMA (Lempel-Ziv-Markov chain algorithm)

LZMA was developed by Igor Pavlov starting in 1998, but the 7-Zip archiver was not released until 1999. LZMA is a highly optimized LZ77 derivative. As documented in the LZMA SDK^[14], it uses massive sliding windows (up to 4 gigabytes) and encodes the LZ77 output using a computationally intensive range coder (a type of arithmetic coding) combined with a Markov chain model. The Markov model predicts the probability of each bit based on the context of previous bits, allowing LZMA to compress data much more densely than DEFLATE, at the cost of significantly higher CPU and memory usage during compression.

Modern Fast LZ Algorithms

In the 2010s, the focus shifted toward algorithms optimized for modern CPU architectures, prioritizing extreme speed over maximum compression.

• LZ4: Released by Yann Collet in 2011, LZ4^[15] is a byte-oriented LZ77 derivative that omits the entropy coding stage entirely. By formatting tokens to align with byte boundaries, LZ4 achieves decompression speeds exceeding several gigabytes per second per CPU core, making it ideal for real-time applications.
• Zstandard (zstd): Also developed by Yann Collet and published as RFC 8878^[16], Zstandard combines a large-window LZ77 approach with Finite State Entropy, a fast implementation of Asymmetric Numeral Systems^[17]. Asymmetric Numeral Systems combine the execution speed of Huffman coding with the precise fractional-bit compression ratios of arithmetic coding. Zstandard offers compression ratios comparable to DEFLATE but at much higher speeds.
• Brotli: Developed by Jyrki Alakuijala and Zoltan Szabadka at Google and published as RFC 7932^[18], Brotli combines LZ77, Huffman coding, and second-order context modeling. It also includes a static dictionary of over 13,000 common words and phrases used in web documents, making it exceptionally effective for compressing HTML, CSS, and JavaScript.

Real-World Applications and Hardware Acceleration

The derivatives of LZ77 and LZ78 are embedded in almost every layer of modern computing infrastructure.

In web infrastructure, HTTP compression^[19] relies heavily on these algorithms to reduce bandwidth consumption and accelerate page load times. The gzip content encoding, which uses DEFLATE and is specified in RFC 1952^[20], has been the standard for decades. More recently, Brotli and Zstandard have been adopted by major web browsers and content delivery networks due to their superior compression density for text-based web assets. The Web Open Font Format 2.0 (WOFF2)^[21] also mandates Brotli compression to reduce the size of web fonts.

Image formats frequently utilize Lempel-Ziv algorithms to provide lossless image compression. The Graphics Interchange Format (GIF)^[22], introduced by CompuServe in 1987, uses LZW compression. The Portable Network Graphics (PNG)^[23] format was specifically designed to use DEFLATE, partly to avoid the patent encumbrances that affected LZW in the 1990s. PNG applies predictive filters to the image data before passing it to the DEFLATE compressor, maximizing the redundancy that LZ77 can exploit.

File archiving and distribution tools are entirely dependent on these methods. The ZIP file format, the .tar.gz format common in Unix environments, and the .7z format all use LZ-based algorithms. Package managers for operating systems use DEFLATE, LZMA, or Zstandard to compress software binaries for distribution.

In the domain of file systems and databases, LZ algorithms are used for transparent, on-the-fly compression. The ZFS file system and the Btrfs file system^[24] support LZ4 and Zstandard to compress data before writing it to disk, which saves storage space and increases effective disk throughput. Databases like PostgreSQL use LZ-based algorithms (such as pg_lzcompress) to compress large text fields in memory and on disk^[25]. The Linux Kernel Crypto API^[26] provides hardware and software implementations of LZ4, LZO, and DEFLATE for use by various kernel subsystems.

Because compression is a computationally intensive task, enterprise environments increasingly rely on hardware acceleration to offload LZ algorithms from the main CPU. Technologies such as Intel QuickAssist Technology (QAT)^[27] provide dedicated silicon to perform DEFLATE and LZ77 compression at speeds of tens of gigabytes per second. By moving the heavy string-matching operations of LZ77 to specialized hardware, servers can maintain high network throughput and storage efficiency without consuming CPU cycles needed for core application logic.

Significance and Tradeoffs

The significance of LZ77 and LZ78 lies in their ability to provide universal, single-pass, lossless compression with high efficiency. Before their invention, achieving optimal compression required analyzing the entire dataset in advance. Lempel and Ziv proved that an adaptive dictionary approach could match the theoretical entropy limits of a data source on the fly. This made streaming compression practical, allowing data to be compressed and transmitted simultaneously over networks.

A major advantage of LZ algorithms, particularly LZ77 derivatives, is their asymmetric performance profile.^[33] Decompression is typically much faster and requires significantly less memory than compression. During compression, the algorithm must perform computationally expensive string matching to find the longest repeated sequences. During decompression, the algorithm only needs to read the tokens and copy bytes from a known memory address. This asymmetry is highly desirable in scenarios where data is compressed once but read many times, such as web serving, software distribution, and media decoding.

However, LZ algorithms have specific tradeoffs. They are highly effective on data with localized redundancy, such as text, source code, uncompressed bitmaps, and structured data formats like JSON or XML. They are entirely ineffective on data that lacks redundancy or has already been compressed. Attempting to compress encrypted data, compressed audio, or compressed video with an LZ algorithm will yield no size reduction and may even slightly increase the file size due to the overhead of the tokens. This behavior aligns with the pigeonhole principle of information theory, which dictates that no lossless compression algorithm can compress all possible inputs.

The memory requirements of LZ algorithms scale with the size of the window or dictionary. While LZ4 and DEFLATE use small windows (typically 64 kilobytes or 32 kilobytes) that fit easily into the L1 or L2 cache of a modern CPU, algorithms like LZMA require hundreds of megabytes of RAM to maintain their massive dictionaries. This makes LZMA unsuitable for embedded systems or microcontrollers with strict memory constraints, where simpler algorithms or specialized variants must be used. Ultimately, the enduring legacy of LZ77 and LZ78 is their flexibility, providing a foundational logic that continues to be adapted for the shifting constraints of modern computing hardware.