concept · INFO-CS-ADS-187Huffman Coding
Learn how Huffman Coding creates an efficient variable-length prefix code by repeatedly combining the two symbols with the lowest frequencies.
Explanation
Overview
Huffman Coding is a lossless data compression algorithm that assigns variable-length binary codes to symbols according to their frequencies. Frequently occurring symbols receive shorter codes, while less frequent symbols receive longer codes. Its prefix-free property ensures that encoded symbols can be decoded without ambiguity.
Key concepts
Prefix-free codes; Variable-length encoding; Minimum-priority queue; Binary tree construction; Frequency-based compression; Greedy choice
Variables
symbol: A character or data symbol to encode.; frequency: The number of times a symbol occurs.; node: A leaf or internal node in the Huffman tree.; left: The left child of an internal node, commonly assigned bit 0.; right: The right child of an internal node, commonly assigned bit 1.; code: The binary path from the root to a symbol's leaf.
Complexity
treeConstruction: O(n log n) time using a binary minimum-heap.; codeGeneration: O(n) time for a tree containing n leaves.; overall: O(n log n) time and O(n) space for the tree and priority queue.
Example
frequencies: symbol: A; frequency: 5; symbol: B; frequency: 9; oneValidCodeAssignment: F: 0; C: 100; explanation: The two least frequent nodes are combined repeatedly to construct a binary tree. Each symbol receives a code based on its path from the root. Different left-right assignments may produce different but equally optimal codes.
Pseudocode
function huffmanCoding(symbols):
priorityQueue = minHeap of leaf nodes
while priorityQueue.size > 1:
left = priorityQueue.extractMin()
right = priorityQueue.extractMin()
parent = new Node(left.frequency + right.frequency)
parent.left = left
parent.right = right
priorityQueue.insert(parent)
root = priorityQueue.extractMin()
generateCodes(root, "")
Applications
File compression.; ZIP and related compression techniques.; Image and multimedia compression systems.; Data transmission.; Lossless encoding.
Variables
Symbol
A character or data symbol to encode.
Frequency
The number of times a symbol occurs.
Node
A leaf or internal node in the Huffman tree.
Left
The left child of an internal node, commonly assigned bit 0.
Right
The right child of an internal node, commonly assigned bit 1.
Code
The binary path from the root to a symbol's leaf.
Example or application
Frequencies
| Symbol | Frequency |
|---|
A | 5 |
B | 9 |
C | 12 |
D | 13 |
E | 16 |
F | 45 |
One Valid Code Assignment
Explanation
The two least frequent nodes are combined repeatedly to construct a binary tree. Each symbol receives a code based on its path from the root. Different left-right assignments may produce different but equally optimal codes.
Definition
Huffman Coding is a lossless data compression algorithm that assigns variable-length binary codes to symbols according to their frequencies. Frequently occurring symbols receive shorter codes, while less frequent symbols receive longer codes. Its prefix-free property ensures that encoded symbols can be decoded without ambiguity.
Mathematical Representation
At each construction step, combine the two nodes with the smallest frequencies into a new node whose frequency is their sum. Repeat until one Huffman tree remains.
Greedy Strategy
Create one leaf node for every symbol using its frequency.
Insert all nodes into a minimum-priority queue.
Remove the two nodes with the smallest frequencies.
Create a new internal node with their combined frequency.
Make the removed nodes its children.
Insert the new node into the priority queue.
Repeat until only one node remains.
Generate each symbol's binary code by traversing the resulting tree.
Pseudocode
function huffmanCoding(symbols):
priorityQueue = minHeap of leaf nodes
while priorityQueue.size > 1:
left = priorityQueue.extractMin()
right = priorityQueue.extractMin()
parent = new Node(left.frequency + right.frequency)
parent.left = left
parent.right = right
priorityQueue.insert(parent)
root = priorityQueue.extractMin()
generateCodes(root, "")
Complexity
Tree Construction
O(n log n) time using a binary minimum-heap.
Code Generation
O(n) time for a tree containing n leaves.
Overall
O(n log n) time and O(n) space for the tree and priority queue.
Advantages
Produces an optimal prefix code for the given symbol frequencies.
Frequently occurring symbols receive shorter representations.
Supports lossless compression.
Can reduce the average number of bits required per symbol.
Has an efficient implementation using a minimum-heap.
Limitations
The decoder needs access to the code tree or an equivalent code table.
The frequency information and tree metadata introduce storage overhead.
Compression effectiveness depends on the distribution of symbol frequencies.
Huffman coding does not always achieve the best possible compression across every compression method.
Very small files may not benefit because metadata can outweigh the compressed data.
Related Topics
Greedy Algorithms
Binary Trees
Priority Queues
Data Compression
Prefix Codes
Practice Question
Why does Huffman Coding assign shorter codes to more frequent symbols?
Practice Answer
Shorter codes for frequent symbols reduce the total weighted number of bits needed to represent the data.
Learning Objectives
Explain the central idea and purpose of huffman coding.
Identify the assumptions, inputs, and conditions relevant to huffman coding.
Evaluate an application of huffman coding for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Greedy Algorithms and Optimization
Suggest a correction or source · More in Algorithms & Data Structures