Shannon Entropy

Claude Shannon (1948) defined the information content of a symbol with probability p as -log2(p) bits.

Intuition: a coin flip (p=0.5) carries 1 bit of info. A 1-in-256 event (p=1/256) carries 8 bits. A near-certain event (p=0.99) carries only 0.014 bits.

The entropy of a source is the expected information per symbol:

H(X) = -sum_x  p(x) * log2(p(x))

H is measured in bits per symbol. For our purposes (per-byte compression), it's bits per byte.

Uniform 8-bit:   H = 8 bits/byte (incompressible)
English text:    H ≈ 4-5 bits/byte
Source code:     H ≈ 3-4 bits/byte (lots of repetition)

The compression ratio lower bound is:

compressed_size >= H(X) * input_length / 8 bytes

Practical compressors (gzip, zstd, brotli) get close to H but never beat it for memoryless models. Adaptive models that exploit context (current byte depends on previous N bytes) can do better — that's PPM, BWT, and Lempel-Ziv methods.

For this lesson, we just compute H from a frequency table.