Past exam question: 2078 Kartik, Q7
Open in the Padhaiko appWrite down the Huffman Algorithm clearly and find an efficient code word and efficiency that can be assign to the symbols using Huffman Algorithm for "Kun Mandir Ma Janchhau Yattri".
Solution
The Huffman Source Coding Algorithm: Huffman coding is an optimal prefix-free variable-length source coding algorithm:
- Frequency Analysis: Determine the frequency or probability of each distinct symbol in the source alphabet.
- Initialization: Create a leaf node for each symbol and arrange the nodes in order of probability.
- Iterative Reduction:
- Select the two nodes with the smallest probabilities.
- Merge them into a new internal parent node whose probability equals the sum of its two children's probabilities.
- Re-insert the parent node into the active priority list.
- Binary Labeling: Repeat until a single root node of probability remains. Assign
0to one branch and1to the other branch at every fork. - Codeword Extraction: Trace the path from the root to each leaf node to read off its unique prefix-free codeword.
Exact Character Frequency Count: Given string: "Kun Mandir Ma Janchhau Yattri" (case-sensitive, including spaces). Total length: characters across 14 unique symbols:
'a': 5 ()' '(space): 4 ()'n': 3 ()'M': 2 ()'h': 2 ()'i': 2 ()'r': 2 ()'t': 2 ()'u': 2 ()'J': 1 ()'K': 1 ()'Y': 1 ()'c': 1 ()'d': 1 ()
Check total: .
Huffman Tree Construction and Codeword Table: Repeatedly merging the two lowest-frequency nodes (0 to left child, 1 to right child):
| Symbol | Frequency | Probability | Codeword | Length | |
|---|---|---|---|---|---|
'a' | 5 | 111 | 3 | 15 | |
' ' | 4 | 011 | 3 | 12 | |
'n' | 3 | 001 | 3 | 9 | |
'M' | 2 | 0101 | 4 | 8 | |
'h' | 2 | 1000 | 4 | 8 | |
'i' | 2 | 1001 | 4 | 8 | |
'r' | 2 | 1010 | 4 | 8 | |
't' | 2 | 1011 | 4 | 8 | |
'u' | 2 | 1100 | 4 | 8 | |
'Y' | 1 | 0000 | 4 | 4 | |
'c' | 1 | 0001 | 4 | 4 | |
'd' | 1 | 0100 | 4 | 4 | |
'J' | 1 | 11010 | 5 | 5 | |
'K' | 1 | 11011 | 5 | 5 | |
| Total | 29 | 1 | — | — | 106 |
Average Codeword Length, Entropy, and Efficiency:
- Average Codeword Length ():
- Source Entropy ():
- Coding Efficiency ():
The Huffman algorithm iteratively merges the two lowest-probability nodes into a binary tree until a single root remains, yielding prefix-free minimum-redundancy codewords. For "Kun Mandir Ma Janchhau Yattri" ( characters, 14 distinct symbols):
- Total encoded bits (e.g.,
'a':111,' ':011,'n':001, ...,'J':11010,'K':11011). - Average codeword length: .
- Source entropy: .
- Coding efficiency: .