算法设计与分析-习题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.对于下面的数据构造一套哈夫曼编码字符ABCD_出现概率0.40.10.20.150.15先选择最小的B、D然后选_和C再选0.25和0.35最后选A最终为此时的编码b.用a中的编码对文本ABACABAD进行编码。0100011101000101c.对于 100010111001010用a中的编码进行解码。BAD_ADA2.出于数据传输的目的我们常常需要一套码长差异最小的编码(在具有相同平均长度的编码中)。针对以下数据构造哈夫曼编码。在权重相同的情况下选择不同的子树会导致两套不同的编码。请计算这两套编码码长的平均值和方差。字符ABCDE出现概率0.10.10.20.20.4构造的树为A:1100 B:1101 C:111 D:10 E:0平均值4*0.14*0.13*0.22*0.21*0.42.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.41.36第二种另外的平均值为2.2方差是0.963.请指出是否每一种哈夫曼编码都有下面的特性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如果当前字符码长比前一个长就在后面补 010.猜底牌 设计一种策略使在下面的游戏中期望提问的次数达到最小([Gar94])。有一副纸牌是由1张A 2张2 3张3… 9张9组成的一共包含45张牌。有人从这副洗过的牌中抽出一张牌问一连串可以回答是或否的问题来确定这张牌的点数。使用哈夫曼编码构造最优二叉决策树。每次合并频率最小的两组牌让出现频率越高的牌需要的是 / 否提问次数越少。这样可以使期望提问次数达到最小。最小期望提问次数 ≈2.5~2.7 次精确值139/45 ≈3.09次