Huffman code for a sentence (Phool ko)

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 29 letters and 11 distinct symbols.

Step 1: frequencies

a=8, o=5, h=3, k=2, l=2, n=2, p=2, s=2, i=1, m=1, r=1

Step 2: build the Huffman tree

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

 1. i(1) + m(1) = 2  -> N1
 2. r(1) + k(2) = 3  -> N2
 3. l(2) + n(2) = 4  -> N3
 4. p(2) + s(2) = 4  -> N4
 5. N1(2) + h(3) = 5  -> N5
 6. N2(3) + N3(4) = 7  -> N6
 7. N4(4) + o(5) = 9  -> N7
 8. N5(5) + N6(7) = 12  -> N8
 9. a(8) + N7(9) = 17  -> N9
10. N8(12) + N9(17) = 29  -> N10

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.1213 bits/symbol
• Average length L = Σ p·l = 92/29 = 3.1724 bits/symbol
• Efficiency η = H / L = 3.1213 / 3.1724 = 98.39 %
• Total bits with Huffman = 92; with fixed-length codes (4 bits/symbol) = 116, so saving = 24 bits.

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

Transmission efficiency: η ≈ 98.4 %

The fixed-length alternative would need 4 bits per letter, so Huffman coding also reduces the transmitted bits.