DEFLATE — LZ77 + Huffman

DEFLATE (RFC 1951, used by gzip, zlib, PNG, ZIP) combines both techniques:

1. LZ77 phase — scan input, emit literals + back-references.
2. Huffman phase — encode the tokens using two Huffman tables:
   • lit_len — codes for literal bytes (0-255) and lengths (256-285)
   • dist — codes for distances (0-29)

The combined token alphabet:

Code 0-255:    literal byte
Code 256:      end-of-block
Code 257-285:  back-reference length (with extra bits for big lengths)

When the encoder emits MATCH(offset, length), it:

1. Encodes length as a lit_len code (and extra length bits)
2. Encodes offset as a dist code (and extra dist bits)

Each block in DEFLATE can use:

• Stored mode (no compression — for incompressible data)
• Fixed Huffman (pre-defined tables, saves a few bytes)
• Dynamic Huffman (per-block computed tables, best compression)

Dynamic mode encodes the Huffman codes themselves with another Huffman code (yes, three nested) — the "code length code" tree.

Total result: gzip can compress English text to ~30%, source code to ~25%, structured data even less. The compression-speed tradeoff is set by gzip's -1 (fast) to -9 (best).

Modern alternatives:

• brotli (RFC 7932): bigger predefined dictionary; tighter than gzip
• zstd: faster than gzip and tighter; uses Finite State Entropy (a generalized Huffman)
• xz / lzma: very dense; range coding instead of Huffman