Shannon's source coding theorem: you can't compress below entropy

Can you squeeze endless text into fewer bits without losing anything?

Imagine trying to pack an infinite number of identical books into a finite space without leaving any out.

Shannon's theorem tells us that there's a limit to how much we can compress data without losing information. It's like trying to fit an endless series of identical books into a finite space; you can't compress them below their entropy without risking loss.

Example

If each book (data) is unique and you have an infinite collection, you can't compress them into fewer bits (space) than what's dictated by their entropy (size).

Remember this

You can't compress data below its entropy without losing information.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

Huffman coding

Huffman coding is an entropy-optimal prefix code for lossless data compression

Rate-distortion theory: minimum bits to represent data within distortion D

How many bits do we need to perfectly copy a song?

Kolmogorov complexity

Kolmogorov complexity is uncomputable

GPTQ quantization does

Post-training quantization using second-order information for model compression

Vector quantization

How can you store a huge library of books in a tiny closet?

Entropy H = -Σ p(x) log₂ p(x) measures average surprise in bits

How do we measure uncertainty in everyday decisions?

Swipe through 100 ML concepts daily

Open Pocket Polymath