Huffman coding: from a heap trace to canonical bits

The objective is to minimize sum(freq[s]*length[s]) among binary prefix codes. Huffman repeatedly combines the two least-weight subtrees. The tree can be rebuilt from frequencies only if tie rules agree; canonical codes can instead be rebuilt from lengths.

Execute the merge process

Use symbol IDs A=0, B=1, C=2, D=3 and frequencies 5,2,1,1. Order heap entries by (weight,minimum symbol ID in subtree). The first popped node becomes the left child.

Step	Two popped nodes	Inserted node	Remaining ordered heap
1	C:1, D:1	CD:2, min=2	B:2, CD:2, A:5
2	B:2, CD:2	BCD:4, min=1	BCD:4, A:5
3	BCD:4, A:5	root:9	root

With left=0, right=1, the tree codes are A=1, B=00, C=010, D=011; lengths are [1,2,3,3]. Cost is 5+4+3+3=15 bits for nine symbols. Each merge adds one bit to every leaf below it, so the same total is the sum of merge weights 2+4+9=15. This provides an independent accounting check.

Why the greedy step works: in an optimal full tree, two deepest leaves can be siblings. Assigning the two smallest weights to those positions cannot increase weighted depth. Contract them into one leaf whose weight is their sum; the remaining problem has the same form. A deterministic tie rule chooses among potentially equally good trees; it is not the proof of optimality.

Canonical codes preserve lengths, not tree paths

Sort used symbols by (length,symbol ID). Start code=0 at the first length. After assigning each code, increment; before a longer next code, shift left by the difference in lengths.

Symbol	Length	Calculation	Canonical bits
A	1	first code 0	0
B	2	(0+1)<<1	10
C	3	(2+1)<<1	110
D	3	6+1	111

The original tree and canonical table have equal weighted cost. Their encoded bytes differ. Do not use a tree-code encoder with a canonical decoder unless the header actually communicates that change.

Codes live in the low Len bits of Bits; writing code 110 means WriteBits(6,3), not writing the complete 32-bit integer. Unused symbols have length zero and emit nothing. A singleton is assigned length one, bits zero. An empty frequency table has no codes; an enclosing format must define how empty messages are framed.

Validate a table before decoding it

Given lengths, count how many words occur at each depth. Start with one available root slot. At each depth:

slots = 2*slots - count[depth]
if slots < 0: reject

For [1,2,3,3], slots are 1,1,0. For [1,1,2], they become 0,-1: impossible. A positive remainder is an incomplete tree, which this pack permits. During tree decoding, following a missing branch is invalid input, not an implicit zero or EOF.

The canonical exercise assumes valid lengths no greater than 32 because its codes are uint32. The capstone receives external headers and must perform that validation itself. Real DEFLATE imposes a different 15-bit limit and uses a more compact header; this pack's limits and serialization are its own contract. See RFC 1951 section 3.2.2 for the canonical construction used by that format.

Implementation and reconstruction

Heap construction costs O(A log A) for A used symbols; tree traversal costs O(A). Canonical sorting costs O(A log A). Header size is additional to payload; sending lengths is simpler than sending pointers, but does not guarantee a small file.

1. With lengths [2,0,2,3], assign the three used codes.
2. Why can a correct weighted cost still produce the wrong expected bytes?
3. Does a singleton have entropy one bit per symbol?

Model answers

1. Symbol 0=00, 2=01, 3=100. The unused symbol does not increment the code.
2. Tied merges or tree-versus-canonical conventions can change bit patterns while preserving lengths and cost.
3. No: it has entropy zero. A one-bit code is this pack's explicit representation convention.

Implement Huffman Build, then Canonical Huffman.