Past exam question: 2078 Chaitra (Regular), Q7
Open in the Padhaiko appQuestion
Construct a Huffman code for the given symbols.
| Symbol | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Frequency (in thousands) | 35 | 18 | 10 | 20 | 9 | 8 |
Solution
Arrange Symbols by Frequency (Min-Priority Queue): Initial sorted frequencies: F(8), E(9), C(10), B(18), D(20), A(35) (total frequency = ).
Greedy Tree Merging:
- Merge two smallest:
F(8)andE(9)FE(17). Remaining:C(10), FE(17), B(18), D(20), A(35). - Merge two smallest:
C(10)andFE(17)CFE(27). Remaining:B(18), D(20), CFE(27), A(35). - Merge two smallest:
B(18)andD(20)BD(38). Remaining:CFE(27), A(35), BD(38). - Merge two smallest:
CFE(27)andA(35)CFEA(62). Remaining:BD(38), CFEA(62). - Merge remaining two:
BD(38)andCFEA(62)Root(100).
Huffman Tree and Code Assignment (0 = left, 1 = right):
(100)
/ \
(38) (62)
/ \ / \
B(18) D(20) (27) A(35)
/ \
C(10) (17)
/ \
F(8) E(9)
Reading root-to-leaf paths:
| Symbol | Frequency | Codeword | Length | Weighted Bits |
|---|---|---|---|---|
| A | 35 | 11 | 2 | 70 |
| B | 18 | 00 | 2 | 36 |
| D | 20 | 01 | 2 | 40 |
| C | 10 | 100 | 3 | 30 |
| F | 8 | 1010 | 4 | 32 |
| E | 9 | 1011 | 4 | 36 |
Average code length = bits/symbol.
Answer:
Huffman codes (0 left, 1 right): A = 11, B = 00, D = 01, C = 100, F = 1010, E = 1011 (average code length = bits/symbol).