Huffman coding of "Mississippi is missing"

Weighted Huffman coding builds the Huffman tree from the actual symbol counts (weights) in the message. Assumptions: case is ignored, and the space is counted as a symbol. The message "mississippi is missing" has 22 symbols and 7 distinct symbols: i = 7, s = 7, space = 2, m = 2, p = 2, g = 1, n = 1.

Huffman tree construction

Huffman procedure: list the symbols by probability. Repeatedly combine the two least probable entries into one node whose weight is their sum, until only one node is left. In each merge, the first group listed gets bit 0 and the second group gets bit 1. Each symbol's code word is read from the root down to that symbol.

1. {n} (1) + {g} (1) → 2
2. {m} (2) + {space} (2) → 4
3. {n, g} (2) + {p} (2) → 4
4. {n, g, p} (4) + {m, space} (4) → 8
5. {s} (7) + {i} (7) → 14
6. {s, i} (14) + {n, g, p, m, space} (8) → 22

                    (22)
                0 /      \ 1
              (14)        (8)
            0/   \1     0/   \1
           s:7   i:7  (4)     (4)
                     0/ \1   0/  \1
                   (2)  p:2  m:2  sp:2
                  0/ \1
                 n:1  g:1

Code table

Efficiency

Average code length:

$$\bar L = \sum p_i l_i = \frac{54}{22} = 2.4545\ \text{bits/symbol}$$

Here the numerator is the total number of bits in the encoded message: $7(2) + 7(2) + 2(3) + 2(3) + 2(3) + 1(4) + 1(4) = 54$ bits.

Entropy:

$$H = -\sum p_i \log_2 p_i = 2.4002\ \text{bits/symbol}$$

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{2.4002}{2.4545} = 0.9779 = 97.79\%$$

Redundancy $= 1 - \eta = 2.21\%$.

A fixed-length code for 7 symbols needs $\lceil \log_2 7 \rceil = 3$ bits/symbol ($\eta = 80.01\%$). Huffman saves 18.18% of the bits.

Answer: $\bar L = 2.455$ bits/symbol, $H = 2.400$ bits/symbol, transmission efficiency η ≈ 97.79%. The whole message takes 54 bits, compared with 66 bits using a 3-bit fixed code.