Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 37 ยท Compression in Practice

Dictionary Compression: LZ77 and LZ78

Learn how Lempel-Ziv dictionary coders replace repeats with references: implement LZ77 sliding-window and LZ78 dictionary compression in Python and test round trips.

Huffman and arithmetic coding compress by giving frequent symbols short codes. They need to know the symbol probabilities, and they do not notice that a text repeats whole phrases: "the", "the", "the". Lempel-Ziv coders take a different route. They discover repetition while reading the data, and replace every repeat with a short reference to an earlier occurrence. No probability model is transmitted.

Almost every general-purpose compressor you use is built on this idea: ZIP, gzip, PNG, zlib, 7-Z (LZMA), Zstandard, LZ4 and Snappy. In this lesson you implement the two original algorithms, LZ77 (1977) and LZ78 (1978), and see why they approach the entropy rate of a stationary source for long inputs, even though they know nothing about it in advance.

LZ77: a sliding window

LZ77 keeps a window of the most recent data. At each position the encoder searches the window for the longest string that matches the upcoming text, and emits a triple:

TEXT
(offset, length, next_symbol)
  • offset: how far back the match starts (0 if no match);
  • length: how many symbols match;
  • next_symbol: the first symbol after the match, which guarantees progress even when nothing matches.

The decoder is simpler: it copies length symbols from offset back, then appends next_symbol. A match may even overlap the text being produced: offset 1 and length 10 repeats the previous symbol ten times, a natural run-length encoding.

Python LZ77 encoder and decoder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the tokens for a repeated 20 times: the second token is (1, 18, 'a'), a copy that overlaps itself. The decoder handles that naturally, because it appends symbols one at a time.

The encoder above searches every window position for every input position, which is slow (quadratic). Real implementations use hash tables or hash chains to find candidate matches in nearly constant time, and bounded search depth, trading compression for speed. That is exactly what the "level" option of gzip changes.

Cost accounting

A token like (offset, length, next) is only worth it if it is shorter than the text it replaces. With a window of 255 and lengths up to 255, a triple costs about 3 bytes, so a match must be longer than 3 symbols to pay. Real formats use variable-length codes for offsets and lengths and entropy-code the tokens afterwards. The next lesson shows how DEFLATE combines LZ77 with Huffman coding.

LZ78: an explicit dictionary

LZ78 does not use a window. Instead encoder and decoder both build a dictionary of phrases as the data flows. Each output token is (index, symbol): the index of the longest phrase already in the dictionary that matches, plus the one symbol that extends it. The extended phrase is then added to the dictionary. The decoder makes the same additions, so the dictionary never has to be transmitted.

LZW, the algorithm in the original GIF and Unix compress, is a refinement of LZ78 that starts with all single characters in the dictionary and outputs only indexes.

Python LZ78 and its growing dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Early tokens each add a one- or two-letter phrase; later tokens reuse longer and longer ones. On a short text like this the gain is small, because the dictionary is still learning. Compression gets better the longer the data.

Universality

Ziv and Lempel proved that for any stationary ergodic source, the compression rate of LZ77 and LZ78 approaches the source's entropy rate as the input length grows. This is called universality: one algorithm, no knowledge of the statistics, asymptotically optimal. In practice convergence can be slow, and good compressors add a modelling and entropy-coding stage on top.

Python Repetition compresses, randomness does not

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of phrases is a measure of complexity: a constant string needs about sqrt(2n) phrases, a random string needs about n / log n, and everything else falls in between. That is the Lempel-Ziv complexity, used in research to estimate entropy.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an LZ77 token (offset, length, next_symbol) mean?

    The decoder copies a run from the already-decoded text and then adds one literal symbol.
  2. 2. How does the LZ78 decoder learn the dictionary?

    Both sides add phrase + symbol after every token, so the dictionaries stay identical without being sent.
  3. 3. Why can an LZ77 match overlap the text being produced?

    With offset 1 and length 10 the same symbol is repeated: each copied symbol is available as soon as it is written.
  4. 4. What does universality of Lempel-Ziv coding mean?

    That is Ziv and Lempel's result: asymptotic optimality without a model of the source.

Summary

  • Lempel-Ziv coders replace repeated phrases with references; no statistics are transmitted.
  • LZ77 uses a sliding window and emits (offset, length, next) triples.
  • LZ78 builds a dictionary that encoder and decoder grow in step; LZW is a popular variant.
  • Both are universal: asymptotically optimal for stationary sources.
  • Real compressors pair them with entropy coding, as in DEFLATE.

Next: DEFLATE, gzip and zlib