Huffman coding of a sentence (Khoji Rahechha)

Assumptions: spaces are ignored, upper and lower case letters are treated as the same symbol, and each letter is a source symbol. The sentence has 30 letters and 16 distinct symbols.

Step 1: frequencies

h=5, a=4, e=4, k=3, y=3, c=1, d=1, g=1, i=1, j=1, l=1, n=1, o=1, r=1, s=1, u=1

Step 2: build the Huffman tree

Repeatedly merge the two smallest weights (N1, N2, ... are the new nodes):

 1. c(1) + d(1) = 2  -> N1
 2. g(1) + i(1) = 2  -> N2
 3. j(1) + l(1) = 2  -> N3
 4. n(1) + o(1) = 2  -> N4
 5. r(1) + s(1) = 2  -> N5
 6. u(1) + N1(2) = 3  -> N6
 7. N2(2) + N3(2) = 4  -> N7
 8. N4(2) + N5(2) = 4  -> N8
 9. k(3) + y(3) = 6  -> N9
10. N6(3) + a(4) = 7  -> N10
11. e(4) + N7(4) = 8  -> N11
12. N8(4) + h(5) = 9  -> N12
13. N9(6) + N10(7) = 13  -> N13
14. N11(8) + N12(9) = 17  -> N14
15. N13(13) + N14(17) = 30  -> N15

The branch to the smaller-weight node is labelled 0 and to the larger 1, and the codes are read from the root downwards.

Step 3: code table

Step 4: entropy, average length and efficiency

• Entropy H = −Σ p log₂ p = 3.6696 bits/symbol
• Average length L = Σ p·l = 111/30 = 3.7000 bits/symbol
• Efficiency η = H / L = 3.6696 / 3.7000 = 99.18 %
• Total bits with Huffman = 111; with fixed-length codes (4 bits/symbol) = 120, so saving = 9 bits.

(Huffman codes are not unique when weights tie, but every choice gives the same average length and efficiency.)

Answer: η ≈ 99.2 %