Source coding: compression is prediction

Before this lesson: lesson 01 (surprisal, entropy, the question game), lesson 02 (the chain rule, used for blocks of symbols), lesson 03 (KL divergence, Gibbs' inequality) and lesson 04 ($H(p, q) = H(p) + \mathrm{KL}(p\,\|\,q)$, bits per byte). Time: about 70 minutes, plus the notebook.

---

Why this matters #

Lesson 01 called entropy "the average number of yes/no questions". This lesson makes that exact: entropy is the smallest average number of bits per symbol that any lossless code can reach. This turns log-loss into a physical quantity.

• Language models report losses in bits per byte (lesson 04). With arithmetic coding, that number is the size of the compressed text. Delétang et al. (2024) show that large language models are strong general-purpose compressors.
• Every compressor ends with an entropy coder: zip, gzip and PNG (Huffman coding), JPEG, zstd (Huffman and asymmetric numeral systems), learned image codecs (arithmetic coding with a neural model).
• Model compression: quantized weights are often entropy-coded, and the entropy of the quantized values is a lower bound on the bits per weight of such a code.
• Minimum description length (MDL) chooses between models by the total length of model plus data: a principled form of Occam's razor.

As in the whole track, $\log$ is the natural log (nats) and $\log_2$ gives bits. In this lesson all code lengths and entropies are in bits. We write $\mathrm{KL}_2(p\,\|\,q)$ for the KL divergence in bits ($\mathrm{KL}$ in nats divided by $\ln 2$).

1. Predict first #

2. The picture #

Fixed length vs variable length #

Four symbols $a, b, c, d$ have probabilities $(\frac12, \frac14, \frac18, \frac18)$. A fixed-length code ($00, 01, 10, 11$) needs 2 bits per symbol. Now try a variable-length code: $a = 0$, $b = 10$, $c = 110$, $d = 111$. On average it needs

This is exactly the entropy $H = 1.75$ bits. Look at the lengths: each one equals the surprisal $-\log_2 p$ of its symbol ($-\log_2 \frac12 = 1$, $-\log_2 \frac14 = 2$, $-\log_2 \frac18 = 3$). This code is the question game of lesson 01: the bits are the answers to "is it $a$?", "is it $b$?", "is it $c$?".

Prefix-free codes decode instantly #

A code is prefix-free (also called a prefix code) when no codeword is the beginning of another codeword. Then you can read the bits from left to right and output a symbol as soon as a codeword is complete. You need no separators:

Step by step: the first bit $0$ is a codeword ($a$), so output $a$. The next bits $1$, $11$ are not codewords, $110$ is ($c$). The last three bits $111$ give $d$.

The code tree and the budget #

Draw each codeword as a path in a binary tree: $0$ = go left, $1$ = go right. A code is prefix-free exactly when every codeword is a leaf: no codeword lies on the path to another one.

Now the key picture. Read a codeword $c$ of length $l$ as the binary fraction $0.c$. All infinite bit strings that start with $c$ fill an interval of length $2^{-l}$ in $[0, 1)$. For example, $10$ owns $[0.10_2, 0.11_2) = [0.5, 0.75)$, an interval of length $2^{-2} = \frac14$.

• Prefix-free means that these intervals do not overlap.
• The intervals lie inside $[0, 1)$, so their lengths add up to at most 1.

So a code has a budget of 1, and a codeword of length $l$ costs $2^{-l}$ of it. Short codewords are expensive: a 1-bit codeword uses half of the budget. How should you spend the budget? Give each symbol a share close to its probability: $2^{-l_i} \approx p_i$, that is, $l_i \approx -\log_2 p_i$. This is the whole theory in one line. Section 3 makes it exact.

Interactive figure: loading…

3. Definitions and main results #

Setup. A source $X$ takes values $1, \dots, K$ ($K \ge 2$) with probabilities $p_1, \dots, p_K > 0$.

• A binary symbol code gives symbol $i$ a codeword $c_i$, a string of bits of length $l_i$.
• The expected length is $L = \sum_i p_i l_i$ bits per symbol.
• A code is uniquely decodable if every concatenation of codewords can be split in only one way.
• A code is prefix-free if no codeword is a prefix of another. Prefix-free codes are uniquely decodable, and they decode instantly.
• $L^*$ is the smallest expected length over all prefix codes.
• A code with $\sum_i 2^{-l_i} = 1$ is complete.

3.1 The Kraft inequality #

Theorem 1 (Kraft inequality). (a) The lengths of every binary prefix code satisfy $\sum_{i=1}^K 2^{-l_i} \le 1$. (b) Conversely, if positive integers $l_1, \dots, l_K$ satisfy $\sum_i 2^{-l_i} \le 1$, then there is a prefix code with these lengths.

Proof of (a), with the tree.

1. Let $l_{\max} = \max_i l_i$. The bit strings of length $l_{\max}$ are the $2^{l_{\max}}$ leaves of the full binary tree of depth $l_{\max}$.
2. The codeword $c_i$ has $2^{l_{\max} - l_i}$ descendants among these leaves: the strings that start with $c_i$.
3. Prefix-free means that these sets of descendants are disjoint. (A string that starts with both $c_i$ and $c_j$ would make one of them a prefix of the other.)
4. So $\sum_i 2^{l_{\max} - l_i} \le 2^{l_{\max}}$. Divide by $2^{l_{\max}}$. $\blacksquare$

Proof of (b), with intervals.

1. Sort the lengths: $l_1 \le l_2 \le \dots \le l_K$. Let $F_i = \sum_{j<i} 2^{-l_j}$, so $F_1 = 0$. Kraft gives $F_i + 2^{-l_i} \le 1$.
2. Every term $2^{-l_j}$ with $j < i$ is a whole multiple of $2^{-l_i}$, because $l_j \le l_i$. So $F_i$ is a multiple of $2^{-l_i}$, and its binary expansion ends after $l_i$ digits. Let $c_i$ be these $l_i$ digits.
3. The binary fractions that start with $c_i$ form the interval $[F_i, F_i + 2^{-l_i})$. These intervals are laid end to end, so they do not overlap.
4. If $c_i$ were a prefix of $c_j$, the interval of $c_j$ would lie inside the interval of $c_i$. Disjoint intervals rule this out. $\blacksquare$

Example. Lengths $(1, 2, 3, 3)$ give $F = 0, 0.5, 0.75, 0.875$. In binary these are $0.0_2, 0.10_2, 0.110_2, 0.111_2$, so the code is $0, 10, 110, 111$.

McMillan's theorem. Every uniquely decodable code also satisfies the Kraft inequality. So restricting to prefix codes loses nothing: for every uniquely decodable code there is a prefix code with the same lengths.

Proof of McMillan's theorem

Let $S = \sum_i 2^{-l_i}$ for a uniquely decodable code, and let $n \ge 1$.

1. Expand the power: $S^n = \sum_{i_1, \dots, i_n} 2^{-(l_{i_1} + \dots + l_{i_n})}$. Each term belongs to one sequence of $n$ symbols, and the exponent is the length of its encoded bit string.
2. Group the terms by this length $m$, which lies between $n$ and $n\,l_{\max}$. Let $A_m$ be the number of symbol sequences whose encoding has $m$ bits. Then $S^n = \sum_{m=n}^{n l_{\max}} A_m 2^{-m}$.
3. Unique decodability means that different symbol sequences give different bit strings. There are only $2^m$ bit strings of length $m$, so $A_m \le 2^m$.
4. Hence $S^n \le n\,l_{\max} - n + 1 \le n\,l_{\max}$ for every $n$.
5. If $S > 1$, the left side grows exponentially in $n$ and the right side only linearly, which is impossible for large $n$. So $S \le 1$. $\blacksquare$

(MacKay, Information Theory, Inference, and Learning Algorithms, §5.2.)

3.2 The entropy bound (source coding theorem) #

Theorem 2 (entropy bound). Every prefix code (indeed every uniquely decodable code) has $L \ge H(X)$, with equality if and only if $p_i = 2^{-l_i}$ for all $i$. There is a prefix code with $L < H(X) + 1$. Hence

Why this is true (intuition). Every code "believes in" a distribution: the shares $2^{-l_i}$ of the budget. Using a code is like using a model. By Gibbs' inequality (lesson 03), coding with any model other than $p$ costs extra bits. Integer lengths cost less than 1 extra bit because rounding $-\log_2 p_i$ up adds less than 1.

Proof.

1. Let $Z = \sum_j 2^{-l_j}$. Then $Z \le 1$ by Kraft (or McMillan). Define $r_i = 2^{-l_i}/Z$. This is a probability distribution: the implicit distribution of the code.
2. Write $l_i = -\log_2 r_i - \log_2 Z$. Then

3. $\mathrm{KL}_2(p\,\|\,r) \ge 0$ by Gibbs' inequality, and $-\log_2 Z \ge 0$ because $Z \le 1$. So $L \ge H$.
4. Equality needs both terms to be 0: $r = p$ and $Z = 1$. That is, $p_i = 2^{-l_i}$ for all $i$ (dyadic probabilities, powers of $\frac12$).
5. Upper bound. Take the Shannon lengths $l_i = \lceil -\log_2 p_i \rceil$ (round up). From $l_i \ge -\log_2 p_i$ we get $2^{-l_i} \le p_i$, so $\sum_i 2^{-l_i} \le \sum_i p_i = 1$, and Theorem 1(b) gives a prefix code with these lengths. From $l_i < -\log_2 p_i + 1$ we get $L < H + 1$.
6. $L^*$ is at most the length of this code, and at least $H$ by step 3. $\blacksquare$

Blocks of symbols. Code $n$ independent symbols at once, as one "super-symbol" from an alphabet with $K^n$ values. By the chain rule and independence (lesson 02), $H(X_1, \dots, X_n) = nH(X)$. Theorem 2 for the block gives $nH \le L^*_n < nH + 1$. Divide by $n$:

The rounding cost of less than 1 bit is now shared by $n$ symbols. So entropy is the best possible compression rate, and you can get as close to it as you like. This is Shannon's source coding theorem for lossless codes.

Interactive figure: loading…

The cost of a wrong code. If the code is complete ($Z = 1$), step 2 reads $L = H(p) + \mathrm{KL}_2(p\,\|\,r)$ with $r_i = 2^{-l_i}$. Every code is a model, and its excess length is the KL divergence from the true distribution to the code's implicit distribution. Section 3.5 comes back to this.

3.3 The Huffman code #

Shannon lengths prove the bound, but they are not optimal. Huffman's algorithm (1952) finds the best prefix code for a known distribution.

The idea: the two least likely symbols should get the longest codewords, and these codewords should differ only in the last bit. Merging them reduces the problem to $K - 1$ symbols.

Interactive figure: loading…

Ties. For $p = (0.4, 0.2, 0.2, 0.1, 0.1)$, the algorithm can break ties in different ways. One choice gives lengths $(2, 2, 2, 3, 3)$, another gives $(1, 2, 3, 4, 4)$. Both have $L = 2.2$ bits, and $H = 2.122$ bits. Ties can change the tree, even the set of lengths, but never the expected length.

Theorem 3 (Huffman is optimal). For a known distribution $p$, no prefix code has a smaller expected length than the Huffman code. By McMillan's theorem, no uniquely decodable symbol code has either.

Proof of Theorem 3 (exchange and induction)

Order the symbols so that $p_{K-1}$ and $p_K$ are the two smallest probabilities.

1. Swap. In an optimal code, $p_i > p_j$ implies $l_i \le l_j$. If not, swap the two codewords: $L$ changes by $(p_i - p_j)(l_j - l_i) < 0$, which contradicts optimality.
2. No lonely nodes. In the tree of an optimal code, every internal node has two children. If a node had only one child, delete that branch's bit from every codeword below it. The code stays prefix-free and gets shorter. So a longest codeword has a sibling, and that sibling is also a codeword of maximal length.
3. Siblings. By steps 1–2, some optimal code gives symbols $K-1$ and $K$ codewords of maximal length. Exchanging codewords among leaves of maximal length does not change $L$, so we may assume that $K-1$ and $K$ are siblings.
4. Merge. Merge symbols $K-1$ and $K$ into one symbol with probability $p_{K-1} + p_K$. This gives a source $p'$ with $K - 1$ symbols. A code $C'$ for $p'$ becomes a code $C$ for $p$ when the merged leaf gets two children. Then $L(C) = L(C') + p_{K-1} + p_K$, because both symbols pay one extra bit. In the other direction, the optimal code of step 3 merges into a code for $p'$ with the same relation. Together: $L^*(p) = L^*(p') + p_{K-1} + p_K$.
5. Induction on $K$. Huffman's first step is exactly this merge, and the rest of Huffman builds a code for $p'$. For $K = 2$, Huffman gives $0, 1$, which is optimal. If Huffman is optimal for $K - 1$ symbols, step 4 gives $L(\text{Huffman}(p)) = L^*(p') + p_{K-1} + p_K = L^*(p)$. $\blacksquare$

Consequences: Huffman codes are complete (Kraft sum 1), and $H \le L_{\text{Huffman}} < H + 1$, because $L_{\text{Huffman}} = L^*$.

Weaknesses.

• The extra bit. Lengths are whole numbers, so every symbol costs at least 1 bit. For a coin with $P(\text{heads}) = 0.99$, $H = 0.081$ bits, but Huffman needs 1 bit per flip.
• A fixed distribution. If the probabilities depend on the context (the previous characters) or change over time, you need a new code for each context.
• Fix 1: blocks. The overhead drops below $1/n$ bit per symbol, but the alphabet grows like $K^n$.
• Fix 2: arithmetic coding (next section).

3.4 Arithmetic coding #

Arithmetic coding removes the "extra bit per symbol". It codes a whole sequence $x_1, \dots, x_n$ as one number in $[0, 1)$.

1. Start with the interval $[0, 1)$.
2. For each symbol $x_t$: split the current interval into pieces, one per possible symbol, with lengths proportional to the model's probabilities $q(x_t \mid x_{<t})$. Keep the piece of the symbol that actually comes.
3. After $n$ symbols, the interval has width $w = q(x_1) \, q(x_2 \mid x_1) \cdots q(x_n \mid x_{<n}) = q(x_{1:n})$, by the chain rule of probability.
4. Send the shortest binary fraction whose whole dyadic interval lies inside the final interval. This needs at most $\lceil -\log_2 w \rceil + 1 < -\log_2 q(x_{1:n}) + 2$ bits.

The decoder runs the same model: it splits $[0, 1)$ the same way, sees which piece contains the received number, outputs that symbol, and repeats. It must also know $n$ (or the model has an end-of-message symbol).

Small example. Model $q(a) = 0.8$, $q(b) = 0.2$; sequence $a\,a\,b\,a$.

step	symbol	interval	width
0	—	$[0, 1)$	1
1	$a$	$[0, 0.8)$	0.8
2	$a$	$[0, 0.64)$	0.64
3	$b$	$[0.512, 0.64)$	0.128
4	$a$	$[0.512, 0.6144)$	0.1024

$-\log_2 0.1024 = 3.29$ bits. The 5-bit fraction $0.10001_2 = 0.53125$ owns $[0.53125, 0.5625)$, which lies inside the final interval, so the codeword is $10001$: 5 bits, below the bound $3.29 + 2$. For short sequences the "+2" matters; for long ones it does not. For $a\,a\,a\,a\,b\,a\,a\,a$ this model needs 6 bits, the uniform model 8 bits, and the model $q(a) = 0.2$ needs 17 bits.

Interactive figure: loading…

Any model works, as long as the decoder can run it too: fixed probabilities, counts that adapt as the data arrive, or a neural network that predicts the next token. Modern entropy coders such as asymmetric numeral systems (ANS) reach the same lengths and run faster.

3.5 Compression = prediction #

Put the pieces together.

• With a model $q$, the ideal code length of $x$ is $-\log_2 q(x)$ bits. Arithmetic coding reaches it for a whole sequence within 2 bits; Shannon lengths $\lceil -\log_2 q \rceil$ reach it within 1 bit per symbol.
• If the data come from $p$, the expected ideal length is the cross-entropy (lesson 04):

A wrong model costs exactly $\mathrm{KL}_2(p\,\|\,q)$ extra bits per symbol. With Shannon lengths for $q$: $H(p) + \mathrm{KL}_2(p\,\|\,q) \le L < H(p) + \mathrm{KL}_2(p\,\|\,q) + 1$.

• Note the direction: the data come from $p$, the code is designed for $q$, and the cost is $\mathrm{KL}(p\,\|\,q)$, not $\mathrm{KL}(q\,\|\,p)$.

Interactive figure: loading…

Sequences and language models. A language model predicts each token from the earlier ones. By the chain rule of probability, $q(x_{1:n}) = \prod_t q(x_t \mid x_{<t})$, so

The code length of a text is the sum of the per-token losses in bits. So the training loss of a language model, converted to bits, is the length of the text after arithmetic coding with that model. Minimizing cross-entropy is learning to compress. In the other direction, a compressor is a model: a complete code with lengths $l_i$ "believes" the distribution $q_i = 2^{-l_i}$.

Minimum description length (MDL). The decoder must know the model. A fair comparison of two models counts the bits for the model and the bits for the data given the model: $L(\text{model}) + L(\text{data} \mid \text{model})$. A huge model may code the data in few bits but cost many bits itself. MDL picks the model with the smallest total; it is one precise form of Occam's razor.

Answers to section 1. (1) 1 bit. Each symbol needs at least one bit, so $\text{heads} = 0$, $\text{tails} = 1$ is optimal, 0.531 bits above $H$. Coding pairs of flips gives 0.645 bits per flip (section 4), blocks of $n$ flips get within $1/n$ of 0.469, and arithmetic coding gets within 2 bits of $-\log_2 q$ of the whole sequence. (2) $\mathrm{KL}_2(p\,\|\,q)$ bits per symbol with ideal lengths $-\log_2 q$, plus less than 1 bit if the lengths are rounded up to whole numbers. (3) About 250 KB: 2 bits instead of 8 bits per character is a factor of 4, and $10^6 \cdot 2$ bits $= 250\,000$ bytes. The decoder needs the same model, so a fair comparison (MDL, section 3.5) adds the size of the model.

4. Worked example #

(a) A Huffman code by hand. Five symbols $a, b, c, d, e$ with $p = (0.45, 0.25, 0.17, 0.08, 0.05)$.

step	merge the two smallest	new node	nodes left
1	$e$ (0.05) + $d$ (0.08)	$de$ (0.13)	$a$ 0.45, $b$ 0.25, $c$ 0.17, $de$ 0.13
2	$de$ (0.13) + $c$ (0.17)	$cde$ (0.30)	$a$ 0.45, $cde$ 0.30, $b$ 0.25
3	$b$ (0.25) + $cde$ (0.30)	$bcde$ (0.55)	$a$ 0.45, $bcde$ 0.55
4	$a$ (0.45) + $bcde$ (0.55)	root (1)	—

Label the branches: $a$ gets 0 and $bcde$ gets 1; inside $bcde$, $b$ gets 0 and $cde$ gets 1; inside $cde$, $c$ gets 0 and $de$ gets 1; inside $de$, $d$ gets 0 and $e$ gets 1. The code is

• Expected length: $0.45 \cdot 1 + 0.25 \cdot 2 + 0.17 \cdot 3 + 0.08 \cdot 4 + 0.05 \cdot 4 = 0.45 + 0.5 + 0.51 + 0.32 + 0.2 = 1.98$ bits.
• Entropy: the surprisals are $1.152, 2, 2.556, 3.644, 4.322$ bits, so $H = 0.45 \cdot 1.152 + 0.25 \cdot 2 + 0.17 \cdot 2.556 + 0.08 \cdot 3.644 + 0.05 \cdot 4.322 = 1.961$ bits. Check the theorem: $1.961 \le 1.98 < 2.961$ ✓. A fixed-length code would need 3 bits.
• Kraft sum: $\frac12 + \frac14 + \frac18 + \frac1{16} + \frac1{16} = 1$: the code is complete.
• Decoding $0101101110$: $0 \mid 10 \mid 110 \mid 1110 \to a\,b\,c\,d$.

(b) Shannon lengths. $\lceil -\log_2 p_i \rceil = (2, 2, 3, 4, 5)$. The expected length is $0.9 + 0.5 + 0.51 + 0.32 + 0.25 = 2.48$ bits: below $H + 1 = 2.961$, as promised, but 0.5 bits worse than Huffman. The Kraft sum is $\frac14 + \frac14 + \frac18 + \frac1{16} + \frac1{32} = 0.719$: 28% of the budget is wasted.

(c) A wrong model. True $p = (\frac12, \frac14, \frac18, \frac18)$ with $H(p) = 1.75$ bits.

• Use the code for the uniform model $u$ (all lengths 2): $L = 2$ bits. The KL in bits is $\mathrm{KL}_2(p\,\|\,u) = \frac12 \log_2 \frac{1/2}{1/4} + \frac14 \log_2 \frac{1/4}{1/4} + 2 \cdot \frac18 \log_2 \frac{1/8}{1/4} = \frac12 + 0 - \frac14 = 0.25$, and indeed $L = 1.75 + 0.25$.
• The other way round: the code $0, 10, 110, 111$ on uniform data gives $L = \frac14(1 + 2 + 3 + 3) = 2.25 = H(u) + \mathrm{KL}_2(u\,\|\,p) = 2 + 0.25$.

Both results are exact, because every length equals $-\log_2$ of the model probability.

(d) Blocks. The coin with $P(\text{heads}) = 0.9$, $H = 0.469$ bits. One flip at a time: 1 bit. Pairs have probabilities $0.81, 0.09, 0.09, 0.01$. Huffman merges $0.01 + 0.09 = 0.10$, then $0.09 + 0.10 = 0.19$, then $0.19 + 0.81 = 1$. The lengths are $1, 2, 3, 3$, so

below the bound $H + \frac12 = 0.969$. Blocks of 3, 4, 5, 6 flips give $0.533, 0.493, 0.480, 0.470$ bits per flip.

5. In code #

NumPy and SciPy check the hand computations above: the entropy, the expected lengths, the Kraft sums, a brute-force search over all valid length vectors, and the cost of a wrong model.

import itertools
import numpy as np
from scipy.stats import entropy

p = np.array([0.45, 0.25, 0.17, 0.08, 0.05])
huffman = np.array([1, 2, 3, 4, 4])        # lengths of the code built by hand in section 4
shannon = np.ceil(-np.log2(p))             # Shannon lengths
print(shannon)                              # [2. 2. 3. 4. 5.]
print(round(entropy(p, base=2), 4))         # 1.9606  = H in bits
print(round(p @ huffman, 4), round(p @ shannon, 4))       # 1.98 2.48
print((2.0 ** -huffman).sum(), (2.0 ** -shannon).sum())   # 1.0 0.71875  (Kraft sums)

# Brute force over all length vectors that satisfy Kraft: nothing beats 1.98.
grid = np.array(list(itertools.product(range(1, 6), repeat=5)))
ok = (2.0 ** -grid).sum(axis=1) <= 1
print(round((grid[ok] @ p).min(), 4))       # 1.98

# Wrong model: ideal lengths -log2 q(x) cost H(p) + KL(p || q) bits per symbol.
p4, u4 = np.array([1/2, 1/4, 1/8, 1/8]), np.full(4, 1/4)
print(entropy(p4, base=2) + entropy(p4, u4, base=2))    # 2.0   = 1.75 + 0.25
print(entropy(u4, base=2) + entropy(u4, p4, base=2))    # 2.25  = 2 + 0.25

scipy.stats.entropy(p, base=2) is $H(p)$ in bits, and entropy(p, q, base=2) is $\mathrm{KL}_2(p\,\|\,q)$. The notebook builds the Huffman code with heapq, encodes and decodes, and compares model-based code lengths with zlib on real text.

6. Where it shows up #

• File formats. DEFLATE (zip, gzip, PNG) is LZ77 followed by Huffman coding. Baseline JPEG Huffman-codes the quantized DCT coefficients. zstd uses Huffman coding for literals and an ANS coder for the rest.
• Language models as compressors. With arithmetic coding, a model's cross-entropy in bits per token is its compressed size per token. Delétang et al. (ICLR 2024) report that Chinchilla 70B, trained on text, compresses ImageNet patches to 43.4% and LibriSpeech audio to 16.4% of the raw size, better than PNG (58.5%) and FLAC (30.3%), when the model size is not counted.
• Bits per byte (lesson 04) is exactly this compression rate, measured per raw byte so that models with different tokenizers can be compared.
• Tokenizers. Byte-pair encoding (BPE) started as a compression algorithm (Gage, 1994): it replaces frequent pairs of symbols by new symbols. A tokenizer shortens the sequence the model must predict.
• Model compression. Deep Compression (Han, Mao and Dally, ICLR 2016) prunes, quantizes by weight sharing, and Huffman-codes the result: 35× smaller for AlexNet, 49× for VGG-16. After quantization, the entropy of the histogram of the quantized weights is a lower bound on the bits per weight of any code that treats the weights as independent draws from that histogram.
• Learned image compression uses a neural network as the model for arithmetic coding of a quantized latent; this is lossy coding, the topic of lesson 10.
• ML for science. Error-bounded compressors for simulation output (the SZ family) predict each value from its neighbours, quantize the prediction error, and entropy-code the result. A better predictor gives smaller errors with lower entropy: compression = prediction again.

7. Common mistakes #

• "Huffman reaches the entropy." Only for dyadic probabilities (powers of $\frac12$). Otherwise $H < L < H + 1$, and the gap can come close to 1 bit: for $p = (0.99, 0.01)$, $L = 1$ bit but $H = 0.081$ bits.
• "Shannon lengths are optimal." They prove the bound; Huffman can be much better (2.48 vs 1.98 bits above). For $p = (0.9999, 0.0001)$ the Shannon length of the rare symbol is 14 bits, while 1 bit is enough.
• "Each Huffman codeword is at most $\lceil -\log_2 p_i \rceil$ long." False symbol by symbol. For $p = (\frac13, \frac13, \frac14, \frac1{12})$, one Huffman code has lengths $(1, 2, 3, 3)$: the symbol with $p = \frac14$ gets 3 bits, but its Shannon length is 2. Only the average is better.
• "The entropy bound holds for every symbol." It is a bound on the expected length. A single rare symbol can get a codeword much longer than the average.
• Wrong direction of the KL. Data from $p$, code for $q$: the cost is $\mathrm{KL}(p\,\|\,q)$.
• Bits vs nats. Code lengths use $\log_2$; ML losses use $\ln$. Divide nats by $\ln 2 = 0.693$ to get bits.
• Forgetting the model. The decoder needs the code or the model. In MDL its size is part of the total length.
• "A good compressor shrinks every file." There are $2^n$ bit strings of length $n$ and only $2^n - 1$ shorter ones, so no lossless code shortens all of them. Random bits cannot be compressed.

8. Check yourself #

1. Is there a binary prefix code with lengths $(1, 2, 2, 3)$? With $(1, 2, 3, 3)$?
   Answer

   Kraft sums: $\frac12 + \frac14 + \frac14 + \frac18 = 1.125 > 1$, so no. $\frac12 + \frac14 + \frac18 + \frac18 = 1$, so yes: $0, 10, 110, 111$.
2. Build a Huffman code for $p = (0.25, 0.25, 0.2, 0.15, 0.15)$. Give its expected length and the entropy.
   Answer

   Merge $0.15 + 0.15 = 0.30$; then $0.20 + 0.25 = 0.45$; then $0.25 + 0.30 = 0.55$; then $0.45 + 0.55 = 1$. The lengths are $(2, 2, 2, 3, 3)$, for example $00, 10, 01, 110, 111$. $L = 2 \cdot 0.7 + 3 \cdot 0.3 = 2.3$ bits; $H = 2.285$ bits. (MacKay, Example 5.15.)
3. The data are fair coin flips. An arithmetic coder uses the model $q(\text{heads}) = \frac14$, $q(\text{tails}) = \frac34$. About how many bits per flip does it spend, and why?
   Answer

   $H(p, q) = \frac12 \cdot 2 + \frac12 \cdot 0.415 = 1.208$ bits $= H(p) + \mathrm{KL}_2(p\,\|\,q) = 1 + 0.208$. The model error costs 0.208 bits per flip.
4. Why does an optimal prefix code have Kraft sum exactly 1?
   Answer

   If the sum is below 1, the code tree is not full: some internal node has only one child. Deleting that branch's bit from every codeword below it keeps the code prefix-free and lowers $L$ (all $p_i > 0$). So the code was not optimal.
5. A complete code has lengths $(1, 2, 3, 3)$. Which distribution does it "believe in"? What is its expected length on $p = (0.4, 0.4, 0.1, 0.1)$, written as entropy plus KL?
   Answer

   $q = (\frac12, \frac14, \frac18, \frac18)$. $L = 0.4 + 0.8 + 0.3 + 0.3 = 1.8$ bits $= H(p) + \mathrm{KL}_2(p\,\|\,q) = 1.722 + 0.078$.
6. Why can arithmetic coding beat the Huffman code for the coin with $P(\text{heads}) = 0.99$?
   Answer

   Huffman gives every flip its own codeword, so it needs at least 1 bit per flip. Arithmetic coding codes the whole sequence as one interval of width $q(x_{1:n})$ and needs fewer than $-\log_2 q(x_{1:n}) + 2$ bits in total: about $0.081n + 2$ bits for $n$ flips on average.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is a prefix-free code?

   Show answer

2. State the Kraft inequality.

   Show answer

3. Why does a codeword of length $l$ use $2^{-l}$ of the budget?

   Show answer

4. State the entropy bound for the best expected length $L^*$ of a symbol code.

   Show answer

5. What are the Shannon code lengths, and what do they prove?

   Show answer

6. What is the rule of Huffman's algorithm?

   Show answer

7. Compute the Huffman code lengths for $p = (0.4, 0.3, 0.2, 0.1)$.

   Show answer

8. What is the ideal code length of $x$ under a model $q$?

   Show answer

9. How many extra bits per symbol does a code for $q$ cost on data from $p$?

   Show answer

10. Why is a language model's loss a compression rate?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What does entropy mean operationally?" The smallest expected number of bits per symbol for lossless coding, reached in the limit of long blocks.
• "Prove the Kraft inequality." Disjoint sets of descendants in the code tree, or disjoint intervals of length $2^{-l_i}$ in $[0, 1)$.
• "Is Huffman optimal? Then why use arithmetic coding?" Huffman is optimal among symbol codes for a fixed, known $p$. But it pays up to 1 bit per symbol and adapts badly. Arithmetic coding gets within 2 bits of $-\log_2 q$ of the whole message, with any adaptive model.
• "Why is cross-entropy a compression objective?" The model spends $-\log_2 q(x)$ bits on $x$; the expected excess over the entropy is $\mathrm{KL}(p\,\|\,q)$.
• "Can you compress uniformly random bits?" No. Their entropy is 1 bit per bit, and by counting, no lossless code shortens every string.
• "Your LM has 0.9 bits per byte. What does that mean?" With arithmetic coding, the model would store the text in 0.9 bits per raw byte, about 11% of the original size, not counting the model.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. huffman_code(probs) with heapq; check that the code is prefix-free and complete.
2. encode and decode for a prefix code, and a round trip on a random message.
3. Brute force: no length vector that satisfies Kraft beats Huffman on a small example.
4. block_rate(probs, n): bits per symbol of Huffman codes on blocks, for the coin with $P(\text{heads}) = 0.9$ and $n = 1, \dots, 6$.
5. Code a text with a unigram model and a bigram (previous-character) model: ideal code lengths compared with zlib.

11. Watch and read #

Huffman Codes: An Information Theory PerspectiveReducible · 29 min

Prefix codes as trees, the entropy bound, and Huffman's algorithm with clear animations.

Lecture 4: Entropy and Data Compression (III): Shannon's Source Coding Theorem, Symbol CodesJakob Foerster · David MacKay's Cambridge lectures · 57 min

Symbol codes, the Kraft inequality as a budget, and the bound H ≤ L < H + 1.

Lecture 5: Entropy and Data Compression (IV): Shannon's Source Coding Theorem, Symbol CodesJakob Foerster · David MacKay's Cambridge lectures · 63 min

The weaknesses of Huffman codes and arithmetic coding with an adaptive model.

• David MacKay, Information Theory, Inference, and Learning Algorithms (free PDF): §5.1–5.6 (symbol codes, Kraft, implicit probabilities, Huffman and its weaknesses) and §6.2 (arithmetic coding).
• Stanford EE274 (Data Compression) notes: prefix-free codes, Huffman codes and arithmetic coding.
• Delétang et al., Language Modeling Is Compression (ICLR 2024): §2 (arithmetic coding, and why compressing well means modelling well in log-loss) and §3 (experiments).