How File Compression Actually Works: Huffman Coding, LZ77, and DEFLATE Explained

Every developer has worked with compressed files. You unzip a package, serve a gzip-encoded response, or export a PNG — and compression is happening under the hood. But the question most tutorials skip is: why does it work? Why can you take a 500 KB text file and reduce it to 180 KB without losing a single byte, but you cannot meaningfully compress a ZIP file further?

The answer lies in information theory and a handful of elegant algorithms. This article walks through the real mechanics: from Shannon entropy to Huffman trees to the DEFLATE format that underpins ZIP, gzip, and PNG.

Why Files Are Compressible at All

Files are compressible because they contain redundancy — patterns, repetitions, and predictable sequences that carry less information than their raw byte count suggests.

Consider a simple example. The string AAAAAAAAAA (ten As) takes 10 bytes in ASCII. But the information content is trivial: you could describe it perfectly as "ten As." A compression algorithm does exactly that — it replaces verbose, redundant data with a shorter description.

Real files are full of this kind of redundancy:

• English text re-uses common words and letter combinations constantly. "the", "ing", "tion" appear far more often than "xqz".
• Source code has deeply repetitive structure: function, return, const, indentation runs, blank lines.
• Bitmap images contain long horizontal runs of identical or near-identical pixels — especially in flat-color areas.
• Log files repeat timestamps, hostnames, and status codes thousands of times.

The more redundant the data, the more compressible it is. The less redundant — the more random — the harder it becomes to compress.

Entropy: The Hard Limit on Compression

Claude Shannon's 1948 paper A Mathematical Theory of Communication introduced a precise way to measure information content: entropy, measured in bits.

Shannon entropy answers the question: how many bits do you actually need, on average, to represent one symbol from this data source?

The formula for a source with symbols s₁, s₂, ..., sₙ and probabilities p₁, p₂, ..., pₙ is:

H = -Σ pᵢ × log₂(pᵢ)

Here is what that means in practice. Suppose you have a file containing only two characters: A (appears 90% of the time) and B (appears 10% of the time).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 bits per symbol

A naive encoding uses 1 bit per symbol (0 for A, 1 for B). But the entropy says the theoretical minimum is 0.469 bits per symbol — less than half. A good compression algorithm gets close to that limit.

Now consider a truly random file where every byte value (0–255) appears with equal probability (1/256 each):

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 bits per byte

Eight bits per byte — full entropy. There is no redundancy to exploit. This is why you cannot compress a ZIP file further: it is already close to maximum entropy. Every bit is carrying information; there are no patterns left to eliminate.

Run-Length Encoding: The Simplest Form

Before getting to the heavier algorithms, run-length encoding (RLE) illustrates the core idea cleanly.

RLE replaces a run of repeated symbols with a count and the symbol:

Original:  AAABBBBBCCDDDDDD
RLE:       3A 5B 2C 6D

Original: 16 characters. Encoded: 8 characters. 50% reduction.

RLE is used in fax transmission (CCITT Group 3/4), BMP files, and as a sub-step inside more complex formats. Its weakness is obvious: it performs poorly on data without long runs. The string ABABABAB has no runs, so RLE makes it larger by prepending counts of 1 everywhere.

That weakness is exactly what drives more sophisticated approaches.

Huffman Coding: Shorter Codes for Common Symbols

In standard ASCII, every character gets 8 bits regardless of how often it appears. Huffman coding breaks that assumption. Frequent symbols get shorter codes; rare symbols get longer codes. The average code length drops, and the file shrinks.

Building a Huffman Tree

Take the string AABBBCCCC (9 characters). Count the frequencies:

Step 1. Put each symbol in a leaf node weighted by its frequency.

[A:2]  [B:3]  [C:4]

Step 2. Repeatedly merge the two lowest-weight nodes into a parent node whose weight is their sum, until one tree remains.

