How Do LZ77 and LZW Achieve Lossless Data Compression?

LZ77 and Lempel-Ziv-Welch are dictionary-based lossless data compression algorithms that reduce file size by replacing repeated sequences of characters with shorter references to earlier occurrences. Instead of assigning shorter bit codes to individual symbols based on frequency, both algorithms exploit patterns of repetition within the data stream itself. Because the original sequences can be reconstructed deterministically from these references, no information is lost during compression or decompression.

How Dictionary-Based Compression Works

In classical computing, raw data such as text, source code, or uncompressed bitmaps often contains recurring substrings. A dictionary-based compressor maintains a record of previously seen substrings and substitutes subsequent appearances with compact pointers or index codes.

The compression is lossless because every pointer unambiguously identifies an exact sequence of bytes that has already been processed. When the decompressor reads the compressed stream, it maintains an identical view of the prior data and expands each reference back into its original characters.

How LZ77 Uses a Sliding Window

Introduced by Abraham Lempel and Jacob Ziv in 1977, LZ77 uses a sliding window over the input stream rather than an explicit, separate dictionary table. The sliding window is divided into two adjacent regions:

  1. Search buffer: A fixed-size region of recently processed bytes that acts as the implicit dictionary.
  2. Lookahead buffer: A smaller region containing the upcoming bytes to be encoded.

At each step, the encoder searches the search buffer for the longest prefix of the lookahead buffer. It then outputs a token, typically a triple of the form \((d, l, c)\), where:

  • \(d\) is the backward distance (offset) from the current position to the start of the match in the search buffer.
  • \(l\) is the length of the matched substring.
  • \(c\) is the next literal character immediately following the match in the lookahead buffer.

If no match is found, the encoder outputs \((0, 0, c)\) to emit the single literal character. After emitting the token, the window slides forward by \(l + 1\) positions.

Decoding LZ77

Decoding an LZ77 stream is fast and requires minimal memory. The decoder maintains an output buffer of recent bytes. For each \((d, l, c)\) token, it copies \(l\) bytes starting from \(d\) positions back in the output buffer, appends those bytes to the output, and then appends the literal character \(c\).

How Lempel-Ziv-Welch (LZW) Uses an Explicit Dictionary

Published by Terry Welch in 1984 as a refinement of LZ78, the Lempel-Ziv-Welch (LZW) algorithm builds an explicit table of substrings dynamically as it reads the input. Unlike LZ77, LZW does not output literal characters alongside pointers; it outputs only dictionary index codes.

Encoding with LZW

The LZW encoder initializes its dictionary with all possible single-byte values (indices \(0\) through \(255\) for 8-bit bytes). It then processes the input stream using the following steps:

  1. Read characters into a current string \(P\) while \(P\) exists in the dictionary.
  2. When appending the next character \(C\) produces a string \(P + C\) that is not in the dictionary, output the dictionary code for \(P\).
  3. Add \(P + C\) to the dictionary under the next available index.
  4. Reset \(P\) to \(C\) and continue.

Because repeated substrings are added to the dictionary as single entries, longer and longer sequences are replaced by a single integer code, such as a 12-bit index.

Decoding LZW Without Transmitting the Dictionary

A key feature of LZW is that the dictionary does not need to be stored in the compressed file. The decoder initializes its own dictionary with the same single-byte entries (\(0\) through \(255\)). As it reads each code, it outputs the corresponding string and reconstructs the exact same multi-character entries in the same order as the encoder.

There is one edge case: when the encoder outputs a code for a string it just added in the previous step, the decoder has not yet added that entry. LZW handles this deterministically by taking the previous decoded string and appending its own first character.

Comparing LZ77 and LZW

While both algorithms achieve lossless compression through substring references, they differ in structure and trade-offs:

  • Dictionary representation: LZ77 uses an implicit sliding window of recent bytes, whereas LZW maintains an explicit table of indexed strings.
  • Memory and speed: LZ77 encoding can be computationally expensive when searching for the longest match in a large search buffer, while decoding is very fast. LZW uses hash tables or tries for fast dictionary lookups during both encoding and decoding.
  • Real-world formats: LZ77 forms the basis of DEFLATE (used in ZIP, gzip, and PNG), while LZW is famously used in GIF images and the Unix compress utility.

Both algorithms demonstrate how classical lossless compression reduces redundancy by turning repeated data into compact references that can be reversed with complete accuracy.