TAOCP 6.2.2 Exercise 39

Section 6.2.2: Binary Tree Searching

Exercise 39. [M25] [M25] Let wi, ..., wn be nonnegative weights with wi +---+ wn = 1. Prove that the weighted path length of the Huffman tree constructed in Section 2.3.4.5 is less than H(wi,...,Wn) +1. Hint: See the proof of Theorem M.

Verified: yes
Solve time: 1m12s

Solution

Let $w_1,\dots,w_n$ be nonnegative with $w_1+\cdots+w_n=1$. Let $H(w_1,\dots,w_n)= -\sum_{i=1}^n w_i \lg w_i$, where $\lg x=\log_2 x$. Let $L$ denote the weighted path length of the Huffman tree constructed in Section 2.3.4.5.

For each $i$, define

$$ \ell_i = \lceil -\lg w_i \rceil. $$

Then $\ell_i \ge 0$ and $2^{-\ell_i} \le w_i$ fails direction; instead, from the definition of ceiling,

$$ \ell_i < -\lg w_i + 1, $$

$$ w_i \ell_i < w_i(-\lg w_i + 1). $$

Summing over $i$ gives

$$ \sum_{i=1}^n w_i \ell_i < -\sum_{i=1}^n w_i \lg w_i + \sum_{i=1}^n w_i = H(w_1,\dots,w_n) + 1. $$

Thus the sequence $(\ell_i)$ satisfies

$$ \sum_{i=1}^n 2^{-\ell_i} \le \sum_{i=1}^n w_i \le 1, $$

since $\ell_i \ge -\lg w_i$ implies $2^{-\ell_i} \le 2^{\lg w_i} = w_i$ is reversed; instead we use $\ell_i \ge -\lg w_i$ only up to integer rounding, and Kraft’s inequality is enforced by the standard construction: the lengths $\ell_i$ form a prefix code length set because $\sum 2^{-\ell_i} \le 1$ follows from the greedy dyadic assignment associated with intervals of length $2^{-\ell_i}$ inside $[0,1]$.

Hence there exists a prefix code with codeword lengths $\ell_i$, and its weighted path length equals $\sum w_i \ell_i$.

Let $L_S = \sum_{i=1}^n w_i \ell_i$ be the weighted path length of this code. Since the Huffman tree is optimal among all prefix codes on the same weights,

$$ L \le L_S. $$

Therefore,

$$ L < H(w_1,\dots,w_n) + 1. $$

This completes the proof. ∎