Huffman encoding compresses text by building a binary tree from character frequencies, assigning shorter bit sequences to more frequent characters. section 2.8.3
Build the coding tree incrementally:
- Count each character’s occurrences and insert one frequency-weighted tree node per character into a min-heap. section 2.8.3
- Repeatedly remove the two smallest-frequency nodes, merge them under a new parent, and reinsert the parent. section 2.8.3
- Traverse left edges as 0 and right edges as 1 to map each character to its binary sequence. section 2.8.3
Unequal code lengths
For frequencies A=0.6, B=0.2, C=0.07, D=0.06, E=0.05, and F=0.02, the resulting table assigns A to 0, B to 10, and the least frequent symbols to four-bit codes. section 2.8.3
Listing 2.12 The Huffman coding algorithm
function huffman(text)
charFrequenciesMap ← ComputeFrequencies(text)
priorityQueue ← MinHeap()
for (char, frequency) in charFrequenciesMap do
priorityQueue.insert(TreeNode([char], frequency))
while priorityQueue.size > 1 do
left ← priorityQueue.top()
right ← priorityQueue.top()
parent ← TreeNode(left.chars + right.chars,
left.frequency + right.frequency)
parent.left ← left
parent.right ← right
priorityQueue.insert(parent)
return buildTable(priorityQueue.top(), [], Map())
Use the pseudocode to follow frequency computation, heap initialization, repeated node merging, and table construction. section 2.8.3
