Huffman code for a sentence (Kun Mandir)

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 25 letters and 13 distinct symbols.

Huffman algorithm

1. List symbols with their probabilities.
2. Merge the two smallest probabilities into one node (sum).
3. Repeat until one node remains.
4. Label branches 0 and 1; read each code from the root to the leaf.

Step 1: frequencies

a=5, n=3, h=2, i=2, m=2, r=2, t=2, u=2, c=1, d=1, j=1, k=1, y=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. j(1) + k(1) = 2  -> N2
 3. y(1) + h(2) = 3  -> N3
 4. i(2) + m(2) = 4  -> N4
 5. r(2) + t(2) = 4  -> N5
 6. u(2) + N1(2) = 4  -> N6
 7. N2(2) + n(3) = 5  -> N7
 8. N3(3) + N4(4) = 7  -> N8
 9. N5(4) + N6(4) = 8  -> N9
10. a(5) + N7(5) = 10  -> N10
11. N8(7) + N9(8) = 15  -> N11
12. N10(10) + N11(15) = 25  -> N12

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.5093 bits/symbol
• Average length L = Σ p·l = 89/25 = 3.5600 bits/symbol
• Efficiency η = H / L = 3.5093 / 3.5600 = 98.58 %
• Total bits with Huffman = 89; with fixed-length codes (4 bits/symbol) = 100, so saving = 11 bits.

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

Answer: η ≈ 98.6 %