Prefix-free property check — Huffman coding
exam standardwhat makes the code decodable
Answer
b=00 d=010 c=011 a=1
2 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
Because every symbol sits at a leaf, no codeword is a prefix of any other, and a decoder can therefore read the stream bit by bit and emit a symbol the moment it reaches a leaf — with no delimiters and no lookahead. The page walks a short encoded stream through that process, since the prefix property is usually stated as a definition and rarely demonstrated as the mechanism it is.
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 | 2 | 2 | 4 |
| 3 | 4 | 5 | 9 |