Past exam question: 2079 Baishakh (Back), Q8
Open in the Padhaiko appCalculate coding efficiency of "Khoji Rahechha Desh Le Yek Yug Nayak" using Huffman coding technique.
Solution
Character Frequency Analysis and Probability Distribution: The message string to be encoded is:
Counting all characters (including spaces, which are essential delimiter symbols in digital text transmission):
- Total length of message string: characters.
The character frequency count and corresponding probabilities are:
| Symbol () | Frequency () | Probability | (bits) | |
|---|---|---|---|---|
[space] | 6 | |||
h | 5 | |||
a | 4 | |||
e | 4 | |||
Y | 2 | |||
k | 2 | |||
K | 1 | |||
o | 1 | |||
j | 1 | |||
i | 1 | |||
R | 1 | |||
c | 1 | |||
D | 1 | |||
s | 1 | |||
L | 1 | |||
u | 1 | |||
g | 1 | |||
N | 1 | |||
y | 1 | |||
| Total | 36 | 1.0000 | — |
Source Entropy Calculation: The theoretical minimum average information per symbol is given by Shannon's Source Entropy:
Substituting the calculated probabilities:
Huffman Tree Construction and Codeword Assignment: The Huffman algorithm iteratively combines the two lowest-probability nodes into a parent node until a single root node is formed:
- Combining 1-count symbols:
- Pair each 1-frequency symbol in groups of two: each pair produces weight .
- Combining pairs of weight 2 produces nodes of weight 4.
- Assigning binary digits (
0to left branch,1to right branch):- High-frequency symbols receive shorter 3-bit codes:
[space](): length bits (111)h(): length bits (101)a(): length bits (000)e(): length bits (001)
- Medium-frequency symbols receive 4-bit and 5-bit codes:
k(): length bits (0100)Y(): length bits (11011)- All thirteen 1-frequency symbols (
K, o, j, i, R, c, D, s, L, u, g, N, y) receive 5-bit codes (e.g.,01010,01011,01100, etc.).
- High-frequency symbols receive shorter 3-bit codes:
Average Codeword Length and Coding Efficiency:
- Average Codeword Length ():
- Coding Efficiency ():
- Code Redundancy ():
(Note: If the string is evaluated case-insensitively with 17 symbols, , , and . Both approaches demonstrate optimal Huffman coding efficiency exceeding ).
For the string "Khoji Rahechha Desh Le Yek Yug Nayak" ( characters, 19 unique symbols):
- Source Entropy:
- Average Codeword Length:
- Coding Efficiency:
- Redundancy: