Lossless compression

The MP3 encoder makes audio smaller by throwing away what you can’t hear. Lossless compression can’t throw anything away: whatever comes out of the decompressor must be identical, bit for bit, to what went in. Zip files, PNG images and FLAC audio all work this way. So how can a file get smaller without losing anything?

The answer, which this page builds up to, is prediction. If you can guess what’s coming next, you don’t need many bits to confirm the guess, and you only need a lot of bits when the guess is wrong. Every method here is a way of predicting, and the entropy from the Shannon limit page measures how well any method using a given prediction can possibly do.

A few terms first:

A bit is a 0 or a 1, and a byte is 8 bits. A plain text file stores each character as one byte (accented letters and symbols take two or three).
To compress is to turn a file into a shorter one; to decompress is to turn it back.
A code gives each symbol (a character, say) a codeword: the bits that stand for it.

Most figures below compress the text chosen here. Try the short passage, the first chapter of Alice’s Adventures in Wonderland (longer, so the methods that learn have more to learn from), or anything you like.

1 · What compression can’t do

Before any methods, a limit. No lossless compressor can shrink every file. It’s a matter of counting. There are $2^n$ different files of exactly $n$ bits, but only $2^n - 1$ files shorter than that, counting every length from 0 bits up to $n - 1$ . If a compressor made every $n$ -bit file shorter, two different files would have to come out the same, and then the decompressor couldn’t tell which one to give back.

How many different files there are of each length, up to the chosen length (orange).

There are 256 files of exactly 8 bits, but only 255 shorter ones, so at least one 8-bit file can’t get shorter at all. And at most 127 of the 256 (49.6%) can shrink by 2 bits or more: there are only that many files of 6 bits or fewer.

So a compressor that shrinks some files must make others bigger. It wins only because the files people actually have aren’t typical of all possible files. Text, pictures and sound have patterns, and a compressor’s job is to give the patterned files short versions, and leave the patternless ones (which nobody has) to grow a little.

2 · The naive approach: run-length encoding

The simplest pattern is repetition. Run-length encoding replaces a run of identical things with a count: “AAAAAAB” becomes “6 A, 1 B”. Fax machines used it, because a page is mostly long runs of white.

The picture: 64 × 32 pixels, each black or white. Orange marks show where each run ends; on the right, the run lengths of every other row. The readouts also run-length encode the chosen text, sending each run as two bytes (a count and the character).

The picture takes 256 bytes at 1 bit per pixel, and 95 bytes as runs (one byte each): 37.1% of the size. But the short passage, 1,097 bytes, grows to 2,150 bytes (196.0%): 98.0% of its runs are just one character long, and each one now costs two bytes instead of one.

Run-length encoding knows only one kind of pattern, and English doesn’t have it. Doubled letters are about as long as runs get. The rest of the page finds patterns that text does have.

3 · Variable-length codes

Text stores every character in 8 bits, whether it’s an “e”, which is everywhere, or a “z”, which is rare. A better plan is to give common characters short codewords and rare ones long codewords, as Morse code does: E is a single dot, Q is four symbols.

But Morse code needs a gap between letters, or ”…” could be S or EEE or IE. A code that needs no gaps must be prefix-free: no codeword may be the beginning of another. Then a decoder reading bits always knows when a codeword has ended.

A prefix-free code is easiest to see as a tree. Start at the top; each 0 goes left and each 1 goes right; and every codeword ends at a leaf, a node with nothing below it. To decode, walk down the tree bit by bit until you reach a leaf, write down its symbol, and start again from the top.

The tree for the chosen code: each codeword is the path to its symbol (0 left, 1 right). Step through the bits to watch the decoder walk; orange is where it is. The readouts list every message the bits could possibly be.

With the prefix-free code (a = 0, b = 10, c = 110, d = 111), “badcab” is sent as 100111110010 and can only be read back one way. With a = 0, b = 01 and c = 10, which isn’t prefix-free (“0” is the start of “01”), “acb” is sent as 01001, which reads just as well as “bab”.

4 · Entropy is the limit

How short can a prefix-free code be, on average? The Shannon limit page measured a source’s entropy: its average surprise, where a symbol with probability $p$ carries $\log_2(1/p)$ bits of surprise. For a source whose symbols have probabilities $p_1, p_2, \ldots$ ,

