Huffman Tree Explained with Examples and Implementation

Huffman Tree Explained with Examples and Implementation

What is a Huffman Tree?

A Huffman Tree is a binary tree used to create an optimal prefix code for a set of symbols with known frequencies. It minimizes the total weighted path length (average code length) so frequently occurring symbols get shorter codes and rare symbols get longer codes.

Key properties

• Prefix-free: No code is a prefix of another, so codes are uniquely decodable.
• Optimality: For a given set of symbol frequencies, Huffman coding yields the minimum average code length among all prefix codes.
• Binary tree: Leaves represent symbols; path from root to leaf gives the symbol’s binary code (left=0, right=1).

Algorithm (high-level)

1. Create a leaf node for each symbol and add it to a priority queue ordered by frequency.
2. While there is more than one node in the queue:
   • Remove the two nodes with the smallest frequencies.
   • Create a new internal node with these two nodes as children and frequency equal to their sum.
   • Insert the new node back into the queue.
3. The remaining node is the root of the Huffman Tree.
4. Traverse the tree to assign codes: left edge = 0, right edge = 1.

Worked example

Symbols with frequencies:

• A: 45
• B: 13
• C: 12
• D: 16
• E: 9
• F: 5

Step-by-step:

1. Initial queue (freq): F(5), E(9), C(12), B(13), D(16), A(45)
2. Merge F(5)+E(9)=14 → new node FE(14). Queue: C(12), B(13), FE(14), D(16), A(45)
3. Merge C(12)+B(13)=25 → CB(25). Queue: FE(14), D(16), CB(25), A(45)
4. Merge FE(14)+D(16)=30 → FED(30). Queue: CB(25), FED(30), A(45)
5. Merge CB(25)+FED(30)=55 → CBFED(55). Queue: A(45), CBFED(55)
6. Merge A(45)+CBFED(55)=100 → root(100)

Assigning codes by traversing (left=0, right=1) yields a possible set:

• A: 0
• B: 101
• C: 100
• D: 111
• E: 1101
• F: 1100

Average code length = (451 + 133 + 123 + 163 + 94 + 54) / 100 = (45 + 39 + 36 + 48 + 36 + 20)/100 = ⁄₁₀₀ = 2.24 bits/symbol.

Implementation (Python)

python
Copy CodeCopied
import heapq from collections import defaultdict, namedtuple 
Node = namedtuple(“Node”, [“freq”, “symbol”, “left”, “right”])
# For heapq, nodes compare by freq only
class HuffmanNode:
def init(self, freq, symbol=None, left=None, right=None):
        self.freq = freq         self.symbol = symbol         self.left = left         self.right = right     def lt(self, other):
        return self.freq < other.freq 
def build_huffman_tree(freq_map):
    heap = [HuffmanNode(freq, sym) for sym, freq in freq_map.items()]
    heapq.heapify(heap)
    if len(heap) == 1:
        # Edge case: only one symbol
        node = heapq.heappop(heap)
        return HuffmanNode(node.freq, None, left=node)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = HuffmanNode(a.freq + b.freq, None, left=a, right=b)
        heapq.heappush(heap, merged)
    return heap[0]

def generate_codes(node, prefix=””, code_map=None):
    if code_map is None:
        code_map = {}
    if node is None:
        return code_map     if node.symbol is not None:
        code_map[node.symbol] = prefix or “0”  # handle single-symbol case
    else:
        generate_codes(node.left, prefix + “0”, code_map)
        generate_codes(node.right, prefix + “1”, code_map)
    return code_map 
# Example usage:
freq_map = {‘A’:45, ‘B’:13, ‘C’:12, ’D’:16, ‘E’:9, ‘F’:5}
root = build_huffman_tree(freq_map)
codes = generate_codes(root)
print(“Huffman Codes:”, codes)

Encoding and decoding

• Encoding: Replace each symbol with its code and concatenate bits.
• Decoding: Traverse the tree from root for each bit; when reaching a leaf, output the symbol and return to root.

Complexity

• Building tree: O(n log n) using a priority queue (n = number of symbols).
• Generating codes: O(n).
• Encoding/decoding per symbol: O(code length) which averages to the entropy-bound optimal length.

Practical notes

• Huffman coding is optimal among prefix codes but not always globally optimal for all compression schemes (context modeling or arithmetic coding can do better).
• For small alphabets or skewed frequencies, consider canonical Huffman codes for simpler storage of the codebook.

References and further reading

• Huffman, D. A. (1952). A Method for the Construction of Minimum-Redundancy Codes.
• Textbook chapters on data compression (e.g., Salomon, Sayood).