Text "mississippi" — Huffman coding
introfrequencies derived from the text
Answer
average 1.9091 bits/symbol, 21 bits total
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
Entering text rather than a frequency table, with the counts derived automatically: i and s appear four times each, p twice, m once. The page shows the count step separately from the tree step because students often mis-tally, and a wrong frequency table produces a plausible-looking but wrong tree. Eleven characters compress from eighty-eight bits to twenty-one.
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 |