Past exam question: 2074 Chaitra, Q9(a)
Open in the Padhaiko appQuestion
Write down the Huffman Algorithm clearly.
Solution
Step-by-Step Specification of the Huffman Algorithm: The Huffman algorithm constructs an optimal prefix-free variable-length binary code for a discrete memoryless source:
- Source Probability Ordering: List all unique source symbols and their corresponding probabilities in strictly descending order ().
- Initial Node Creation: Treat each symbol as an individual leaf node of a binary tree, labeled with its probability.
- Iterative Binary Tree Reduction:
- Identify the two available nodes with the lowest probabilities (say and ).
- Create a new parent node with combined probability .
- Connect the two children nodes to this parent.
- Remove the two children from the active candidate list and insert the parent node, maintaining descending probability order.
- Termination: Repeat this reduction until exactly one root node with aggregate probability remains.
- Codeword Extraction: Label every left branch with binary digit
0and every right branch with binary digit1(or vice versa). Trace the unique path from root to each terminal leaf node to obtain its prefix codeword.
Answer:
The Huffman Algorithm operates by:
- Sorting symbol probabilities in descending order.
- Successively merging the two lowest-probability nodes into a parent node whose probability equals their sum.
- Repeating until a single root node of probability is formed.
- Assigning binary
0and1to opposing tree branches, extracting prefix codewords by tracing from root to each leaf.