算法导论15.3 Exercises 答案

15.3-1

由于\(x.freq\le y.freq\)，因此\(x.freq\)是\(C\)中频率的最小值，此时\(y.freq\)是\(C\)中频率的次小值。由于\(a.freq\le b.freq\)，并且有\(x.freq=b.freq\)，那么有\(x.freq=a.freq\)。由于\(y.freq\)是\(C\)中的次小值，并且\(C\)中已经有\(3\)个频率值是最小且相等的，因此\(y.freq=b.freq\)。最终有\(x.freq=y.freq=a.freq=b.freq\)。

15.3-2

令\(T\)为这一棵非满二叉树，并且\(u\)是某一个只包含一个子节点的节点，那么考虑删除节点\(u\)，并将\(u\)的这个儿子拼接到其父节点中，得到一棵新树\(T'\)。这棵树\(T'\)将会比\(T\)更加优秀，证明过程是考虑比较\(B(T)\)和\(B(T')\)的大小。

注意到，由于\(u\)节点被删除，此时以\(u\)为子树的所有节点的深度都减少了\(1\)。那么有

\(\begin{aligned} B(T')&=\sum_{c\in C} c.freq\cdot d_{T'}(x)\\ &=\sum_{u\text{ is an ancestor of }x} x.freq\cdot d_{T'}(x)+\sum_{u\text{ isn't an ancestor of }x} x.freq\cdot d_{T'}(x)\\ &=\sum_{u\text{ is an ancestor of }x} x.freq\cdot d_{T}(x)+\sum_{u\text{ isn't an ancestor of }x} x.freq\cdot (d_{T}(x)-1)\\ &<\sum_{u\text{ is an ancestor of }x} x.freq\cdot d_{T}(x)+\sum_{u\text{ isn't an ancestor of }x} x.freq\cdot d_{T}(x)\\ &=B(T) \end{aligned}\)

由此可知，我们构造出了一棵更优秀的树\(T'\)。因此一个非满二叉树必定不可能对应一个最优无前缀编码。

15.3-3

由此可以产生出如下的哈夫曼树。

graph TD
  A[a:1]
  B[b:1]
  C[c:2]
  D[d:3]
  E[e:5]
  F[f:8]
  G[g:13]
  H[h:21]
  ab((2))
  ac((4))
  ad((7))
  ae((12))
  af((20))
  ag((33))
  ah((54))
  ah--0---H
  ah--1---ag
  ab--0---B
  ab--1---A
  ac--0---C
  ac--1---ab
  ad--0---D
  ad--1---ac
  ae--0---E
  ae--1---ad
  af--0---F
  af--1---ae
  ag--0---G
  ag--1---af

由此可以构造出哈夫曼编码：

\(\begin{array}{|l|l|} \hline a & 1111111\\ \hline b & 1111110\\ \hline c & 111110\\ \hline d & 11110\\ \hline e & 1110\\ \hline f & 110\\ \hline g & 10\\ \hline h & 0\\ \hline \end{array}\)

对于一般情况而言，如果现在有\(n\)个字符，第\(n\)个字符的频率为\(f_n(f_1=f_2=1,f_n=f_{n-1}+f_{n-2})\)，那么可以按照如下构造哈夫曼编码：第\(1\)个字符的哈夫曼编码为\(1^{n-1}\)，对于第\(m(m>1)\)个字符，其哈夫曼编码为\(1^{n-m} \mid\mid 0\)。

接下来通过说明算法HUFFMAN的运行结果说明这个结论是正确的。

首先证明：\(\displaystyle{F_n=\sum_{i=1}^n f_i = f_{i+2}-1}\)。考虑使用数学归纳法进行证明。

• 当\(n=1\)时，\(F_1=f_3-1=2-1=1\)，成立。

• 当\(n>1\)时，假设对于\(m=1,2,\dots,m-1\)，\(F_m=f_{m+2}-1\)都成立。那么有\(F_n=F_{n-1}+f_n=f_{n+1}-1+f_n=f_{n+2}-1\)。结论仍然成立。

因此，\(F_n=f_{n+2}-1\)成立。

接下来证明循环不变量：最小优先队列中的关键字按顺序总是\(\{f_i,F_{i-1},f_{i+2},f_{i+3},\dots,f_n\}\)，并且用\(F\)表示的关键字\(F_{i-1}\)要么是最小值，要么是次小值。这个序列已经有序的原因是，当\(i\ge 2\)时，\(F_{i-1}=f_{i+1}-1=f_i+(f_{i-1}-1)\ge f_i,F_{i-1}=f_{i+1}-1<f_{i+2}\)。

因此，算法HUFFMAN总是弹出\(Q\)中用\(F\)表示的那个关键字，最终变成了一个新关键字\(F_i=F_{i-1}+f_i\)。最终产生的编码如上述结论。

初始化：\(Q\)中的元素一开始为\(\{f_2,f_1,f_3,\dots,f_n\}\)，将\(f_1\)用\(F_1\)代替后，循环不变量成立。

保持：若\(Q\)中的元素当前为\(\{f_i,F_{i-1},f_{i+1},f_{i+2},\dots,f_n\}\)，那么弹出最小的两个元素\(f_i,F_{i-1}\)，构造出新元素\(F_i=F_{i-1}+f_i\)后，再添加进\(Q\)中，得到\(\{f_{i+1},F_{i},f_{i+2},f_{i+3},\dots,f_n\}\)，根据上面的结论可知，这个序列仍然是有序的。在这个保持过程中，用\(F\)表示的那个关键字被弹出来，这个用\(F\)表示的关键字添加进\(Q\)后，仍然是\(Q\)中最小或者是次小的数，在下一次仍然会被弹出。

终止：\(Q\)中只剩下一个元素\(F_n\)，整个序列仍然是有序的。

因此，用\(F\)表示的关键字不断被弹出、加入，最终构造出的哈夫曼树的所有内部节点至少都有一个叶子节点，因此构造出来的哈夫曼编码如上结论所述。

15.3-4

令\(L(T)\)表示满二叉树\(T\)的叶子节点的频率之和，\(t(u)\)表示以\(u\)为根节点的子树，\(l(T),r(T)\)分别为\(T\)的左子树和右子树。

题目相当于证明\(\displaystyle{B(T)=\sum_{u\in T} L(l(t(u)))+L(r(t(u)))}\)。对于\(T\)中的一个内部节点\(u\)而言，\(L(l(t(u)))+L(r(t(u)))\)相当于是以\(u\)为根节点的子树的叶节点频率之和，即\(L(t(u))\)；对于一个叶节点\(l\)，由于左右子节点都为空，因此\(L(l(t(u)))+L(r(t(u)))\)的值为\(0\)。

最终转化成证明\(\displaystyle{B(T)=\sum_{u\in T} L(t(u))-L(T)}\)。考虑使用归纳法证明这个式子。

对于一棵只有\(1\)个节点的二叉树\(E\)，注意\(E\)也是一个满二叉树，那么根据\(B(E)\)的定义，可知\(B(E)=L(E)-L(E)=0\)，原结论成立。

对于任意一棵\(n\)个节点的满二叉树树\(T\)，设其根节点为\(x\)。假设对于\(1,2,3,\dots n-1\)个节点的满二叉树，上面的结论都成立，那么其左子树\(l(t(x))\)和右子树\(r(t(x))\)都满足这个条件。由于\(T\)可以视为是由根节点\(x\)，左子树\(l(t(x))\)和右子树\(r(t(x))\)构成，因此相对于\(T,l(t(x))\)和\(r(t(x))\)无论是根节点还是叶子节点，深度都增加了\(1\)，因此总体代价都增加了\(L(l(t(x)))+L(r(t(x)))=L(T)\)。那么有

\(\begin{aligned} B(T)&=B(l(x))+B(r(x))+L(T)\\ &= \sum_{u\in l(x)} L(t(u))-L(l(x))+\sum_{u\in r(x)} L(t(u))-L(r(x)) + L(T)\\ &= \sum_{u\in l(x)} L(t(u))+\sum_{u\in r(x)} L(t(u))\\ &= \sum_{u\in T-\{x\}} L(t(u))\\ &= \sum_{u\in T} L(t(u))-L(T)\\ \end{aligned}\)

故原结论成立。

15.3-5

首先，每一个字符都需要用\(\lceil\lg n\rceil\)位二进制编码表示，最终需要\(n\lceil\lg n\rceil\)位的编码表示这个从编码映射到字符的字典。另外的\(2n-1\)个字符则用来表示这棵哈夫曼树的结构。这棵树一共有\(2n-1\)个节点，我们用\(0\)表示内部节点，用\(1\)来表示叶子节点，然后先序遍历整棵树，得到一个\(2n-1\)比特的序列。由于满二叉树每个内部节点必定有两个子节点，回溯到原来的节点再继续遍历时直接从另外一个子节点往下走即可，因此这个比特序列一定能够还原出原来的满二叉树结构。

具体的过程由REBUILD-CODING给出。

// S是这个n ⌈lg n⌉ + 2n - 1长度的字符串；D表示编码规则的转换（可以抽象地理解成一个哈希表），将⌈lg n⌉位比特转换成一个字符。
// S是一个位字符串，假设其有一个子程序READ，READ(x)表示继续往下读取x比特，并返回这个长度为x的比特串；S还有一个方法FINISH，用于判断S的字符串是否读完。
REBUILD-TABLE(S, D, n)
  let S1 and S2 be new STACKS
  let T be a new HASH-TABLE
  c = S.READ(1)
  if c == 1
    error "illegal code"
  PUSH(S1, 0)
  while not S.FINISH()
    while NOT-EMPTY(S1)
      // 当前节点已经都被向下遍历了2次，应该回溯。
      if S1[S1.size] == 2
        POP(S1)
        POP(S2)
      else
        break
    // S1[S1.size]即为栈顶的值，它要么为0，要么为1，表示它是左子节点还是右子节点。
    PUSH(S2, S1[S1.size])
    S1[S1.size] = S1[S1.size] + 1
    PUSH(S1, 0)
    c = S.READ(1)
    if c == 1
      s = S.read(⌈lg n⌉)
      parse S2 into a string t
      T[D[s]] = t
      POP(S2)
      POP(S1)
  return T  

15.3-6

先插入频率为\(0\)的哑节点，使得最小优先队列\(Q\)的大小模\(3\)的值为\(1\)。与构建二元哈夫曼树时的情况相同，每次取出\(3\)个节点，并且新生成一个节点\(q\)的频率是这\(3\)个节点的频率之和，并将\(q\)连接到这\(3\)个节点。具体过程由算法HUFFMAN3给出。

HUFFMAN3(C)
  Q = C
  while Q.size mod 2 != 1
    let p be a new node
    p.freq = 0
    p.left = NIL
    p.right = NIL
    // 将哑节点p插入最小优先队列Q中。
    INSERT(Q, p)
  while Q.size > 1
    let q be a new node
    x = EXTRACT-MIN(Q)
    y = EXTRACT-MIN(Q)
    z = EXTRACT-MIN(Q)
    第i个子节点用p[i]表示。
    q.p[0] = x
    q.p[1] = y
    q.p[2] = z
    INSERT(Q, q)
  return EXTRACT-MIN(Q)

贪心选择性和最优子结构证明和二叉的情况几乎完全相同。最优子结构的证明过程是替换一个三叉节点，贪心选择性证明则考虑频率最小的\(3\)个节点和深度最深的\(3\)个节点。

15.3-7

令\(n=8\)，序列\(\{f_1,f_2,\dots,f_{2^n}\}\)表示所有字符的频率之和，并且已经排好序。按照题目定义，还满足\(2f_1\ge f_{2^n}\)。

按照HUFFMAN算法，可以知道之后插入的新节点\(F_1=f_1+f_2\ge f_{2^n}\)，可以视为经过了\(2^{n-1}-1\)次FOR循环后，节点\(F_1\)才有机会再弹出。那么在这\(2^{n-1}\)次迭代中，\(f\)的所有元素都将被第5-6行弹出了一次，并且构建成了一个长度为\(F_{2^{n-1}}\)的有序序列。可以证明仍然满足\(2F_1\ge F_{2^n-1}\)，因为\(2F_1=2f_1+2f_2\ge f_{2^{n}-1}+f_{2^{n}}=F_{2^{n-1}}\)。

最终由于同一层下的节点每次都恰好被遍历，因此构建出来的哈夫曼树是一个满二叉树，每一个字符都用一个\(n\)比特编码来表示。因此在这种情况下，哈夫曼编码并不比定长编码有效。

15.3-8

可以知道，大小为\(n\)比特的不同文件一共有\(2^n\)。一个无损压缩器为了区分这\(2^n\)个文件，压缩产生的结果必定也是\(2^n\)个不同的编码。如果使用小于\(n\)比特的所有位串来区分这些文件，那么一共有\(2^0+2^1+\dots+2^{n-1}=2^n-1\)种方法，但是仍然还有\(1\)个文件不能用小于\(n\)比特的编码表示。因此不存在一个无损压缩器可以对所有文件，都能产生有效的压缩。