Why can’t you zip a zip?

I was sending a project folder to a friend over the hostel WiFi, which on a good night moves about as fast as a sleepy turtle. Three hundred megabytes. Not happening.

So I zipped it. Forty-one megabytes.

Okay, that’s genuinely impressive. Same files, same code, same everything, and it’s now seven times smaller. And then my brain did the thing it always does at 1 AM: if zipping made it seven times smaller, what happens if I zip the zip?

You already know where this is going. I zipped the zip.

It got bigger.

Not by much. A few kilobytes. But bigger. The compressor looked at my file, thought really hard about it, and gave me back something worse than what I started with.

Wait, what?

That’s when I realised I had no idea what “compressing” a file actually means. I’d been right-clicking “Compress” for years like it was a magic button. So, this post. Let’s open up the magic button.

The theory that made too much sense (and was wrong)

My first guess: compression throws away the useless stuff. Spaces, blank lines, padding. Files have air in them, zip squeezes the air out, like vacuum-packing a pillow.

Easy to test. I took a text file, deleted every space and newline, and gzipped it.

It still shrank. A lot. No air left to squeeze, and it still got less than half the size.

So it isn’t removing anything. Every single byte comes back when you unzip. The file is exactly the same, down to the last bit. Which means the compressor found a shorter way to say the same thing.

And that’s the whole trick. Hold on to that sentence, it explains everything including the zip-of-a-zip mystery.

Some letters are boring

Here’s an idea older than computers. In the 1830s, Samuel Morse and Alfred Vail were designing a code for the telegraph, where every dot and dash costs time. The story goes that Vail went to a newspaper printer and counted how many of each letter they kept in their type cases. Lots of E’s. Very few Q’s.

So in Morse code, E is a single dot. T is a single dash. Q is --·-. The letters you send all the time are cheap, the rare ones are expensive, and on average your messages get shorter.

Computers mostly don’t do this. Plain text spends exactly 8 bits on every character, whether it’s an e that shows up every few letters or a z you see twice a page. That’s like paying the same postage for a postcard and a fridge.

How much could you save? In 1948, Claude Shannon worked out the exact answer and called it entropy: the average number of bits you need per symbol, given how often each one shows up. If a symbol has probability $p$, the ideal code for it is ${\log }_2\frac{1}{p}$ bits long, so common things get short codes and surprising things get long ones. Average that over all the symbols:

That’s the floor. No code that works one symbol at a time can beat it.

Entropy is really a measure of surprise. If I tell you the next letter is probably an E, and it’s an E, you learned almost nothing. If it’s a Q, you learned a lot. Compression is just charging less for the boring stuff.

Huffman: the term paper that beat the professor

Knowing the floor exists is one thing. Actually building a code that gets close to it is another.

In 1951, David Huffman was a grad student at MIT in Robert Fano’s information theory class. Fano gave the students a choice: sit the final exam, or write a term paper on finding the most efficient binary code. Huffman picked the paper, struggled with it for months, and was about to give up and study for the exam when the answer clicked. Fano himself had worked on this problem with Shannon and hadn’t cracked it1Fano’s own method, Shannon–Fano coding, builds the tree from the top down by splitting the symbols into two halves of roughly equal weight. It’s good, but not always optimal. Huffman’s bottom-up merging always is, among codes that give each symbol its own whole number of bits..

Huffman’s algorithm is so simple it feels like cheating:

1. Count how often each symbol appears.
2. Take the two rarest things, and glue them together into one, with their counts added up.
3. Repeat until there’s only one thing left.

That’s it. What you get is a tree. Read the path from the top down to each letter (left is 0, right is 1) and that’s its code. Rare letters got glued early, so they’re buried deep with long codes. Common letters got glued last, so they sit near the top with short codes.

Type something into the box and build the tree one merge at a time:

Look at the codes under the letters once it finishes. The common ones (the s, the space, the e) get two or three bits. The one-off letters, like the b in “by”, get four or five. The whole sentence comes to 114 bits instead of 296, just above the entropy floor of about 111.

There’s one more neat property hiding in there: no code is the start of another code. Since every letter is a leaf, you never pass through a letter on the way to another one. So when you’re decoding a long string of bits, there’s never any confusion about where one letter ends and the next begins. No separators needed.

Here’s the whole thing in Python, using a heap to always grab the two lightest trees:

import heapq
from collections import Counter

def huffman_codes(text):
    # Each heap entry: (weight, tiebreak, {symbol: code so far})
    heap = [(n, i, {ch: ""}) for i, (ch, n) in enumerate(Counter(text).items())]
    heapq.heapify(heap)
    tiebreak = len(heap)
    while len(heap) > 1:
        w1, _, left = heapq.heappop(heap)
        w2, _, right = heapq.heappop(heap)
        merged = {ch: "0" + code for ch, code in left.items()}
        merged |= {ch: "1" + code for ch, code in right.items()}
        heapq.heappush(heap, (w1 + w2, tiebreak, merged))
        tiebreak += 1
    return heap[0][2]

print(huffman_codes("she sells sea shells by the sea shore"))