Merge [A:2] and [B:3] → parent [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

Merge [C:4] and [AB:5] → root [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

Step 3. Assign codes by traversing the tree: left edge = 0, right edge = 1.

Counting the Bit Savings

With Huffman codes, encoding AABBBCCCC costs:

A × 2 occurrences × 2 bits = 4 bits
B × 3 occurrences × 2 bits = 6 bits
C × 4 occurrences × 1 bit  = 4 bits
Total = 14 bits

With fixed 8-bit ASCII:

9 characters × 8 bits = 72 bits

14 bits vs 72 bits — an 81% reduction on this toy example. Real-world gains are smaller, but the principle holds. English text typically compresses to 4–5 bits per character with Huffman alone, down from 8.

The critical insight: Huffman codes are prefix-free. No code is a prefix of another, which means a decoder can unambiguously reconstruct the original stream without any separators. The tree structure itself is stored in the compressed file header so the decoder can rebuild it.

LZ77 and LZ78: Exploiting Repeated Sequences

Huffman coding works on individual symbol frequencies. But it misses a larger class of redundancy: repeated sequences. The word "function" in source code carries 8 bytes each time it appears. If you could replace the second and subsequent occurrences with a pointer back to the first, you would save significantly.

That is exactly what Abraham Lempel and Jacob Ziv described in their 1977 and 1978 papers, giving us LZ77 and LZ78.

LZ77: Sliding Window Compression

LZ77 maintains a sliding window — a buffer of recently seen data. As the encoder processes new data, it looks back through the window to find the longest match for what comes next. If it finds one, it emits a back-reference (offset, length) instead of the literal bytes.

Consider encoding the string:

abcabc

Processing abc: no prior history, emit literals a, b, c.

Processing the second abc: the encoder looks back and finds abc starting 3 positions ago, with length 3. It emits the back-reference (offset=3, length=3) instead of three literal bytes.

The decoder, seeing (3, 3), goes back 3 positions in its output buffer and copies 3 bytes — reconstructing abc perfectly.

In a real implementation, the match search is bounded by the window size (gzip uses a 32 KB window). A longer window finds more matches but costs more memory and search time.

The back-reference (offset, length) is typically 2–3 bytes. So replacing a 10-byte repeated sequence with a 2-byte reference saves 8 bytes. The longer the match, the better the ratio.

LZ78 and LZW

LZ78 builds an explicit dictionary of encountered patterns rather than using a sliding window. LZW (Lempel-Ziv-Welch), a derivative, became famous as the algorithm behind GIF compression and the Unix compress utility. LZW encodes patterns as single dictionary indices, growing the dictionary on the fly during encoding and decoding.

DEFLATE: LZ77 Plus Huffman Coding

DEFLATE, defined in RFC 1951, combines LZ77 and Huffman coding in sequence:

1. LZ77 pass: Replace repeated sequences with (offset, length) back-references. The output is a stream of literals and back-references.
2. Huffman pass: Apply Huffman coding to that stream. Frequent literals get short codes; rare back-reference values get longer ones.

The two techniques attack different types of redundancy. LZ77 eliminates long-range repetition. Huffman coding then eliminates frequency-based redundancy in whatever remains. Together they achieve compression ratios that neither alone could reach.

DEFLATE data is organized into blocks. Each block can use one of three modes:

• No compression — for data where compression would expand the output (already-random data)
• Fixed Huffman codes — a pre-agreed code table, saving the overhead of storing a custom tree
• Dynamic Huffman codes — a custom tree optimized for this specific block, stored in the block header

The dynamic mode is used for most compressible data. The encoder analyzes the block, builds an optimal Huffman tree, stores it at the start of the block, then encodes the data using that tree.

Where DEFLATE Lives in Real File Formats

ZIP

ZIP files store each entry independently with its own DEFLATE-compressed stream. This per-entry compression means you can extract a single file from a ZIP without decompressing the whole archive. The ZIP format also supports a "stored" mode (no compression) for files that are already compressed.

gzip

gzip wraps a single DEFLATE stream with a header (magic number, OS, modification time) and a CRC32 checksum. It is the standard compression format for HTTP Content-Encoding: gzip and for .tar.gz archives. The .gz extension is always a single DEFLATE stream.

PNG

PNG uses DEFLATE (via zlib) to compress its pixel data. Before compression, PNG applies a filter step: it transforms each row of pixels into differences from a prediction (delta coding). This dramatically increases the runs and repetitions that LZ77 can exploit, improving compression significantly. For typical screenshots and diagrams, PNG compresses to 20–50% of the raw pixel data size. Image compression tools that export PNG are relying on this pipeline.

zlib

zlib is a wrapper format around DEFLATE — it adds a two-byte header and an Adler-32 checksum. PDF streams use zlib/DEFLATE when compressing embedded content (PDF compression reduces file size by recompressing or removing these streams). HTTP, WebSockets, and many network protocols also use zlib.

JPEG: A Different Approach

It is worth pausing here because JPEG uses a completely different compression strategy — one that deliberately loses data.

JPEG applies a Discrete Cosine Transform (DCT) to 8×8 pixel blocks. The DCT converts pixel values into frequency components (similar to a Fourier transform). High-frequency components — fine detail — are then quantized aggressively (rounded to coarser values or discarded entirely). The remaining coefficients are encoded with Huffman coding, but the lossy quantization step is what makes JPEG so much smaller than PNG for photographs.

The trade-off: JPEG cannot perfectly reconstruct the original pixels. PNG can. This is the lossless vs. lossy distinction explored in depth in our article on lossy vs. lossless file conversion.

For a photograph, JPEG at quality 80 might use 10% of the bytes a lossless PNG would need. For a screenshot with flat colors and sharp edges, PNG usually wins because DCT artifacts are visible and DEFLATE compresses flat regions extremely well.

Why You Cannot Compress a ZIP File Further

This is a common source of confusion. If compression works by finding patterns, why does compressing an already-compressed file yield almost nothing?

Because DEFLATE is doing its job correctly. A well-compressed DEFLATE stream looks statistically random — by design. The back-references and Huffman codes eliminate the predictable patterns. What remains is close to the entropy limit of the data.

Run a second compressor over it and it finds no runs (LZ77 finds no long matches) and no frequency skew (Huffman sees a near-uniform symbol distribution). The entropy is already 7.9+ bits per byte. There is nothing left to exploit.

This is also why you should never compress already-compressed media. Wrapping a JPEG inside a ZIP costs you the ZIP overhead with no size benefit. The same applies to MP3, MP4, HEIC — all compressed formats that already sit near their entropy ceiling.

Algorithm Comparison

Putting It Together

The chain from raw data to compressed bytes looks like this for a gzip-compressed file:

1. Input: Raw byte stream (e.g., a text file)
2. LZ77: Scan for back-references with a 32 KB sliding window, producing a stream of literals and (offset, length) pairs
3. Huffman coding: Build two trees — one for literals/lengths, one for offsets — and encode the LZ77 output
4. DEFLATE blocks: Package the Huffman trees and encoded data into one or more blocks
5. gzip wrapper: Prepend the gzip header, append the CRC32 and original file size
6. Output: .gz file, typically 30–70% smaller for compressible input

Decompression runs strictly in reverse: parse the gzip header, read and reconstruct Huffman trees from block headers, decode the Huffman stream back into LZ77 tokens, apply back-references to reconstruct the original byte stream. Decompression is always faster than compression because the hard work (searching for optimal matches, building optimal trees) is done only once.

Key Takeaways

• Files are compressible because they contain redundancy — repeated patterns and skewed symbol frequencies.
• Shannon entropy sets the hard floor: truly random data cannot be compressed because every bit is already carrying information.
• RLE handles repetition crudely. Huffman coding handles frequency skew elegantly. LZ77 handles long-range sequence repetition.
• DEFLATE chains LZ77 and Huffman in sequence, which is why it beats either algorithm alone. It is the engine inside ZIP, gzip, PNG, and zlib-compressed PDF streams.
• JPEG takes a fundamentally different approach: lossy DCT quantization followed by lossless Huffman, trading pixel accuracy for dramatic size reduction.
• Compressing a compressed file accomplishes nothing because good compression produces near-maximum-entropy output.

Understanding these algorithms matters when you are choosing a format, diagnosing unexpectedly large files, or debugging a compression pipeline. The next time you reach for PDF compression, extract a ZIP file, or export a PNG for image compression, you will know exactly what the software is doing to your bits.