算法设计与分析-习题9.4
目录
1.
a.对于下面的数据构造一套哈夫曼编码：
b.用a中的编码对文本ABACABAD进行编码。
c.对于 100010111001010用a中的编码进行解码。
2.出于数据传输的目的，我们常常需要一套码长差异最小的编码(在具有相同平均长度的编码中)。针对以下数据构造哈夫曼编码。在权重相同的情况下，选择不同的子树会导致两套不同的编码。请计算这两套编码码长的平均值和方差。
3.请指出是否每一种哈夫曼编码都有下面的特性：
a.频率最低的两个字符具有相同的码长。
b.频率较高的字符的码长总是小于等于频率较低的字符的码长。
4.有一个n个字符构成的字母表，它的哈夫曼编码可能具有的最大码长是多少？
5.
a.为哈夫曼树的构造算法写一段伪代码。
b.如果以字母表的规模为自变量，哈夫曼树构造算法的时间效率类型是什么？
6.请说明，如果字母表中的字符按照它们的使用频率顺序给出，则可以在线性时间内构造一棵哈夫曼树。
7.给定一棵哈夫曼编码树，可以用哪种算法求出所有字符的代码字？以字母表的规模为自变量，算法的时间效率类型是什么？
8.请解释如何在不实际构造一棵哈夫曼树的情况下，生成一套哈夫曼编码。
10.猜底牌 设计一种策略，使在下面的游戏中，期望提问的次数达到最小([Gar94])。有一副纸牌，是由1张A， 2张2， 3张3，…， 9张9组成的，一共包含45张牌。有人从这副洗过的牌中抽出一张牌，问一连串可以回答是或否的问题来确定这张牌的点数。
最小期望提问次数 ≈ 2.5~2.7 次
1.
a.对于下面的数据构造一套哈夫曼编码：
字符 | A | B | C | D | _ |
出现概率 | 0.4 | 0.1 | 0.2 | 0.15 | 0.15 |
先选择最小的B、D
然后选_和C；再选0.25和0.35
最后选A
最终为：
此时的编码：
b.用a中的编码对文本ABACABAD进行编码。
0100011101000101
c.对于 100010111001010用a中的编码进行解码。
BAD_ADA
2.出于数据传输的目的，我们常常需要一套码长差异最小的编码(在具有相同平均长度的编码中)。针对以下数据构造哈夫曼编码。在权重相同的情况下，选择不同的子树会导致两套不同的编码。请计算这两套编码码长的平均值和方差。
字符 | A | B | C | D | E |
出现概率 | 0.1 | 0.1 | 0.2 | 0.2 | 0.4 |
构造的树为：
A:1100 B:1101 C:111 D:10 E:0
平均值=4*0.1+4*0.1+3*0.2+2*0.2+1*0.4=2.2
方差=(4-2.2)^2*0.1+(4-2.2)^2*0.1+(3-2.2)^2*0.2+(2.2-2)^2*0.2+(2.2-1)^2*0.4=1.36
第二种：
另外的平均值为2.2，方差是0.96
3.请指出是否每一种哈夫曼编码都有下面的特性：
a.频率最低的两个字符具有相同的码长。
- 哈夫曼算法第一步就是把频率最小的两个结点合并。
- 它们一定是同一个父结点的左右孩子。
- 从根到它们的深度一样，所以码长一定相同。
b.频率较高的字符的码长总是小于等于频率较低的字符的码长。
哈夫曼树是一棵带权路径长度最优的二叉树，它满足：频率越大的字符，离根越近，码长越短；频率越小的字符，离根越远，码长越长。、
4.有一个n个字符构成的字母表，它的哈夫曼编码可能具有的最大码长是多少？
要让某个字符的码长最长，就要把它一直放在合并的最底层，每次都只和最小的节点合并，让它一层层往下沉。
构造方式（最 “不平衡” 的哈夫曼树）：
- 字符频率：1, 1, 2, 4, 8, 16, …（后一个是前面所有之和）
- 每次都把频率最小的两个合并
- 最早的那个最小字符，会一路被压到最深
结果：
- 叶子节点最大深度 =n − 1
- 对应哈夫曼编码最长可能n − 1 位
5.
a.为哈夫曼树的构造算法写一段伪代码。
算法 HUFFMAN(C): 输入: 字符集合 C，每个字符 c 有频率 freq[c] 输出: 哈夫曼树的根节点 n = |C| // 字符个数 创建最小优先队列 Q 将 C 中所有字符加入 Q // 按频率从小到大排序 // 合并 n-1 次 for i = 1 to n-1: 新建一个空节点 z x = 最小队列 Q 中取出频率最小的节点 y = 最小队列 Q 中取出频率次小的节点 z.left = x // x 作为左孩子 z.right = y // y 作为右孩子 z.freq = x.freq + y.freq // 父节点频率 = 孩子之和 将 z 插入优先队列 Q return Q 中最后剩下的节点 // 根节点b.如果以字母表的规模为自变量，哈夫曼树构造算法的时间效率类型是什么？
一共执行n-1 次合并，每次从最小堆取出 / 插入节点的时间是O(log n)，所以效率是Θ(n log n)
6.请说明，如果字母表中的字符按照它们的使用频率顺序给出，则可以在线性时间内构造一棵哈夫曼树。
普通哈夫曼算法慢，是因为用了最小优先队列（堆），每次取最小要O(log n)。
但如果频率已经排好序，我们可以用两个普通队列（FIFO）代替堆：
- 队列 Q₁：存放初始的 n 个字符结点（已按频率升序）。
- 队列 Q₂：存放每次合并生成的新结点。
每次要取两个最小结点时，只需要比较 Q₁ 和 Q₂ 的队首，O(1)就能取出最小的两个，不需要 log n。
7.给定一棵哈夫曼编码树，可以用哪种算法求出所有字符的代码字？以字母表的规模为自变量，算法的时间效率类型是什么？
深度优先遍历（DFS） 或 广度优先遍历（BFS）
做法：
- 从根节点开始遍历整棵哈夫曼树
- 向左走记为
0，向右走记为1 - 每走到一个叶子节点，就得到了该字符对应的编码
效率为Θ(n)，因为要把每个节点都走一遍
8.请解释如何在不实际构造一棵哈夫曼树的情况下，生成一套哈夫曼编码。
根据字符频率，像哈夫曼算法一样不断合并两个最小频率，不构建树结构，只记录每个字符在合并中被 “下沉” 的层数 = 码长。
这样生成的编码一定是前缀码，一定是哈夫曼编码。
- 码长越短，字符越靠前
- 相同码长的排在一起
- 第一个字符的编码 = 全 0（长度等于它的码长）
- 后面每个字符的编码 = 前一个编码+1（二进制加 1）
- 如果当前字符码长比前一个长，就在后面补 0
10.猜底牌 设计一种策略，使在下面的游戏中，期望提问的次数达到最小([Gar94])。有一副纸牌，是由1张A， 2张2， 3张3，…， 9张9组成的，一共包含45张牌。有人从这副洗过的牌中抽出一张牌，问一连串可以回答是或否的问题来确定这张牌的点数。
使用哈夫曼编码构造最优二叉决策树。每次合并频率最小的两组牌，让出现频率越高的牌，需要的是 / 否提问次数越少。这样可以使期望提问次数达到最小。
最小期望提问次数 ≈2.5~2.7 次
（精确值：139/45 ≈3.09次）