Past exam question: 2072 Kartik, Q10(ii)
Open in the Padhaiko appQuestion
Write short notes on: (ii) Huffman loading
Solution
Huffman Coding: Huffman coding is an optimal, lossless statistical data compression and source-coding algorithm developed by David Huffman in 1952.
- Fundamental Principle: Frequently occurring message symbols are assigned shorter binary codewords, while rarer symbols receive longer codewords.
- Prefix Property: Huffman codes generate prefix codes (instantaneous codes), meaning no codeword is a prefix of any other valid codeword. This ensures unique and instantaneous decodability from left to right without requiring delimiters.
- Tree Construction Algorithm:
- List all source symbols in descending order of their occurrence probabilities.
- Select the two symbols with the lowest probabilities and combine them into a parent node whose probability is their sum.
- Replace the two symbols with the parent node and re-order the list.
- Repeat steps 2 and 3 until a single root node with probability 1.0 remains.
- Assign binary labels (
0and1) to the two branches emanating from each parent node. The path from the root to a leaf node yields the codeword for that symbol.
- Optimality: Huffman coding produces the minimum average codeword length among all uniquely decodable symbol-by-symbol codes, approaching Shannon's source entropy limit:
Answer:
Huffman coding is an optimal lossless variable-length prefix coding algorithm that assigns shorter binary codewords to high-probability symbols and longer codewords to low-probability symbols by iteratively merging the two lowest-probability nodes.