H = \sum_i p_i \log_2 \frac{1}{p_i} \ \text{bits per symbol.}

Shannon’s source coding theorem (1948) says that no prefix-free code, coding one symbol at a time, can average fewer bits per symbol than $H$ ; and that some code comes within 1 bit of it. Entropy is the floor. A common symbol (large $p$ ) has little surprise and should get a short codeword; a rare one, a long one.

How often each character occurs in the chosen text (the most common ones), and the entropy of those frequencies. Spaces are shown as ␣, and line breaks as ↵.

The short passage uses 37 different characters, and its entropy is 4.20 bits per character: about half the 8 bits each one is stored in. So a code that treats each character on its own can, at best, store its 1,097 bytes in 577. Chapter 1 of Alice uses 66 different characters, with an entropy of 4.45 bits per character.

This entropy treats each character as if it were drawn at random, regardless of the characters around it. That’s not true of English (after “q” almost always comes “u”), and section 8 uses that. But first, how to build a code that gets close to this floor.

5 · Huffman coding

In 1952, David Huffman, then a student, found the best prefix-free code for any set of frequencies, with a method short enough to do by hand:

Make every symbol a tree of one node, weighed by how often it occurs.
Take the two lightest trees, and join them under a new node whose weight is their total.
Repeat until there’s only one tree.

Each symbol’s codeword is then its path from the top. The rarest symbols were joined first, so they end up deepest, with the longest codewords; the most common were joined last, so they’re near the top.

The tree being built for the phrase “she sells sea shells on the sea shore”, one merge at a time; each node shows its weight, and each line its bit. The table: each character’s count and codeword. Choose the chosen text to see its code (the tree is too big to draw).

For the phrase, the entropy is 2.958 bits per character and Huffman’s code averages 3.027: the 37 characters take 112 bits, against 296 as bytes. For the short passage, Huffman averages 4.242 bits per character, against an entropy of 4.203.

Huffman codes are everywhere: inside zip and gzip files (section 9), JPEG images, and the MP3 encoder’s bitstream, which chooses among 32 fixed Huffman tables for its quantised values. A decoder needs the code too, so a file either uses a code agreed in advance (as MP3 does), or sends its code first (as gzip does), which costs a little extra.

6 · Huffman’s weakness

Huffman’s code is the best one that gives each symbol a whole number of bits. That’s also its limit: every symbol costs at least 1 bit. When some symbol is very common, that’s a lot of waste.

Take the Shannon limit page’s coin, which lands heads 90% of the time. Its entropy is 0.469 bits per flip, but a Huffman code for heads and tails can only be “0” and “1”: 1 bit per flip, more than twice as much. The usual fix is to code blocks of flips together. With two flips at a time there are four blocks (HH, HT, TH, TT), and HH is so common it gets a 1-bit codeword: half a bit per flip.

Huffman’s code for blocks of 1 to 10 flips at a time, in bits per flip, against the entropy (dashed). The orange line is arithmetic coding (next section), coding one flip at a time, measured on 10,000 flips.

With heads 90% of the time, Huffman needs 1.000 bit per flip one at a time, 0.493 four at a time (16 codewords), and 0.477 ten at a time (1,024 codewords), against the entropy’s 0.469. Arithmetic coding, one flip at a time, gets 0.476.

Blocks work, but awkwardly: the table of codewords doubles with every flip added, and the waste only shrinks slowly. There’s a better way.

7 · Arithmetic coding

Arithmetic coding doesn’t give each symbol its own codeword at all. It turns the whole message into a single number between 0 and 1.

Start with the interval from 0 to 1. Split it into one part per symbol, each as wide as that symbol’s probability. The first symbol picks its part, and that part becomes the new interval. Split it the same way, and let the second symbol pick, and so on. Each symbol shrinks the interval by its probability, so after the whole message, the interval’s width is exactly the probability of the whole message.

To send the message, send any binary fraction that lies inside the final interval, such as 0.101 (which is ½ + ⅛). A narrower interval needs more binary places to pin down. An interval of width $w$ needs about $\log_2(1/w)$ bits, and since $w$ is the product of the symbols’ probabilities, that’s the sum of their surprises: exactly the ideal, with no rounding per symbol.

Each row is the interval so far, stretched across the full width, split into each symbol’s share; orange is the share the next symbol picks, which becomes the next row. The numbers above each row are the interval’s two ends.

