How does compression work? Making files smaller, explained

Data compression is a way of storing the same information in fewer bits. The work it does is finding patterns, such as repeated runs, common letters and recurring phrases, and describing them more briefly than writing them out. Lossless compression, used by ZIP files, rebuilds the original exactly. Lossy compression, used by JPEG photos and MP3 music, throws away detail people barely notice, so it shrinks files much further but can't give the original back.

In short

• Compression saves space by replacing predictable, repeated data with shorter descriptions of it.
• Lossless methods rebuild every bit; lossy methods discard what eyes and ears are least likely to miss.
• There is a hard floor: data with no pattern left, including data already compressed, can't be shrunk further.

Where does the saving come from?

From the fact that most data is predictable. In English text the letter e is far more common than z, "the" turns up constantly, and whole phrases repeat. A photo of a blue sky has thousands of neighboring dots of almost the same color. Yet a computer normally stores each letter in the same 8 bits (one byte, as bits vs bytes explains) and each dot in the same number of bits, however common or rare. Compression exploits the gap between how data is stored and how much information it really holds.

Claude Shannon made that gap measurable in his 1948 paper, A Mathematical Theory of Communication, which founded information theory. He defined a quantity he called entropy: the average number of bits truly needed per symbol, worked out from how probable each symbol is. Rare symbols carry more information, common ones less, and no lossless method can beat the entropy on average. Compression is the craft of getting close to it.

How does lossless compression work? Two methods, by hand

The simplest method is run-length encoding: write each run of repeated symbols as a count and the symbol. Take a row of a black-and-white image as 28 letters, W for white and B for black: twelve W, one B, twelve W, three B. Written out, it takes 28 characters. Run-length encoded, it is "12W1B12W3B", 10 characters. The method is useless on data without runs: "ABCD" becomes "1A1B1C1D", twice as long.

A cleverer method gives common symbols short codes and rare ones long codes, as Morse code does with the single dot for E. David Huffman, then a graduate student at MIT, published the best way to choose such codes in 1952. Build one for the word ABRACADABRA, 11 letters:

1. Count. A appears 5 times, B 2, R 2, C 1 and D 1.
2. Join the two rarest. C and D (1 each) join into a group with a count of 2.
3. Repeat. The rarest are now B (2), R (2) and the CD group (2). Join B and R into a group of 4.
4. Repeat. Join the CD group (2) and the BR group (4) into a group of 6.
5. Finish. Join A (5) and the group of 6 into one tree of 11.
6. Read off the codes. Walk down the tree, writing 0 for one branch and 1 for the other. A gets 0; C gets 100, D 101, B 110 and R 111.

Now count the bits. A is 5 × 1 bit, and the other six letters take 3 bits each, 18 in all: 23 bits. Stored as ordinary text, at 8 bits a letter, ABRACADABRA takes 88 bits; even a fixed code of 3 bits for each of the 5 letters takes 33. Shannon's entropy for these letter counts works out at about 22.4 bits, so the Huffman code lands within one bit of the limit. And because no code is the start of another, 0110111 can only mean A, B, R: the decoder needs no spaces. The tree is a data structure, built by a simple algorithm that always merges the two smallest counts.

Real tools combine tricks. ZIP and gzip use DEFLATE, specified in RFC 1951: it first replaces repeated strings with short pointers back to an earlier copy ("the next 12 characters are the same as the 12 that started 340 characters ago"), a method from Abraham Lempel and Jacob Ziv's 1977 work, then Huffman-codes the result.

How does lossy compression work?

By deciding that some information isn't worth keeping. Human senses have blind spots, and lossy formats are built around them. JPEG, the photo standard created in 1992 according to the JPEG committee, splits an image into 8 × 8 blocks of pixels and rewrites each as a mix of smooth gradients and fine ripples. Eyes are poor at seeing very fine detail, and poorer still at fine detail in color, so JPEG stores those ripples roughly or drops them, keeps the broad shapes, and then compresses what's left losslessly. The quality slider in an image editor sets how much to throw away.

MP3 and AAC do the same for sound. A loud sound masks quieter ones at nearby pitches, for a moment, so the encoder spends few or no bits on what would be drowned out anyway. Video formats add another saving: most of each frame is the same as the frame before, so they store mainly what moved.

Format	Lossless or lossy	Typical use	Main trick
ZIP, gzip	Lossless	Documents, software, web pages	Back-references to repeats, then Huffman codes
PNG	Lossless	Screenshots, logos, diagrams	Predicts each pixel from its neighbors, then DEFLATE
FLAC	Lossless	Music archives	Predicts the sound wave and stores only the errors
JPEG	Lossy	Photos	Drops fine detail the eye barely sees
MP3, AAC	Lossy	Music, podcasts	Drops sounds that louder sounds mask
H.264, AV1	Lossy	Video	Stores mostly the changes between frames

The trade is clear-cut. Use lossless for anything that must come back exactly, such as text, code, spreadsheets and medical scans. Use lossy where a close copy is fine, and save the original, because every re-save of a JPEG throws a little more away.

Why doesn't a ZIP of a ZIP get smaller?

Because the first pass already removed the patterns. Compressed data looks random, and random data has nothing left to describe more briefly. It can be measured: compressing an 8,604-byte English text with gzip at its strongest setting gave 3,858 bytes, 45% of the original. Compressing that result again gave 3,881 bytes, 23 bytes larger. Random data of the same size, 8,604 bytes, compressed the same way, came out at 8,627. And 10,000 copies of the letter A came out at 46 bytes.

There is also a simple counting reason no method can shrink everything. There are 2ⁿ different files of n bits, but only 2ⁿ − 1 files shorter than that, counting every length from zero up. A lossless compressor must turn different files into different outputs, or it couldn't undo itself, so if it shortens some files it must lengthen others. Every lossless compressor is a bet that the data has patterns, and it wins only on data that does. That is why claims of a program that shrinks any file, again and again, are always false.

The limit depends on the model of the data, which is where probability comes in. A compressor that predicts the next letter better needs fewer bits for it, which is why the best modern text compressors are built around prediction, the same job a language model does.

Check yourself

• Without looking back, build the Huffman code for the word BANANA and count its bits.
• What does a lossy format throw away, and why is it safe to throw away?
• Explain the counting argument for why no compressor can make every file smaller.

Sources

• A Mathematical Theory of Communication — Claude Shannon, Bell System Technical Journal, 1948
• RFC 1951, DEFLATE Compressed Data Format Specification version 1.3 — L. Peter Deutsch, RFC Editor, 1996
• JPEG 1 — Joint Photographic Experts Group
• Portable Network Graphics (PNG) Specification — World Wide Web Consortium, 2025
• Huffman coding — Wikipedia