A text is made up of the characters a, b, c, d, e each occurring with the…

Construct the Huffman tree by repeatedly combining the two least probable symbols:

• Start with probabilities: a = 0.11, b = 0.40, c = 0.16, d = 0.09, e = 0.24.

• Combine the two smallest: d(0.09) + a(0.11) = 0.20.

• Combine next two smallest: c(0.16) + 0.20 = 0.36.

• Combine e(0.24) + 0.36 = 0.60.

• Combine b(0.40) + 0.60 = 1.00 (root).

Read off code lengths from the tree:

• b has length 1

• e has length 2

• c has length 3

• a has length 4

• d has length 4

Compute the average code length L = Σ p(i)·l(i):

• 0.40 · 1 = 0.40

• 0.24 · 2 = 0.48

• 0.16 · 3 = 0.48

• 0.11 · 4 = 0.44

• 0.09 · 4 = 0.36

Sum: 0.40 + 0.48 + 0.48 + 0.44 + 0.36 = 2.16 bits per symbol.

Therefore the optimal Huffman average length is 2.16 bits per symbol.