Build the Code

Merge the Two Smallest

The first merge combines the two lowest counts.

highlighted = computed this step

Pick the smallest two

Each merge takes the two lowest-count items. Ties use lower lexical symbol or key first.

smallest two, lexical tie\text{smallest two, lexical tie}
Merge the two smallestHuffman rows recomputed from pinned counts and message.Merge the two smallest - 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

C and D tie

C has count 1 and D has count 1. They are the two smallest items.

1+11+1
Merge the two smallestHuffman rows recomputed from pinned counts and message.Merge the two smallest - 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

Make CD

Merging C and D makes CD with count 2.

C+D=CD,∣CD∣=2C+D=CD,\quad |CD|=2
Merge the two smallestHuffman rows recomputed from pinned counts and message.Merge the two smallest - 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 first merge is C with D, forming CD. The table keeps that merge as a recomputed row.

C+D=CDC+D=CD
Merge the two smallestHuffman rows recomputed from pinned counts and message.Merge the two smallest - 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