Build the Code

Counts Choose the Names

Huffman coding starts with exact symbol counts.

highlighted = computed this step

Start with counts

Huffman coding starts with symbol counts. More common symbols should get shorter names.

counts first\text{counts first}
Counts choose the namesHuffman rows recomputed from pinned counts and message.Counts choose the names - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

The counts are pinned

Here A appears 5 times, B appears 2 times, and C and D each appear 1 time.

A:5,B:2,C:1,D:1A:5,B:2,C:1,D:1
Counts choose the namesHuffman rows recomputed from pinned counts and message.Counts choose the names - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

A should be short

A has the largest count, so the final code should not spend many bits on A.

larger count means shorter code\text{larger count means shorter code}
Counts choose the namesHuffman rows recomputed from pinned counts and message.Counts choose the names - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

Summary

The table is not a hand-written answer. It recomputes the code from these counts and the deterministic tie rule.

deterministic recompute\text{deterministic recompute}
Counts choose the namesHuffman rows recomputed from pinned counts and message.Counts choose the names - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes