Four equally likely symbols — Huffman coding
corewhen compression achieves nothing
Answer
average 2.0000 bits/symbol, 8 bits total
3 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
A uniform distribution over four symbols gives every symbol a two-bit code, exactly what a fixed-length encoding would give. Huffman exploits imbalance, and there is none, so there is nothing to gain. The page makes the point that a compression ratio of one is a correct result rather than a failure, and links to the entropy tool where the same conclusion arrives as a number.
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 | 1 | 2 |
| 2 | 1 | 1 | 2 |
| 3 | 2 | 2 | 4 |