Workspace

Entropy: why some data compresses and some never will

3 day streakD

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.

BasicsLesson 1 of 617 min

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.

Figure 1.1

Measure the surprise in a string

  1. ␠8×2.43 bits
  2. o4×3.43 bits
  3. e3×3.84 bits
  4. h2×4.43 bits
  5. r2×4.43 bits
  6. t2×4.43 bits
  7. u2×4.43 bits
  8. a1×5.43 bits
  9. b1×5.43 bits
  10. c1×5.43 bits
  11. d1×5.43 bits
  12. f1×5.43 bits
  13. + 15 rarer symbols
Characters
43
Entropy
4.39 bits/char
Floor for this model
189 bits
As 8-bit text
344 bits
Type or pick text. The bars show each character's frequency and its ideal code length, −log₂ p. The total is the floor for any coder that treats characters independently. Repetitive text sits far below 8 bits per character; random text approaches its alphabet's limit.
Worked exampleThree symbols, uneven odds
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

Pre-compressed assets

Servers skip gzip for JPEG, PNG, MP4 and zip files: they are already compressed, and recompressing wastes CPU.

Encrypted backups

Backup tools compress before encrypting. Tools that encrypt first cannot deduplicate or compress at all.

Sorted columns

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.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap