SICP 全笔记

Exercise 2.71. Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., $2^{n-1}$. Sketch the tree for n=5; for n=10. In such a tree (for general n) how may bits are required to encode the most frequent symbol? the least frequent symbol?

我们可以把树画成下面这个样子的。

({A B C D E},31}
      /  \
     /    \
    /      \
 A, 2^4  ({B C D E}, 15)
             /  \
            /    \
           /      \
        B, 2^3    ({C D E}, 7)
                     /  \
                    /    \
                   /      \
                 C, 2^2   ({D E}, 3)
                            / \
                           /   \
                          /     \
                         D, 2   E, 1

因为 $2^1, 2^2, 2^3, \dots$ 的数列前面 n 项和永远比第 n + 1 项小 1，所以 n 为多少，就有几层树（每个 symbol 都单独地占了一层）。

因此，频率最高的，只要 1 bit，最低的，要 n-1 个 bit 位。