Back to Compression
Huffman Coding
Optimal prefix-free variable-length coding algorithm
Algorithm Type
Greedy, optimal prefix coding
Time Complexity
O(n log n) - tree construction
Applications
JPEG, MP3, ZIP compression
Input Text
Huffman Tree Visualization
Enter text and click "Build Huffman Tree" to see the visualization
Huffman Coding Algorithm
How It Works
- 1. Count Frequencies: Calculate frequency of each character
- 2. Create Leaf Nodes: Make a leaf node for each character
- 3. Build Priority Queue: Add all nodes to priority queue (min-heap)
- 4. Build Tree: Repeatedly merge two nodes with lowest frequencies
- 5. Assign Codes: Traverse tree to assign binary codes (0=left, 1=right)
- 6. Encode Text: Replace each character with its binary code
Advantages
- • Optimal prefix-free coding
- • No ambiguity in decoding
- • Greedy algorithm gives optimal result
- • Efficient for text compression
- • Widely used in practice
Applications
- • JPEG image compression
- • MP3 audio compression
- • ZIP file compression
- • Data transmission protocols
- • Fax machine encoding