A 20-megabyte folder becomes a 4-megabyte ZIP file, and when you unzip it, every byte comes back perfectly. Where did the other 16 megabytes go, and how did the file "remember" them? The answer is that they were never really information at all — they were predictability, and predictability doesn't need to be stored. Compression is the art of writing down only the surprises.

That framing comes straight from information theory, and if it sounds odd, start with the pillar of this cluster, what information really is: information is measured by unpredictability, and anything you could have guessed is dead weight. This article is about the machinery that removes the dead weight — and the hard mathematical floor it can never break through.

Trick one: short codes for common things

Look at any English text and count letters. E appears constantly; Z and Q barely at all. Yet a plain text file spends exactly 8 bits on every character — the same price for an E as for a Q. That's like a store charging the same for a stick of gum and a television. There's obvious room to renegotiate.

The renegotiation is called Huffman coding (David Huffman, 1952, famously worked out as a term paper). The idea: assign each symbol a codeword of bits, but make the codewords different lengths — short for frequent symbols, long for rare ones. Maybe E gets 01 (2 bits), T gets 110, and Q gets 111011010 (9 bits). You pay more for Q, but you buy Q so rarely and E so constantly that the average cost per letter plummets.

There's one catch to variable-length codes: with no spaces between codewords, how do you know where one ends? Huffman codes solve this by being prefix-free — no codeword is the beginning of another. Picture a branching tree: from the root, go left for 0, right for 1, and every symbol sits on a leaf. Reading bits walks you down the tree; hitting a leaf means a symbol is complete, and you jump back to the root. No separators needed. Huffman's algorithm builds the tree that minimizes the average code length for given symbol frequencies, and it's provably optimal among codes of this type.

Morse code had the same instinct a century earlier — E is a single dot, Q is dah-dah-di-dah — which is a nice reminder that the idea is older than the theory that explains it.

Trick two: never say the same thing twice

Huffman attacks letter frequencies, but text has a bigger redundancy: repetition. The phrase "the compression algorithm" might appear forty times in a manual about compression. Why spell it out forty times?

Dictionary methods — the LZ77 and LZ78 algorithms of Abraham Lempel and Jacob Ziv (1977 and 1978) — replace repeats with references. LZ77's version: as you read the data, keep a sliding window of the recent past. When the next stretch of input matches something you've seen in the window, don't output the text — output a short pointer meaning "go back 3,041 characters and copy 25 of them." The pointer costs a few bytes; the repeated phrase might have cost dozens. LZ78 builds an explicit dictionary of phrases seen so far and refers to entries by number; same spirit, different bookkeeping.

Real compressors stack the tricks. ZIP's DEFLATE algorithm runs LZ77 first, turning repeats into pointers, then Huffman-codes the output, so common pointers and literals get short bit-patterns too. PNG does the same to image data after a filtering step that turns smooth gradients into long runs of near-identical values. FLAC predicts each audio sample from the previous few and stores only the prediction error, which is small and compresses beautifully. Different domains, one strategy: transform the data so its predictability is exposed, then encode the surprises efficiently.

The floor you cannot break

Every so often someone claims a revolutionary compressor that shrinks anything — random data, already-zipped files, whatever — by 50%. It's always false, and not because engineers aren't clever enough. It's mathematics.

Shannon's source coding theorem says: a source with entropy H bits per symbol cannot be losslessly encoded in fewer than H bits per symbol on average. Entropy — the average surprise of the source, unpacked with coin-flip arithmetic in Shannon entropy explained — is the incompressible core. English text has entropy of roughly 1 bit per character — modern estimates mostly land between 1 and 1.3 (Shannon estimated this himself with a lovely experiment: have people guess the next letter of a text, and measure how good their guesses are). Since ASCII spends 8 bits per character, an ideal compressor could in theory shrink text by a factor of 5 to 8; real general-purpose compressors typically manage 2-to-4-to-1, because they can't exploit every regularity a human reader would. But no lossless algorithm will ever break through the entropy floor, because what remains is genuine information.

Data that's already random — encrypted files, or the output of a good compressor — has entropy nearly equal to its length. There is nothing predictable left to remove, which is why zipping a ZIP accomplishes nothing. Compression is a one-time harvest of predictability.

There's a beautiful pincer here, worth pausing on. Compression removes redundancy to make data small; error-correcting codes then add redundancy back — but carefully structured redundancy, designed to survive noise, unlike the accidental kind that was removed. Your phone does both to every photo it sends: squeeze out nature's sloppy redundancy, stamp in engineered redundancy, transmit. And how many bits per second the channel can carry at all is itself capped, by the noisy-channel mathematics in why noise limits communication.

Cheating the floor: lossy compression

So H is an unbreakable floor — for exact reconstruction. But who said reconstruction has to be exact?

A photo straight off a camera sensor might be 30 megabytes. The JPEG is 3. No lossless scheme can do that to photographic data, and JPEG doesn't try: it throws information away, permanently, choosing information your eyes wouldn't have registered. Human vision is sharp on brightness but blurry on color detail, and nearly blind to very fine, low-contrast texture. JPEG converts the image into a form where those components are separated out (a frequency transform, taken 8-by-8 pixel block by block), then stores the visually loud components carefully and the visually invisible ones crudely or not at all. What's left gets losslessly packed with — of course — Huffman-style entropy coding.

MP3 and its successor AAC play the same game with your ears. Psychoacoustics says a loud sound masks quieter sounds near it in frequency and time; the encoder finds the masked sounds and simply doesn't store them. MP4 video adds the biggest saving of all: consecutive frames are nearly identical, so store one frame and then only the changes — motion and difference — for the frames that follow.

The trade is explicit and honest. Lossless (ZIP, PNG, FLAC): perfect restoration, modest savings, mandatory for text and code where one wrong bit is a catastrophe. Lossy (JPEG, MP3, MP4): dramatic savings, and the original is gone forever — re-save a JPEG twenty times and the wounds accumulate. Which is why photographers shoot RAW and studios archive lossless masters, then export lossy copies for the world.

Once you know the pattern, you spot it everywhere — the piece of everyday engineering hiding inside every photo you text. It's exactly the kind of how-things-actually-work story NerdSip bottles into five-minute reads, and compression might be the single most-used algorithm in your day.

The takeaway

Compression works by refusing to store what could be predicted: short codes for common symbols (Huffman), pointers instead of repeated phrases (LZ77/LZ78), and stacked pipelines that expose structure before encoding it. Shannon's entropy H is the hard floor — the average bits per symbol below which no lossless scheme can go, because what remains is pure surprise. Lossy formats duck under the floor only by redefining the goal: discard what human senses won't miss, then pack the rest. Every file on your phone is a negotiation between those two ideas, settled by a theorem from 1948.