“SEAT” ends in the interval 0.7536 to 0.7560, of width 0.0024 (0.2 × 0.4 × 0.3 × 0.1), worth 8.70 bits. The binary fraction 0.110000010 lies inside it: the whole word in 9 bits. Ten flips of the 90% coin with one tail (HHHHTHHHHH) leave an interval of width 0.0387, worth 4.69 bits, and need 5.

Real arithmetic coders work with whole numbers, sending bits as soon as the interval’s leading digits are settled, so they never need unlimited precision. The one on this page, decoding included, comes within a couple of bits of the ideal over a whole message. Modern compressors (such as Zstandard, used inside Linux and many web browsers) often use asymmetric numeral systems (ANS), a faster way, invented by Jarek Duda in 2009, of getting the same result.

8 · Better predictions: context

Arithmetic coding takes whatever probabilities it’s given. So the question becomes: how well can we predict the next symbol? Section 4’s entropy used the same probabilities for every character, but English is far more predictable than that. After “th”, “e” is very likely; after “q”, “u” almost certain.

A context model predicts each character from the few before it. An order-2 model, for example, keeps counts of what followed each pair of characters, and uses them for its probabilities. Two refinements make it work:

It’s adaptive: it starts knowing nothing and learns the counts as it goes, so the decoder can learn the same counts, in step, as it decodes. Nothing needs sending ahead.
It blends contexts. A context seen only once or twice is a poor guide, so the model mixes in the prediction from the next shorter context, trusting the longer one more as it gets more familiar (Ian Witten and Timothy Bell’s rule, 1991).

The bars: bits per character for the chosen text, compressed with an adaptive context model of each order and the arithmetic coder, against Huffman’s code (one character at a time) and gzip (section 9). The table: what the model predicts next, after it has read the whole text, given the last few characters of the phrase you type, with each prediction’s cost in bits if it turns out right.

For the short passage, an order-2 model needs 3.73 bits per character, against Huffman’s 4.24. Longer contexts do slightly worse: in 1,097 characters, there’s too little to learn them from. Chapter 1 of Alice has enough: the order-3 model gets down to 2.91 bits per character, better than gzip’s 3.41. After “the”, it predicts a space with a probability of 66.9% (costing 0.6 bits if right), and “r” with 19.0%.

The better the prediction, the fewer bits: the model is the compressor. The best text compressors use enormous models, mixing many kinds of context, and reach well under 2 bits per character on large texts. Today’s large language models are, in this sense, extraordinarily good predictors of text, and so, connected to an arithmetic coder, extraordinarily good (if very slow) compressors.

9 · Dictionary methods: LZ77 and gzip

A different idea, from Abraham Lempel and Jacob Ziv in 1977: instead of predicting characters one by one, notice when a whole stretch of text has appeared before, and refer back to it. “Copy 7 characters, starting 23 back” can replace a repeated phrase, however long. LZ77 reads through the text, and at each point looks back for the longest earlier match: if it finds one at least 3 characters long, it sends a copy; if not, it sends the next character as a literal.

LZ77 on the first 600 characters of the chosen text, one token (a literal or a copy) at a time. Blue shading marks text that was copied; for the current copy, orange is what’s being written, and green is where it’s copied from.

LZ77’s copies are cheap to find and to decode, and they catch long repeats that context models take a while to learn. DEFLATE (Phil Katz, 1993), the method inside zip, gzip and PNG files, combines them: LZ77 first, then Huffman codes for the literals, the copy lengths and the copy distances, with codes chosen for each file and sent at its start.

Here’s a real gzip file of the chosen text, built in stages. The download is a genuine .gz file: your computer’s own tools will decompress it.

Five stages, from the text to the file. 1: LZ77’s tokens. 2: DEFLATE’s symbols: 0–255 for literal bytes, 256 to end the block, 257–285 for copy lengths (each with a few extra bits), and 30 more symbols for copy distances. 3: the Huffman code lengths chosen for those symbols. 4: the bits: first the code tables, then the data. 5: the gzip file around them, with a download button.

The short passage becomes 400 literals and 154 copies, which cover 63.5% of its 1,097 characters. The code tables take 387 bits and the data 4,137 bits, and with gzip’s 18 bytes of header and checksum, the file is 584 bytes (53.2%). zlib, the library inside most gzip tools, makes 577 bytes at its highest setting. Alice’s chapter 1 becomes 4,954 bytes (42.7%).

