Huffman Coding Algorithm

Huffman Coding Algorithm Lossless Compression

Overview: Huffman Coding is a greedy algorithm created by David Huffman in 1952 while working on his Ph.D. at MIT. It is an optimal prefix-free, variable-length statistical entropy encoding technique. The core principle dictates that symbols occurring more frequently in a source message receive shorter binary codes, while less frequent symbols receive longer binary codes.

Because it is prefix-free (no assigned binary codeword is a prefix of any other codeword), a bitstream can be decoded sequentially in a single pass without needing explicit boundaries or delimiters between symbols.

Algorithmic Complexity

Time Complexity

O(N log N) — Where N is the number of unique characters. Building the min-heap takes O(N), and extracting the minimum nodes N-1 times takes O(N log N).

Space Complexity

O(N) — Requires storage for the priority queue, leaf nodes, and internal tree structures representing the N unique symbols.

Core Algorithm Steps

1. Frequency Counting & Analysis:
   Scan the input stream to compute the frequency distribution of each distinct character or byte sequence.
2. Priority Queue Initialization:
   Create a leaf node for each symbol containing its character value and frequency count. Insert all leaf nodes into a Min-Heap (priority queue sorted by frequency).
3. Tree Construction (Greedy Approach):
   Iterate while the min-heap contains more than one node:
   • Pop the two lowest-frequency nodes (Node_1, Node_2).
   • Create a parent node with a combined frequency equal to Node_1.freq + Node_2.freq.
   • Set Node_1 as the left child and Node_2 as the right child.
   • Insert the new parent node back into the min-heap.
4. Bit Assignment & Dictionary Generation:
   Perform a Depth-First Search (DFS) starting from the root of the constructed Huffman Tree. Assign a bit value of 0 to every left branch and 1 to every right branch. The path from the root to any leaf node defines that symbol's unique binary code.

Detailed Worked Example

Launch Huffman Tree Generator

Input String: BCCABBDDAAEE (12 characters, 96 bits under standard 8-bit ASCII encoding)

Step 1: Calculate Frequency Table

• A: 3 occurrences (P = 3/12)
• B: 3 occurrences (P = 3/12)
• C: 2 occurrences (P = 2/12)
• D: 2 occurrences (P = 2/12)
• E: 2 occurrences (P = 2/12)

Step 2: Tree Synthesis Sequence

• Combine lowest nodes C (2) and D (2) → Internal Node [CD: 4]
• Combine lowest remaining E (2) and A (3) → Internal Node [EA: 5]
• Combine B (3) and [CD: 4] → Internal Node [BCD: 7]
• Combine [EA: 5] and [BCD: 7] → Root Node [12]

Step 3: Visual Huffman Tree Structure

[Root: 12] / \ (0) / \ (1) / \ [EA: 5] [BCD: 7] / \ / \ (0) / \ (1) (0)/ \ (1) / \ / \ E (2) A (3) B (3) [CD: 4] / \ (0) / \ (1) / \ C (2) D (2)

Step 4: Final Binary Encoding Dictionary

Symbol	Frequency	Huffman Code	Bit Length	Total Encoded Bits
E	2	00	2 bits	4 bits
A	3	01	2 bits	6 bits
B	3	10	2 bits	6 bits
C	2	110	3 bits	6 bits
D	2	111	3 bits	6 bits

Compression Ratio Achieved:

• Original Size (8-bit ASCII): 12 characters × 8 bits = 96 bits
• Compressed Huffman Size: 4 + 6 + 6 + 6 + 6 = 28 bits
• Space Reduction: (96 - 28) / 96 = 70.83% savings

Applications in Image Processing

In digital image processing, raw image data contains vast spatial redundancy. Huffman coding serves as the final, critical step in lossless and lossy compression formats (such as JPEG and PNG).

• Entropy Coding in the JPEG Pipeline:
  In JPEG compression, image blocks (8x8 pixels) are transformed using Discrete Cosine Transform (DCT) and then quantized. The resulting high-frequency coefficients contain long runs of zeroes. Huffman coding is executed on these final run-length pairs to store the image coefficients without further data loss.
• Handling Pixel Intensity Distribution:
  Images (like medical X-rays or astronomical photography) frequently exhibit dominant background shades. Instead of wasting 8 bits per grayscale pixel (0-255), Huffman coding assigns short 2 to 4-bit codes to dominant background pixel intensities, dramatically reducing raw image payload size.
• Integration with Run-Length Encoding (RLE):
  For lossy image routines, pixel coefficients are reordered in a Zig-Zag pattern to consolidate zero-value frequencies. RLE creates tuples of (run_length, value), which are subsequently mapped to optimized pre-defined or dynamic Huffman Tables.
• PNG Compression (DEFLATE Algorithm):
  PNG image formats use the DEFLATE compression engine. DEFLATE combines LZ77 (sliding window dictionary substitution) with dual dynamic Huffman trees—one tree for literal/length symbols and another for distance metrics—producing high compression ratios for graphics.

Key Takeaway: Huffman Coding achieves maximum efficiency when symbol probabilities are inverse powers of two (2^-1, 2^-2, 2^-3). For datasets with skewed distributions—like quantized image coefficients—it approaches Shannon's theoretical Entropy limit.

Notes Created By Bijan Krishna Paul Computer Science & Engineering