Huffman Coding

Knowledge Summary

Huffman Tree (Optimal Binary Tree)

A binary tree with the minimum weighted path length (WPL).

$WPL = \sum_{i=1}^{n} w_i \times l_i$

where $w_i$ is the weight of a leaf node and $l_i$ is the path length from that leaf to the root.

Constructing a Huffman Tree

1. Put all nodes into a priority queue (min-heap)
2. Remove the two nodes with the smallest weights each time
3. Create a new node with weight equal to the sum of the two child weights
4. Put the new node back into the priority queue
5. Repeat steps 2-4 until only one node remains

Huffman Coding

A prefix code based on the Huffman tree:

• Encode the left branch as 0 and the right branch as 1
• Characters with higher frequency get shorter codes, and those with lower frequency get longer codes
• The code of any character is never a prefix of another character's code

Example

Character frequencies: A=5, B=9, C=12, D=13, E=16, F=45

Construction process:

1. Merge A(5) + B(9) = 14
2. Merge C(12) + D(13) = 25
3. Merge 14 + E(16) = 30
4. Merge 25 + 30 = 55
5. Merge F(45) + 55 = 100

Frequently Tested Points

• Given frequencies, compute the minimum WPL
• Construct a Huffman tree and write the codes
• Determine whether a code system is a prefix code