Past exam question: 2078 Bhadra, Q8
Open in the Padhaiko appEncode "Jasta lai tastai dhido lai nistai" using weighted Huffman encoder. Also demonstrate how it is decoded.
Solution
Frequency Analysis of the Input Message: Given string: "Jasta lai tastai dhido lai nistai" (case-sensitive, including spaces). Total length: characters across 11 unique symbols:
'a': 7 ()'i': 6 ()' '(space): 5 ()'t': 4 ()'s': 3 ()'d': 2 ()'l': 2 ()'J': 1 ()'h': 1 ()'n': 1 ()'o': 1 ()
Check total: .
Huffman Tree Construction and Codeword Table: Iteratively merging the two lowest-weight nodes (0 to left child, 1 to right child):
| Symbol | Weight | Codeword | Length | |
|---|---|---|---|---|
'a' | 7 | 00 | 2 | 14 |
'i' | 6 | 111 | 3 | 18 |
' ' | 5 | 110 | 3 | 15 |
't' | 4 | 011 | 3 | 12 |
's' | 3 | 010 | 3 | 9 |
'd' | 2 | 1000 | 4 | 8 |
'l' | 2 | 1001 | 4 | 8 |
'J' | 1 | 10100 | 5 | 5 |
'h' | 1 | 10101 | 5 | 5 |
'n' | 1 | 10110 | 5 | 5 |
'o' | 1 | 10111 | 5 | 5 |
| Total | 33 | — | — | 104 |
Average codeword length , entropy , efficiency .
Encoding the Message: Substituting each character with its prefix codeword:
"Jasta":10100(J) +00(a) +010(s) +011(t) +00(a) =101000001001100" ":110"lai":1001(l) +00(a) +111(i) =100100111" ":110"tastai":011(t) +00(a) +010(s) +011(t) +00(a) +111(i) =0110001001100111" ":110"dhido":1000(d) +10101(h) +111(i) +1000(d) +10111(o) =100010101111100010111" ":110"lai":100100111" ":110"nistai":10110(n) +111(i) +010(s) +011(t) +00(a) +111(i) =1011011101001100111
Complete encoded bitstream (104 bits): 10100000100110011010010011111001100010011001111101000101011111000101111101001001111101011011101001100111
Demonstration of Decoding Procedure: The decoder starts at the root of the shared Huffman tree and reads incoming bits left-to-right (0 = left, 1 = right) until reaching a leaf:
10100: reaches leaf'J'. Emit'J', reset to root.00: reaches leaf'a'. Emit'a', reset to root.010: reaches leaf's'. Emit's', reset to root.011: reaches leaf't'. Emit't', reset to root.00: reaches leaf'a'. Emit'a', reset to root.110: reaches leaf' '. Emit' ', reset to root.
Continuing through all 104 bits uniquely reconstructs "Jasta lai tastai dhido lai nistai" with zero ambiguity because the code is prefix-free.
For "Jasta lai tastai dhido lai nistai" ( characters, 11 unique symbols), the weighted Huffman codewords are: 'a': 00, 'i': 111, ' ': 110, 't': 011, 's': 010, 'd': 1000, 'l': 1001, 'J': 10100, 'h': 10101, 'n': 10110, 'o': 10111. The full message encodes into (, efficiency ), and is uniquely decoded left-to-right by traversing the Huffman tree from root to leaf.