Back to the on-screen lesson ·
Merging the two least probable symbols repeatedly; reading lengths and average length.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run Huffman's algorithm by hand and in code, read codeword lengths and codewords from the resulting tree, compute the average length as the sum of the merged weights, and compare it with the entropy. You will prove that Huffman codes are optimal among all uniquely decodable symbol codes through the exchange argument and induction, explain why the gap to the entropy is always below one bit and vanishes exactly for dyadic sources, and say what techniques recover the remaining fraction of a bit.
Huffman's algorithm builds an optimal prefix code from the bottom up. Start with each symbol as a weight equal to its probability. Repeatedly take the two smallest weights, join them under a new node whose weight is their sum, and put that node back in the list; stop when one node remains. Reading the tree from the root, left branch $0$ and right branch $1$, gives the codewords; a symbol's length is the number of merges above it. A useful shortcut: every merge adds one bit to every symbol beneath it, so the average length is the sum of all merged weights. For $(0.4, 0.3, 0.2, 0.1)$ the merges are $0.3, 0.6, 1$, so $L = 1.9$ bits with lengths $1, 2, 3, 3$, against $H = 1.846$. Ties may be broken either way; different trees can result, all with the same optimal $L$. For dyadic probabilities the algorithm reproduces the Shannon lengths and $L = H$.
Another way: picture
Four leaves labelled $0.4, 0.3, 0.2, 0.1$. The two lightest join into a node $0.3$; it joins the other $0.3$ into $0.6$; that joins $0.4$ at the root. Reading down: $0.4 \to 0$, $0.3 \to 10$, $0.2 \to 110$, $0.1 \to 111$.
Another way: steps
Run the algorithm on $(0.4, 0.3, 0.2, 0.1)$, always merging the two smallest weights:
| step | list of weights | merge | new weight |
|---|---|---|---|
| $1$ | $0.4, 0.3, 0.2, 0.1$ | $0.2 + 0.1$ | $0.3$ |
| $2$ | $0.4, 0.3, 0.3$ | $0.3 + 0.3$ | $0.6$ |
| $3$ | $0.6, 0.4$ | $0.6 + 0.4$ | $1.0$ |
| total | $0.3 + 0.6 + 1.0$ | $L = 1.9$ |
The tree gives lengths $1, 2, 3, 3$ and, reading left $= 0$ and right $= 1$, codewords such as $0, 10, 110, 111$. The shortcut in the last row is worth memorising: every merge pushes everything beneath it one level deeper, adding its own weight to the average length, so $$L = \text{sum of all merged weights}.$$ Here $0.3 + 0.6 + 1.0 = 1.9$, and the direct sum $0.4 \cdot 1 + 0.3 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 3 = 1.9$ agrees. The shortcut is faster and needs no codewords at all.
Every practice distribution, with its merge sequence, average length, entropy and gap:
| distribution | Huffman merges | $L$ | $H$ | gap $L - H$ |
|---|---|---|---|---|
| $(0.4, 0.3, 0.2, 0.1)$ | $0.2 + 0.1 = 0.3;\ 0.3 + 0.3 = 0.6;\ 0.6 + 0.4 = 1$ | $1.9$ | $1.846$ | $0.054$ |
| $(0.5, 0.25, 0.125, 0.125)$ | $0.125 + 0.125 = 0.25;\ 0.25 + 0.25 = 0.5;\ 0.5 + 0.5 = 1$ | $1.75$ | $1.75$ | $0$ |
| $(0.6, 0.2, 0.1, 0.1)$ | $0.1 + 0.1 = 0.2;\ 0.2 + 0.2 = 0.4;\ 0.4 + 0.6 = 1$ | $1.6$ | $1.571$ | $0.029$ |
| $(0.4, 0.2, 0.2, 0.2)$ | $0.2 + 0.2 = 0.4;\ 0.2 + 0.4 = 0.6;\ 0.4 + 0.6 = 1$ | $2$ | $1.922$ | $0.078$ |
| $(0.35, 0.3, 0.2, 0.15)$ | $0.2 + 0.15 = 0.35;\ 0.3 + 0.35 = 0.65;\ 0.35 + 0.65 = 1$ | $2$ | $1.926$ | $0.074$ |
| $(0.45, 0.25, 0.15, 0.15)$ | $0.15 + 0.15 = 0.3;\ 0.25 + 0.3 = 0.55;\ 0.45 + 0.55 = 1$ | $1.85$ | $1.840$ | $0.010$ |
| $(0.3, 0.25, 0.2, 0.15, 0.1)$ | $0.15 + 0.1 = 0.25;\ 0.2 + 0.25 = 0.45;\ 0.25 + 0.3 = 0.55;\ 0.45 + 0.55 = 1$ | $2.25$ | $2.228$ | $0.022$ |
Two patterns are worth noticing. The dyadic row $(0.5, 0.25, 0.125, 0.125)$ has gap $0$: the lengths match the surprises exactly. The row $(0.4, 0.2, 0.2, 0.2)$ has the largest gap, $0.078$: four nearly equal symbols force a fixed-length code of $2$ bits while the entropy is $1.922$. Ties in the merge order (two equal smallest weights) may give different trees, but the average length is always the same.
Common mistakes
$(0.3, 0.25, 0.2, 0.15, 0.1)$: merge $0.15 + 0.1 = 0.25$; list $0.3, 0.25, 0.25, 0.2$.
Smallest two first.
Merge $0.2 + 0.25 = 0.45$; list $0.45, 0.3, 0.25$. Merge $0.25 + 0.3 = 0.55$. Merge $0.45 + 0.55 = 1$.
Ties broken arbitrarily.
$L = 0.25 + 0.45 + 0.55 + 1 = 2.25$ bits; $H = 2.228$; lengths $2, 2, 2, 3, 3$.
Sum of merges.
$(\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \tfrac{1}{8})$: merges $\tfrac{1}{4}, \tfrac{1}{2}, 1$.
$L = 1.75 = H$; lengths $1, 2, 3, 3$ match the surprises exactly.
No loss for dyadic probabilities.
Merge $0.15 + 0.15 = 0.3$; list $0.45, 0.3, 0.25$.
Merge $0.25 + 0.3 = 0.55$; list $0.55, 0.45$.
Re-sorting matters: $0.3$ is now larger than $0.25$.
Merge $0.45 + 0.55 = 1$; $L = 0.3 + 0.55 + 1 = 1.85$ bits, against $H = 1.840$.
Lengths $1, 2, 3, 3$; the gap is only $0.010$ bits.
$(0.3, 0.25, 0.2, 0.15, 0.1)$: merge $0.15 + 0.1 = 0.25$; list $0.3, 0.25, 0.25, 0.2$.
Merge $0.2 + 0.25 = 0.45$; list $0.45, 0.3, 0.25$. Merge $0.25 + 0.3 = 0.55$.
With a tie at $0.25$, either choice gives the same $L$.
Merge $0.45 + 0.55 = 1$; $L = 0.25 + 0.45 + 0.55 + 1 = 2.25$ bits, against $H = 2.228$.
Merges: $0.1 + 0.1 = 0.2$; $0.2 + 0.2 = 0.4$; $0.4 + 0.6 = 1$.
$L = 0.2 + 0.4 + 1 = 1.6$ bits; lengths $1, 2, 3, 3$.
Run Huffman's algorithm on the probabilities $(0.35, 0.3, 0.2, 0.15)$. What is the average codeword length, in bits?
Answer:
A source has one symbol of probability $\tfrac{1}{2}$ and $16$ symbols of probability $2^{-5}$ each. What average length does Huffman's algorithm achieve, in bits?
Answer:
This program reads a count and then that many probabilities, and prints the average Huffman code length: it repeatedly merges the two smallest weights and adds up what it merged. ``` n = int(input()) p = [float(input()) for _ in range(n)] w = sorted(p) total = 0.0 while len(w) > 1: a = w.pop(0) b = w.pop(0) total += a + b w.append(a + b) w.sort() print(round(total, 4)) ``` What does it print when the input is `4`, then `0.5`, `0.25`, `0.125`, `0.125`?
[__output__]
Write each blank here: output:
Run Huffman's algorithm on the probabilities $(0.4, 0.3, 0.2, 0.1)$. What is the average codeword length, in bits?
Answer:
Probabilities $0.4, 0.3, 0.2, 0.1$. What does the first step of Huffman's algorithm do?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A source has one symbol of probability $\tfrac{1}{2}$ and $8$ symbols of probability $2^{-4}$ each. What average length does Huffman's algorithm achieve, in bits?
Answer:
You can build the best symbol code for any source and say how far it is from the entropy. Next: typical sequences, which explain why long blocks reach the entropy.
10. Your turn: Huffman for $(0.6, 0.2, 0.1, 0.1)$, step 2