Huffman Coding

03 Huffman Algorithm

Algorithm Steps

1. Frequency Analysis: Calculate occurrence probability (or frequency) for each symbol in the source data.
2. Initialize Priority Queue: Create a leaf node for each symbol and add it to a min-heap/priority queue ordered by frequency.
3. Tree Construction: While more than one node in the queue:
   • Remove the two nodes with lowest frequencies
   • Create new internal node with frequency = sum of two nodes
   • Make the two nodes left and right children (0=left, 1=right)
   • Insert new node into queue
4. Code Assignment: The remaining node is the root. Traverse from root to leaves, appending 0 for left branches and 1 for right branches.
5. Encoding: Replace each source symbol with its corresponding Huffman code.

Pseudocode

function HuffmanCoding(S):
    // S: set of symbols with frequencies
    n ← |S|
    Q ← priority queue ordered by frequency
    
    for each symbol s in S:
        insert Node(s.freq) into Q
    
    for i ← 1 to n-1:
        z ← new Node()
        z.left ← x ← Extract-Min(Q)
        z.right ← y ← Extract-Min(Q)
        z.freq ← x.freq + y.freq
        Insert(Q, z)
    
    return Extract-Min(Q)  // Root of Huffman tree

function AssignCodes(node, code):
    if node is leaf:
        node.code ← code
    else:
        AssignCodes(node.left, code + "0")
        AssignCodes(node.right, code + "1")

Complexity Analysis

04 Worked Example

Problem Statement

Given a source with symbols {A, B, C, D, E, F} and probabilities:

Step-by-Step Construction

Step 1: Initial Priority Queue

Queue: [F(0.05), E(0.09), C(0.12), B(0.13), D(0.16), A(0.45)]
Sorted by increasing frequency

Step 2: Iteration 1 - Combine F and E

Remove: F(0.05), E(0.09)
Create: Node(0.14) with children F(0), E(1)
New Queue: [C(0.12), B(0.13), Node(0.14), D(0.16), A(0.45)]

Step 3: Iteration 2 - Combine C and B

Remove: C(0.12), B(0.13)
Create: Node(0.25) with children C(0), B(1)
New Queue: [Node(0.14), D(0.16), Node(0.25), A(0.45)]

Step 4: Iteration 3 - Combine Node(0.14) and D

Remove: Node(0.14), D(0.16)
Create: Node(0.30) with children Node(0.14)(0), D(1)
New Queue: [Node(0.25), Node(0.30), A(0.45)]

Step 5: Iteration 4 - Combine Node(0.25) and Node(0.30)

Remove: Node(0.25), Node(0.30)
Create: Node(0.55) with children Node(0.25)(0), Node(0.30)(1)
New Queue: [A(0.45), Node(0.55)]

Step 6: Final Combination

Remove: A(0.45), Node(0.55)
Create: Root(1.00) with children A(0), Node(0.55)(1)
Final Tree Complete!

Final Huffman Tree Visualization

Final Code Table

Encoding Example

Encoding the string "BAD":

B → 101
A → 0
D → 111

BAD → 101 0 111 = 1010111 (7 bits)

Fixed-length (3 bits each): 011 000 011 = 011000011 (9 bits)
Savings: 22.2%

05 Applications in Communication

Variants and Extensions

Comparison with Other Codes

06 Interactive Huffman Calculator

Practice Problems

Step 1: Combine Z(0.1) and Y(0.3) → Node(0.4)
Step 2: Combine Node(0.4) and X(0.6) → Root(1.0)

Codes:
X: 1 (length 1)
Y: 01 (length 2)
Z: 00 (length 2)

Average Length = 0.6×1 + 0.3×2 + 0.1×2 = 1.4 bits/symbol
Entropy = 1.295 bits/symbol
Efficiency = 92.5%

For 8 equiprobable symbols: p = 1/8 = 0.125 each

Huffman will create a balanced tree:
All codes have length 3 (since 2^3 = 8)

Fixed-length: 3 bits/symbol (⌈log₂8⌉ = 3)
Huffman: 3 bits/symbol

Efficiency = 100% (no improvement for uniform distribution)

Entropy H(X) = -8 × (1/8) × log₂(1/8) = 3 bits/symbol
This demonstrates Huffman coding works best with skewed distributions.

Probabilities: D:0.70, C:0.20, A:0.08, E:0.02

Construction:
1. Combine E(0.02) + A(0.08) = Node(0.10)
2. Combine Node(0.10) + C(0.20) = Node(0.30)
3. Combine Node(0.30) + D(0.70) = Root(1.00)

Codes:
D: 1 (1 bit)
C: 01 (2 bits)
A: 001 (3 bits)
E: 000 (3 bits)

Average length = 0.7×1 + 0.2×2 + 0.08×3 + 0.02×3 = 1.4 bits/packet
Fixed-length would require 2 bits/packet (⌈log₂4⌉ = 2)

Bandwidth savings: (2 - 1.4)/2 × 100% = 30%
Effective capacity: 1000/1.4 = ~714 packets/sec vs 500 packets/sec fixed

07 Summary & Key Takeaways