Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 37 ยท Compression in Practice

DEFLATE, gzip and zlib in Practice

See how DEFLATE combines LZ77 and Huffman coding, how gzip and zlib wrap it, and measure compression levels, block types and the entropy limit with Python's zlib.

If you have opened a ZIP file, loaded a PNG, or visited a website that sent Content-Encoding: gzip, you have used DEFLATE. It is the workhorse of general-purpose compression, specified in 1996, and it combines two ideas from this course: Lempel-Ziv matching to remove repetition, and Huffman coding to squeeze the remaining redundancy in the symbol statistics.

Python's zlib module is a thin wrapper over the same C library that most of the internet uses, and it runs in the in-browser Python on this page. We will use it to take DEFLATE apart without reading the specification.

The two stages

  1. LZ77 stage. The compressor scans the data with a 32 KB window and turns it into a stream of literals (single bytes) and matches (length 3 to 258, distance 1 to 32768).
  2. Huffman stage. The stream is divided into blocks. In each block, literals and lengths share one Huffman alphabet (0-255 literals, 256 end-of-block, 257-285 length codes), and distances use a second Huffman alphabet. Extra bits after a code give the exact value.

A block can be one of three types, announced by a 2-bit field BTYPE:

BTYPE Block When it is used
00 stored: raw bytes incompressible data
01 fixed Huffman: built-in code table short inputs, so no table is sent
10 dynamic Huffman: code lengths sent first most real data
flowchart LR
  A["Input bytes"] --> B["LZ77: literals and matches"]
  B --> C["Block: choose stored, fixed or dynamic"]
  C --> D["Huffman codes + extra bits"]
  D --> E["DEFLATE stream"]

DEFLATE is LZ77 followed by Huffman coding, block by block.

Peeking at the block type

A raw DEFLATE stream (no header) starts with the bit BFINAL followed by the two bits of BTYPE. Bits are read from the least significant end of each byte.

Python Which block type did the compressor choose?

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.

A long random input cannot be compressed, so the compressor falls back to stored blocks (5000 bytes become 5005). A tiny input uses fixed Huffman codes because sending a custom code table would cost more than it saves; even then 20 random bytes grow by 3. Larger repetitive data gets a dynamic table and shrinks dramatically.

gzip, zlib and raw DEFLATE

The same compressed bytes come in three wrappers, chosen with the wbits parameter:

Format Header / trailer Used by
raw DEFLATE none ZIP entries, PNG chunks (inside zlib), HTTP internals
zlib 2-byte header, Adler-32 checksum PNG, many protocols
gzip 10-byte header, CRC-32 and length .gz files, HTTP gzip
Python Three wrappers, one algorithm

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.

Compression levels

Levels 1 to 9 trade speed against how hard the matcher searches. Level 0 stores the data unchanged. The format is the same at every level, so any decompressor reads every level.

Python Effect of the compression level

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.

Returns diminish quickly: level 1 is already about 5 times smaller than the input, and level 9 is only about 5% smaller than level 6 while taking noticeably longer. For most data, level 6 is the best compromise, which is why it is the default.

Compression and entropy

Is there a limit to what DEFLATE can do? An order-0 entropy estimate tells how well a memoryless model could do. For our random word text above, the word choice is uniform over 15 words, so each word carries log2(15) โ‰ˆ 3.91 bits. DEFLATE has to spell each word out with Huffman codes and references, so you should expect it to get reasonably close but not reach the bound.

Python Compare zlib with the entropy bound

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.

DEFLATE ends up at about 1.8 times the ideal for this source (17,241 bytes against 9,767). The ideal itself is not reachable without knowing the word model, but a model-based compressor (arithmetic coding of the word choices) would get close to it. That is the trade-off between general and specialized compression.

Compressing encrypted or already-compressed data does not shrink it; it may grow slightly because of block headers. Always compress before encrypting. Note also that compressing secrets together with attacker-controlled text can leak information through the output size, as in the CRIME and BREACH attacks.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What two techniques does DEFLATE combine?

    A 32 KB sliding-window LZ77 stage produces literals and matches, which a Huffman stage then encodes.
  2. 2. Which block type does a compressor choose for incompressible random data?

    Stored blocks copy the bytes as they are, with a small header, when compression would not help.
  3. 3. What distinguishes gzip from zlib wrapping?

    Both wrap the same DEFLATE stream; only the header and integrity trailer differ.
  4. 4. Why does compressing an already compressed file not help?

    Good compression leaves little redundancy; what remains looks random and is not compressible.

Summary

  • DEFLATE = LZ77 (32 KB window) followed by Huffman coding, organized in blocks.
  • Blocks are stored, fixed Huffman or dynamic Huffman, chosen per block.
  • zlib, gzip and raw DEFLATE are three wrappers around the same stream.
  • Levels 1-9 control how hard the matcher works; level 6 is a good default.
  • General-purpose compressors do not reach the entropy of a specific source.

Next: The Burrows-Wheeler Transform and Move-to-Front