Huffman versus entropy for "mississippi" — Huffman coding
edge casethe cost of whole bits
Answer
i=0 m=100 p=101 s=11
1 merge tie(s) were broken by rule, so other trees of exactly the same cost exist. Moffat (2019) §2.2: symbols are numbered 0…m−1 in ascending code-point order, and the heap is keyed on the tuple (weight, isInternal ? 1 : 0, tieRank) with tieRank = −symbolIndex for leaves and the creation sequence number for internal nodes. So: on a tie between leaves the higher-numbered symbol is preferred; on a tie between a leaf and an internal node the leaf is preferred; on a tie between internal nodes the one formed earlier is preferred. The first node popped becomes the 0 (left) child.
Why this example is worth doing
The Huffman average sits just above the entropy, and the gap is the rounding loss from assigning whole numbers of bits to symbols whose ideal lengths are fractional. The page puts the two numbers side by side and names the theorem that bounds the gap below one bit per symbol. It is the most direct link between the coding tools and the Shannon material, and both pages carry it.
Try your own input in the Huffman coding. Build the tree from text or from frequencies, with the merge order and canonical codes.
How the answer is reached
Tie-break
Moffat (2019) §2.2: symbols are numbered 0…m−1 in ascending code-point order, and the heap is keyed on the tuple (weight, isInternal ? 1 : 0, tieRank) with tieRank = −symbolIndex for leaves and the creation sequence number for internal nodes. So: on a tie between leaves the higher-numbered symbol is preferred; on a tie between a leaf and an internal node the leaf is preferred; on a tie between internal nodes the one formed earlier is preferred. The first node popped becomes the 0 (left) child.
Merge order
| step | left | right | weight |
|---|---|---|---|
| 1 | 1 | 2 | 3 |
| 2 | 3 | 4 | 7 |
| 3 | 4 | 7 | 11 |