算法设计与分析 课件 6.5.1-贪心法应用-哈夫曼编码-问题描述和算法求解

信息工程大学算法设计与分析贪心法—哈夫曼编码国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版二进制编码问题：

给定字符集D={d1,d2,...,dn}，字符出现的频率为{w1,w2,…,wn}，要求为每个字符确定一种由0、1构成的二进制编码方案，使得编码后的文件长度最短。字符编码转换01编码译码转换字符

编码方案：等长编码存在的问题：字符频率不等时，得到的编码总长度可能不是最短的。非等长编码潜在的问题：如00表示E，01表示T，0001表示W，收到的编码是0001，那么这组编码是W还是ET呢？无法区分!!原因是E的编码和W的编码的开始部分（前缀）相同。2.非等长编码：采用非等长的二进制串表示。频度高的字符采用较短的二进制串表示，频度低的字符采用较长的二进制串表示，从而达到缩短报文总长的目的。前缀码：任一字符的编码都不是其它字符编码的前缀。因此，对字符集进行不等长编码，则要求这种不等长编码必须是前缀码。判断题。等长编码一定是前缀码。A.正确B.错误

戴维•哈夫曼提出了利用二叉树构造最优前缀码的方法。相应的二叉树称为哈夫曼树，对应的编码称为哈夫曼编码。设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度li与叶子结点权值wi的乘积的和称为该二叉树的带权路径长度(WeightedPathLength，WPL)。

WPL最小的二叉树称为哈夫曼树。字符出现的频率根结点到字符结点的路径长度二进制编码问题本质上是构造哈夫曼树的问题。基于出现频率越高的字符、编码长度越短的贪心思想，哈夫曼提出了构造哈夫曼树的贪心法，优先选择频率低的字符，以自下而上的方式构造哈夫曼树。哈夫曼树的构造过程：初始时，每个结点作为一棵树，共有n棵树；新建一个结点v，选择具有最低频率的两个根结点作为结点v的左、右孩子，形成一棵树，v的权值为其左、右孩子的权值之和；重复步骤2，直到只剩下一棵树为止。选择题。已知n个叶子结点，构造哈夫曼树需要执行（）次合并操作（合并操作指步骤2）。A.nB.n-1C.以上都不对c:14b:15d:17a:38f:6e:101601第一步例子：a:38，b:15，c:14，d:17，f:6，e:10c:14b:15d:17a:38f:6e:10初始化c:14b:15d:17a:38f:6e:101601第二步2901c:14b:152901f:6e:101601d:1733a:3801620110001第五步c:14b:152901f:6e:101601d:1733a:38016201第四步c:14b:152901f:6e:101601d:1733a:3801第三步字符对应的编码：f：1100e：1101d：111c：100b：101a：0c:14b:152901f:6e:101601d:1733a:3801620110001选择题。下图所示的哈夫曼树，密文“010110111111001101100111”对应的明文是（）。A.abdffecdB.abbdfecdC.以上都不对Huffman(C)/*构建哈夫曼树*/输入：C={x1,x2,…,xn}，n,

f(xi),i=1,2,…,n输出：C’1.复制C到C’中，初始化C’中每个字符的左、右孩子为-1；2.Q

C’;/*用字符频率集构建小根堆*/3.for(i=1;i<=n-1;i++){4.z=Allocate-Node();/*生成新结点z加入C’中*/5.z.left=pop(Q);/*取出Q最小元为z的左儿子*/6.z.right=pop(Q);/*取出Q次小元为z的右儿子*/

7.f(z)=f(x)+f(y);8.push(Q,z);/*将z插入Q*/9.}10.returnC’;时间复杂度为O(nlogn)石子合并问题：有n堆石子排成一排，依次编号为1~n。现要将石子两两合并为一堆，并将新的一堆石子数记为本次合并的代价。计算将n堆石子合并成一堆的最小代价。

结点i的权值wi根结点到结点i的路径长度li

*3465101518合并代价=10+15+18=43=3