Skip to main content

Huffman encoding of symbols A to F

Short answer

Combine smallest frequencies stepwise: B(0.08)+A(0.10)=0.18, D(0.12)+C(0.15)=0.27, (BA)+F(0.25)=0.43, (DC)+E(0.30)=0.57, merge for root. Codes: A=001, B=000, C=101, D=100, E=11, F=01. Average bits = sum(freq × length) = 2.45 bits/symbol.

Encode the symbols A, B, C, D, E and F with frequencies 0.10, 0.08, 0.15, 0.12, 0.30 and 0.25 respectively by using Huffman algorithm. Also calculate average number of bits used to encode a symbol.

Arrange the symbols by frequency: B 0.08, A 0.10, D 0.12, C 0.15, F 0.25, E 0.30. At each step join the two smallest weights; the smaller one is placed on the left (edge 0).

Construction

StepTwo smallestMerged weightList after step
1B 0.08 + A 0.100.18D 0.12, C 0.15, (BA) 0.18, F 0.25, E 0.30
2D 0.12 + C 0.150.27(BA) 0.18, F 0.25, (DC) 0.27, E 0.30
3(BA) 0.18 + F 0.250.43(DC) 0.27, E 0.30, (BAF) 0.43
4(DC) 0.27 + E 0.300.57(BAF) 0.43, (DCE) 0.57
5(BAF) 0.43 + (DCE) 0.571.00root

Huffman tree

                  1.00
               /        \
           0.43          0.57
          /    \        /    \
       0.18    F:0.25 0.27    E:0.30
       /  \            /  \
    B:.08 A:.10     D:.12 C:.15

Codes (left = 0, right = 1)

SymbolFrequencyCodeLengthFreq × length
A0.1000130.30
B0.0800030.24
C0.1510130.45
D0.1210030.36
E0.301120.60
F0.250120.50

Average number of bits per symbol

L = Σ (frequency × code length) = 0.30 + 0.24 + 0.45 + 0.36 + 0.60 + 0.50 = 2.45

Answer: 2.45 bits per symbol (a fixed-length code would need 3 bits). The exact codes may differ if the left/right choice is reversed, but the average length is always 2.45.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →