- Asked 7/8
- 2076 Bhadra · 10 marks
- 2074 Magh · 10 marks
- 2072 Magh · 4+10 marks
- 2071 Bhadra · 10 marks
- 2073 Bhadra · 8 marks
- 2072 Asoj · 8 marks
- 2075 Bhadra · 4 marks
Huffman code tree steps with example
Short answer
List symbols with probabilities, sort ascending, combine the two smallest into a parent node, repeat until one root remains, label branches 0 and 1, then read codes from root to leaf. For A=.4, B=.3, C=.15, D=.1, E=.05, codes are A=0, B=10, C=110, E=1110, D=1111, average 2.05 bits/symbol.
Explain the Huffman coding algorithm: what are the steps to create the Huffman code tree? Explain with example.
Huffman coding is a lossless, variable-length, entropy coding method. It gives short codes to frequent symbols and long codes to rare symbols, so the average code length is minimum. The codes are prefix codes: no code is the start of another, so decoding is unambiguous.
Steps to build the Huffman code tree
- List all symbols with their probabilities (or frequencies).
- Sort them in ascending order of probability.
- Take the two nodes with the smallest probabilities and join them under a new parent node whose probability is their sum.
- Put the new node back in the list and sort again.
- Repeat steps 3 and 4 until only one node (the root, probability 1) remains.
- Label every left branch 0 and every right branch 1 (or the reverse, consistently).
- Read the code of each symbol by following the path from the root to its leaf.
Example
Symbols and probabilities: A = 0.40, B = 0.30, C = 0.15, D = 0.10, E = 0.05.
| Step | Combine | New node |
|---|---|---|
| 1 | E (0.05) + D (0.10) | ED = 0.15 |
| 2 | C (0.15) + ED (0.15) | CED = 0.30 |
| 3 | B (0.30) + CED (0.30) | BCED = 0.60 |
| 4 | A (0.40) + BCED (0.60) | Root = 1.00 |
Root(1.0)
0/ \1
A(.4) BCED(.6)
0/ \1
B(.3) CED(.3)
0/ \1
C(.15) ED(.15)
0/ \1
E(.05) D(.10)
Codes read from the root:
| Symbol | Probability | Code | Length |
|---|---|---|---|
| A | 0.40 | 0 | 1 |
| B | 0.30 | 10 | 2 |
| C | 0.15 | 110 | 3 |
| E | 0.05 | 1110 | 4 |
| D | 0.10 | 1111 | 4 |
(Here the 0/1 labels on the last branch put E on 0 and D on 1; swapping them is equally valid.)
Average length = 0.40(1) + 0.30(2) + 0.15(3) + 0.05(4) + 0.10(4) = 0.40 + 0.60 + 0.45 + 0.20 + 0.40 = 2.05 bits/symbol.
A fixed-length code for 5 symbols needs 3 bits, so Huffman saves (3 - 2.05)/3 = 31.7%.
Decoding example: the bit string 0 10 110 0 decodes as A B C A, because no code is a prefix of another.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Huffman code for symbols A to E · Multimedia System, chapter 5
- How Huffman code reduces file size · Multimedia System, chapter 5
- Algorithm for Huffman code · Data Structure and Algorithm, chapter 6
- Source vs channel coding; Huffman for five symbols · Communication Systems, chapter 6
- Importance of source coding; Huffman for eight symbols at 1000 symbols/s · Communication Systems, chapter 6
- Huffman coding principle · Data Communication, chapter 8 · asked 3×