Prove that a binary tree that is not full cannot correspond to an optimal prefix code.
要达到最优前缀编码,必须考虑到前缀的每一种情况,故必须是满二叉树.
更正式的，假设一个节点N不是满的（即它只有一个儿子），不妨设它的父节点为P，它只有左儿子L。则我们总可以将N删掉，并将L直接和P相连，得到一个新的树。这棵新树仍对应一个合法的编码，且N下面所有节点的深度都减少了1，从而新树是比原树更优的一种编码。这与原树是最优编码矛盾。因此一棵不满的二叉树一定不于最优编码对应。
What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers?
a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21
Can you generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers?
推广到n的情形：
设前n+1个斐波那契数，f(0) = 1, f(1) = 1, ... , f(n) = f(n-2) + f(n-1)， 其对应的赫夫曼编码为H(0), H(1), ... , H(n)，则由上图可归纳出：
H(n) = 0, H(k) = H(k+1) + 2n-k (0 < k < n)， H(0) = H(1) + 1
Prove that the total cost of a tree for a code can also be computed as the sum, over all internal nodes, of the combined frequencies of the two children of the node.
straightforward
Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing.
设字符频度为f(1), f(2), ... , f(n)，编码长度依次为d(1), d(2), ... , d(n)。由已知得f(1) >= f(2) >= ... >= f(n)。若编码长度不是递增的，则存在i，使得d(i) > d(i+1)。我们可以交换i和i+1所对应的编码。交换前的总代价为
S = f(1)d(1) + ... + f(i)d(i) + f(i+1)d(i+1) + ... + f(n)d(n)
交换后的总代价为
T = f(1)d(1) + ... + f(i)d(i+1) + f(i+1)d(i) + ... + f(n)d(n)
有T - S = (f(i) - f(i+1))(d(i+1) - d(i)) < 0 <=> T < S。所以交换后得到一个代价更小的编码。这样，我们可以一直交换，直到所有编码长度变为递增的，且其对应的编码也是最优的。
Suppose we have an optimal prefix code on a set C = {0, 1, ..., n - 1} of characters and we wish to transmit this code using as few bits as possible. Show how to represent any optimal prefix code on C using only 2n - 1 + n ⌈lg n⌉ bits. (Hint: Use 2n - 1 bits to specify the structure of the tree, as discovered by a walk of the tree.)
用2n-1位表示树的结构,内部节点用1表示,叶子节点用0表示.用nlog(n)为表示字母序列,每个字母的二进制编码长度为log(n),总共需要nlog(n)位.
Generalize Huffman's algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes.
那就推广到树的结点有三个孩子结点,证明过程同引理16.3的证明.
Suppose a data file contains a sequence of 8-bit characters such that all 256 characters are about as common: the maximum character frequency is less than twice the minimum character frequency. Prove that Huffman coding in this case is no more efficient than using an ordinary 8-bit fixed-length code.
此时生成的Huffman树是一颗满二叉树,跟固定长度编码一致.
Show that no compression scheme can expect to compress a file of randomly chosen 8-bit characters by even a single bit. (Hint: Compare the number of files with the number of possible encoded files.)
Notice that the number of possible source files S using n bit and compressed files E using n bits is 2^n+1 - 1. Since any compression algorithm must assign each element s ∈ S to a distinct element e ∈ E the algorithm cannot hope to actually compress the source file.
Follow @louis1992 on github to help finish this task.