One more idea is worth knowing, from Michael Burrows and David Wheeler in 1994. Write down every rotation of a text (each one starting one character later and wrapping round), sort them alphabetically, and keep the last character of each. For “banana”, the six sorted rotations end in “nnbaaa”. That jumble can be undone exactly (given which row was the original), and its point is that characters which come just before the same context end up next to each other, so the result has long runs. For “she sells sea shells on the sea shore”, the 35 runs of the original become 22. bzip2 compresses the result with a move-to-front step, run-length and Huffman coding, and often beats gzip on text.

10 · Lossless audio

Audio is a different kind of data. Its samples are numbers that wander smoothly up and down, and the same exact run of numbers almost never repeats, so dictionary methods find little to copy. But each sample is close to what the last few samples suggest, and that’s a pattern of its own.

This is the linear prediction of the voice coding page, used differently. A voice coder sends only rough information about the prediction error; a lossless coder sends the error exactly, so the decoder can rebuild every sample. The errors are much smaller than the samples, so they need fewer bits. This is how FLAC works:

Cut the sound into blocks of 4,096 samples (93 ms at 44.1 kHz).
In each block, choose a predictor: one of a few fixed ones (the last sample; a straight line through the last two; and so on), or a linear predictor fitted to the block. Its coefficients are rounded to whole numbers and sent, so the decoder makes exactly the same predictions.
Send each prediction error with a Rice code: the number divided by $2^k$ in unary (that many 1s, then a 0), then its last $k$ bits as they are. Small numbers get short codes, and $k$ is chosen for each part of the block to suit the size of its errors.

Top: the whole sound, with the chosen block marked. Middle: the block’s samples, and its prediction errors: what’s actually sent. Bottom: the whole sound’s size as 16-bit samples, gzipped, predicted and Rice-coded, and as an MP3 at 128 kbit/s for comparison (lossy, so not a fair fight). Listen to the prediction errors: everything the predictor couldn’t guess. Record your own sound to try it on.

The synthetic speech takes 406,602 bytes as 16-bit samples. gzip gets it down to 77.4%; prediction and Rice codes, to 21.0%, without losing a single bit. An MP3 at 128 kbit/s would be 18.1%, but it isn’t lossless. Noise can’t be predicted: try it, and prediction gets only to 92.9%.

Real recordings, with their background noise and room sound, are harder to predict than this synthetic voice: FLAC’s results on music are usually quoted as 50–70% of the original size. That’s the price of losing nothing: a lossy coder like MP3 can do several times better, by throwing away what you can’t hear.

11 · The limits again

Section 1’s counting says some files must grow. Which ones? Files with no patterns: random data, and data that’s already been compressed, whose patterns have been squeezed out.

The chosen text, the same number of random bytes, and the text’s gzip file, each compressed four ways: run-length encoding, Huffman coding (counting the 256-byte table a decoder would need), an order-2 context model, and gzip. The bars are the size as a share of the original; above the dashed line, the file grew.

The short passage shrinks to 53.2% with gzip. The same number of random bytes grows to 106.3%: gzip finds nothing to copy, and its own header and tables are pure overhead. The passage’s gzip file, compressed again, grows from 584 to 653 bytes (111.8%). Compressing twice never helps.

It’s the same lesson as the Shannon limit: there’s a floor, set by how predictable the data is, and no cleverness gets below it. Compression is prediction, and what can’t be predicted can’t be compressed.

Summary

No lossless compressor can shrink every file: there are fewer short files than long ones. Compression works because real data has patterns.
Run-length encoding catches runs of repeats, and makes most other data bigger.
Prefix-free codes need no gaps between codewords; decoding is a walk down a tree.
Entropy is the floor for any code that takes symbols one at a time.
Huffman coding builds the best such code, by repeatedly joining the two rarest symbols; but every symbol costs at least 1 bit.
Arithmetic coding turns a whole message into one number, and reaches the entropy without rounding.
Context models predict from the characters before, and adapt as they go: the better the model, the smaller the file.
LZ77 copies repeated stretches; DEFLATE (zip, gzip, PNG) adds Huffman codes.
Lossless audio predicts each sample from the last few, and Rice-codes the errors, as FLAC does.
Random and already-compressed data can’t be compressed.