Weighted Huffman encoding and decoding

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 28 letters and 10 distinct symbols.

Step 1: frequencies

a=7, i=6, t=4, s=3, d=2, l=2, h=1, j=1, n=1, o=1

Step 2: build the Huffman tree

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

 1. h(1) + j(1) = 2  -> N1
 2. n(1) + o(1) = 2  -> N2
 3. d(2) + l(2) = 4  -> N3
 4. N1(2) + N2(2) = 4  -> N4
 5. s(3) + t(4) = 7  -> N5
 6. N3(4) + N4(4) = 8  -> N6
 7. i(6) + a(7) = 13  -> N7
 8. N5(7) + N6(8) = 15  -> N8
 9. N7(13) + N8(15) = 28  -> N9

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 = 2.9532 bits/symbol
• Average length L = Σ p·l = 83/28 = 2.9643 bits/symbol
• Efficiency η = H / L = 2.9532 / 2.9643 = 99.63 %
• Total bits with Huffman = 83; with fixed-length codes (4 bits/symbol) = 112, so saving = 29 bits.

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

Answer: η ≈ 99.6 %

Encoding the sentence

Replace each letter by its code (words shown separately; spaces are not coded):

Jasta    111010110010101
lai      11010100
tastai   101011001010100
dhido    11001110000110011111
lai      11010100
nistai   11110001001010100

Total = 83 bits (against 112 bits with 4-bit fixed codes).

Complete stream:

11101011001010111010100101011001010100110011100001100111111101010011110001001010100

Decoding

The receiver has the same code table (or the same frequencies to rebuild the tree). It reads bits from the left and walks down the tree (0 = left branch, 1 = right branch) until a leaf is reached, outputs that letter and restarts at the root. Because no code is a prefix of another, there is no ambiguity.

First bits: 11101 01 100 101 01 ...

• 1 → 11 → 111 → 1110 → 11101: leaf j
• 0 → 01: leaf a
• 1 → 10 → 100: leaf s
• 1 → 10 → 101: leaf t
• 0 → 01: leaf a

So "jasta" is recovered, and the same procedure over the whole stream gives "jastalaitastaidhidolainistai" (the original letters, without spaces).