Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: A Mini DEFLATE-Style Compressor

Build a working lossless compressor in Python from scratch: an LZ77 match finder, a Huffman coder, a bit-level encoder and decoder, a round-trip test and a comparison against zlib.

You now know both halves of DEFLATE: LZ77 matching removes repeated phrases and Huffman coding shortens frequent symbols. In this project you build a small compressor from those two ideas, prove that it is lossless with a round-trip test, and measure how close it gets to real zlib.

To keep the code short we make some simplifications compared with real DEFLATE: one Huffman table for the whole file, a 4096-byte window, match lengths 3 to 18 and a fixed 12-bit distance field. It is a teaching compressor, not a production one.

Design

The compressor works in three stages:

  1. Tokenize the input into literals (one byte) and matches (length, distance).
  2. Map to symbols: a literal byte b becomes symbol b (0-255); a match of length L becomes symbol 256 + (L - 3) (256-271). The distance follows as 12 raw bits.
  3. Huffman-code the symbols with one table built from their frequencies.
flowchart LR
  A["Input bytes"] --> B["Match finder: literals and (len, dist)"]
  B --> C["Symbols 0-271 + raw distance bits"]
  C --> D["Huffman code from symbol counts"]
  D --> E["Bit string + code table"]
  E --> F["Decoder: Huffman decode, then copy matches"]

Compression and decompression are mirror images.

Step 1: the match finder

We index every 3-byte sequence by its positions and, for each input position, check the last 32 candidates inside the window for the longest match.

Python Step 1: tokenizing with LZ77

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.

Step 2: Huffman coding

Build the Huffman tree with a priority queue: repeatedly merge the two least frequent nodes. Then read each symbol's code from the path to its leaf. The tie-breaking counter makes the construction deterministic.

Python Step 2: a Huffman code from counts

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.

Step 3: the complete compressor and a test

Now we put the stages together: produce the bit string, then decode it back. We keep the output as a string of 0/1 characters for clarity and count len(bits) / 8 bytes. The code table costs 272 symbols ร— 4 bits in a real file (we charge that as header size).

Python Step 3: compress, decompress, compare

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 round trip is True, so the compressor is correct. Its size is larger than zlib's, which is expected: real DEFLATE has a larger window and longer matches (up to 258), uses separate Huffman tables for lengths and distances, codes distances with Huffman codes plus extra bits instead of 12 flat bits, uses lazy matching, and switches table per block.

Where the bits go

A good engineer asks which part of the output is largest. We can split the cost into literals, match symbols and raw distance bits.

Python Cost breakdown

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.

Raw distances are the biggest single cost, which is why real DEFLATE gives them a Huffman code of their own: some distances (like the typical word separations) are much more frequent than others.

Ideas to extend the project

  • Give distances their own Huffman table, coding the distance as a bucket plus extra bits as DEFLATE does.
  • Raise max_len to 258 and see the effect on highly repetitive data.
  • Write the bits into real bytes with int(bits, 2).to_bytes(...) and store the code table, to produce a file you could decompress later.
  • Try lazy matching: before taking a match, check whether starting one byte later gives a longer one.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the mini compressor spend 12 raw bits on every match distance?

    A flat 12-bit field is easy but wasteful; real DEFLATE entropy-codes distance classes.
  2. 2. How is a literal byte distinguished from a match length in the symbol alphabet?

    One merged alphabet lets the Huffman code decide how long each literal or length symbol should be, as in DEFLATE.
  3. 3. What proves that a compressor is lossless?

    Compression ratio says nothing about correctness; only equality after decoding does.
  4. 4. Which Huffman tie-break detail is essential for the decoder?

    Without the table the decoder cannot know which bit strings stand for which symbols.

Summary

  • A DEFLATE-style compressor = LZ77 tokens + one Huffman code over a merged literal/length alphabet.
  • The decoder mirrors the encoder: Huffman-decode symbols, then copy matches from the output.
  • A round-trip test is the proof of correctness.
  • Splitting the cost shows where improvements pay off (here, distances).
  • Real zlib wins through better matching, separate tables and block-wise adaptation.

Next: Practice Problems with Solutions