Entropy: why some data compresses and some never will
Information is surprise. Learn Shannon's measure, why it sets a hard floor on compressed size, and why random and encrypted data cannot be shrunk at all.
Lossless compression reproduces the input exactly: text, code, JSON, executables. Lossy compression keeps what matters and discards the rest: JPEG, MP3, video, and, as we will see, summarising an agent's context. This module is mostly about lossless compression, where the rules are precise.
Information is surprise
If you can predict the next symbol perfectly, it carries no information: you did not need to be told. If it is a coin flip, it carries one bit. Shannon defined the information of a symbol with probability p as −log₂ p bits, and the entropy of a source as the average over all symbols. Entropy is the minimum average number of bits per symbol any lossless code can achieve for that source model.
Measure the surprise in a string
␠8×2.43 bitso4×3.43 bitse3×3.84 bitsh2×4.43 bitsr2×4.43 bitst2×4.43 bitsu2×4.43 bitsa1×5.43 bitsb1×5.43 bitsc1×5.43 bitsd1×5.43 bitsf1×5.43 bits- + 15 rarer symbols
- Characters
- 43
- Entropy
- 4.39 bits/char
- Floor for this model
- 189 bits
- As 8-bit text
- 344 bits
- Probabilities
- A = 0.5, B = 0.25, C = 0.25
- Ideal code lengths
- A: −log₂ 0.5 = 1 bit; B and C: −log₂ 0.25 = 2 bits
- A matching code
- A =
0, B =10, C =11 - Average
- 0.5 × 1 + 0.25 × 2 + 0.25 × 2 = 1.5 bits per symbol
- Fixed-width alternative
- 2 bits per symbol (3 symbols need 2 bits)
25% smaller, and 1.5 bits is exactly the entropy: no lossless code can do better for this source.
The model is everything
Entropy depends on the model of the data. Counting single letters, English text measures about 4 bits per character. A model that knows q is almost always followed by u, or that predicts whole words, sees far less surprise; strong text compressors reach around 2 bits per character, and language models lower still. Every better compressor is, at heart, a better predictor.
What cannot be compressed
There are 2^n possible n-bit inputs, but fewer than 2^n shorter outputs. So no lossless compressor can shrink every input; any that shrinks some must grow others. Data that is already random, or already compressed, or encrypted, looks uniformly random and has no pattern to exploit. Compressing it adds a few bytes of header.
Go deeperRun-length encoding, the simplest model
Run-length encoding replaces a run of identical symbols with the symbol and a count: AAAAAABBB becomes 6A3B. Its model is “the next symbol is probably the same as the last one”. It is excellent for that kind of data, such as simple images, sparse bitmaps and sorted columns, and worse than useless on text, where it doubles the size of ABCD.
It survives inside sophisticated systems exactly where its model is right: Parquet's run-length encoding of sorted or low-cardinality columns, fax machines, and the zero runs in many binary formats.
Where you will meet it
Servers skip gzip for JPEG, PNG, MP4 and zip files: they are already compressed, and recompressing wastes CPU.
Backup tools compress before encrypting. Tools that encrypt first cannot deduplicate or compress at all.
Databases sort or cluster data so that columns have long runs and low entropy, then compress far better.
Words to know
- Lossless / lossy
- Exact reconstruction versus keeping only what matters.
- Entropy
- The average information per symbol, the floor for lossless coding under a model.
- Model
- A compressor's prediction of what comes next.
- Run-length encoding
- Replacing a run of repeated symbols with one symbol and a count.
Check yourself
Answer out loud before you open each one.
What is the entropy of a fair coin, and of a coin that lands heads 90% of the time?
1 bit; about 0.47 bits (0.9 × 0.152 + 0.1 × 3.32).
Why can no compressor shrink every input?
There are fewer shorter strings than inputs, so some inputs must map to equal or longer outputs.
Why does encrypted data not compress?
Good encryption output is statistically indistinguishable from random data, which has no redundancy.
Try it
Run head -c 1000000 /dev/urandom | gzip | wc -c and compare it to gzipping a 1 MB log file. Then gzip the gzip output and see it grow.