But text isn’t just letters

Huffman is great, but it has a blind spot. It only looks at letters one at a time. It has no idea that merrily showed up four times in a row, or that your code has return in it two hundred times.

My project folder was mostly code. And code repeats whole chunks. Same imports at the top of every file, same function names, same boilerplate.

In 1977, Abraham Lempel and Jacob Ziv came up with a way to exploit exactly that, now called LZ77. The idea: walk through the text, and whenever the next few characters already appeared somewhere earlier, don’t write them out again. Write a tiny note instead:

go back 23 characters, copy 9.

That’s called a back-reference. If nothing earlier matches, you just write the character as is (a “literal”) and move on.

Step through it on a nursery rhyme. Blue is where the copy comes from, green is what it produces:

Watch what happens with merrily, merrily, merrily, merrily. The first one costs eight literals. And then something clever happens: the other three come out as one back-reference, and it copies more than it goes back. It reaches back nine characters and copies twenty-eight. The copy overlaps the stuff it’s still in the middle of writing, which sounds illegal, but works fine if you copy one character at a time. It’s how LZ77 turns aaaaaaaa into “one a, then go back 1 and copy 7”.

DEFLATE: the two ideas, stacked

So we have two tricks that attack different kinds of patterns. Huffman makes common symbols cheap. LZ77 makes repeated phrases cheap. What if you do both?

That’s DEFLATE, designed by Phil Katz for PKZIP in the early ’90s. First LZ77 turns the file into a stream of literals and back-references, then Huffman coding squeezes that stream, giving short codes to the literals and match lengths that show up most. LZ77 looks back up to 32 KB, and a single copy can be up to 258 bytes long.

And DEFLATE is everywhere. It’s inside .zip files, gzip and PNG images, and gzip still squeezes a huge share of the web’s traffic on its way to your browser.

Your browser can actually run it for you, so this next thing isn’t a simulation. Pick an input and watch the real numbers:

The paragraph shrinks nicely. The repeated line nearly vanishes (it’s one line and then one giant back-reference). The random bytes don’t shrink at all. They get bigger.

Now hit “zip it again” a few times. There it is. My zip-of-a-zip, right in your browser. The first round helps, and every round after that adds a little.

I tried the same thing in a terminal, on the markdown file of another post on this site:

$ gzip -9 -k post.md && gzip -9 -c post.md.gz > twice.gz && gzip -9 -c twice.gz > thrice.gz
$ wc -c post.md post.md.gz twice.gz thrice.gz
 23244 post.md
  9980 post.md.gz
 10014 twice.gz
 10046 thrice.gz

Down by more than half, then up, then up again. Every time.

Why it has to get bigger

Here’s the thing I didn’t understand at 1 AM. After DEFLATE is done, the output has no patterns left. That’s literally its job: find every pattern it can and replace it with something shorter. What comes out the other end looks like noise. No common bytes to give short codes to, no repeated phrases to point back at.

So the second zip finds nothing, and it still has to write its headers and block markers. Hence: a few bytes bigger.

But there’s a deeper reason, and it’s my favourite part. No compressor can make every file smaller. Not zip, not some future AI-powered compressor, nothing. And you can prove it with counting.

Take every possible file that’s exactly $n$ bits long. There are $2^n$ of them. Now count every file that’s shorter than $n$ bits, including the empty one:

That’s one fewer. A compressor that’s actually lossless has to send each input to a different output (otherwise how would unzip know which one to give you back?). So if it tried to shrink all $2^n$ files, at least two of them would have to share a shorter output. Impossible.

This is the pigeonhole principle: you can’t put $2^n$ pigeons into $2^n-1$ holes with one pigeon per hole. Try it:

So every compressor makes some files bigger. The good ones just make sure those are files nobody cares about, like random noise, and already compressed stuff. Real files (text, code, images with big flat areas) are full of patterns, which is exactly why compression feels like magic on them.

Compression is prediction

One last idea, and it’s the one that rewired my brain a little.

Every compressor we’ve seen is secretly a prediction machine. Huffman predicts the next letter from how common letters are. LZ77 predicts that whatever’s coming next probably happened before. The better your guess about what comes next, the fewer bits you spend on the surprise when it does.

Take that to the extreme and you get compressors that use fancier and fancier models of the data. People have built compressors out of neural networks, and the Hutter Prize literally pays money for compressing a gigabyte of Wikipedia smaller than anyone else, on the theory that compressing knowledge well and understanding it are close to the same thing.

And random data is incompressible precisely because nothing can predict it. If something could, it wouldn’t be random.

So when my zip-of-a-zip got bigger, it wasn’t the compressor failing. It was the compressor telling me, very politely: I already found everything there was to find.

Then I sent the forty-one megabytes over the turtle WiFi. It took eleven minutes. Some problems compression can’t fix.

References

1. Claude Shannon, A Mathematical Theory of Communication (1948). Where entropy comes from.
2. David Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE (1952).
3. Jacob Ziv and Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory (1977).
4. RFC 1951: DEFLATE Compressed Data Format Specification.
5. The Hutter Prize for compressing human knowledge.