算法导论15.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

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$个字符的频率为$fn(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{Fn=\sum{i=1}^n fi = f{i+2}-1}$。考虑使用数学归纳法进行证明。

  • 当$n=1$时，$F_1=f_3-1=2-1=1$，成立。

  • 当$n>1$时，假设对于$m=1,2,\dots,m-1$，$Fm=f{m+2}-1$都成立。那么有$Fn=F{n-1}+fn=f{n+1}-1+fn=f{n+2}-1$。结论仍然成立。

因此，$Fn=f{n+2}-1$成立。

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

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

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

保持：若$Q$中的元素当前为${fi,F{i-1},f{i+1},f{i+2},\dots,fn}$，那么弹出最小的两个元素$f_i,F{i-1}$，构造出新元素$Fi=F{i-1}+fi$后，再添加进$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给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 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给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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$，序列${f1,f_2,\dots,f{2^n}}$表示所有字符的频率之和，并且已经排好序。按照题目定义，还满足$2f1\ge f{2^n}$。

按照HUFFMAN算法，可以知道之后插入的新节点$F1=f_1+f_2\ge f{2^n}$，可以视为经过了$2^{n-1}-1$次FOR循环后，节点$F1$才有机会再弹出。那么在这$2^{n-1}$次迭代中，$f$的所有元素都将被第5-6行弹出了一次，并且构建成了一个长度为$F{2^{n-1}}$的有序序列。可以证明仍然满足$2F1\ge F{2^n-1}$，因为$2F1=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$比特的编码表示。因此不存在一个无损压缩器可以对所有文件，都能产生有效的压缩。