Merge the two least probable nodes until one tree remains; the tree gives short codewords to probable symbols.
Question: How do you build the shortest code?
Re-simulated Re-simulated: data/scripts/c16.s04.L1.py rebuilds the Huffman tree and reproduces the section's 2.300-bit average length and 2.2855-bit entropy. The four source distributions are chosen teaching values, not measurements. The frames trace the four merges for one source at a time and end on the finished tree, the codeword table and the three bars.
Frame 1 of 5: Step 0 of 4Start with five leaves. The two least probable are d (0.15) and e (0.15).
Step 0 of 4. Start with five leaves. The two least probable are d (0.15) and e (0.15).
Keyboard: Space plays or pauses, Left and Right step, Home goes to the first frame, End goes to the last frame.
Text description of this lab
A tree grows from five symbol leaves, a to e, labelled with their probabilities. At each step the two least probable nodes are ringed in gold and joined by a dashed line, and a parent carrying their summed probability appears above them; four merges leave one root. Reading 0 on a left branch and 1 on a right gives the prefix code: probable symbols short codewords, rare ones long. Bars compare average length with entropy and a fixed three-bit code.