本节初赛复赛都会考。
如何构造一棵哈夫曼树?(哈夫曼树也是一棵二叉树)
给n个点,每个点都有权值,构造一棵哈夫曼树。每次选剩下的两棵根权值最小的树合并成一棵新树,新树的根权值等于两棵合并前树的根权值和。(一开始一个点也看成一棵树,只不过这棵树没有孩子节点)
例1:4个点,a、b、c、d,权值分别为7、5、2、4。
构树过程:因为4个点,所以合并3次(n个点,合并n-1次)
第一步:选根权值最小的两棵树2(c)和4(d)合并,新树的根节点为6,如图(b);
第二步:选根权值最小的两棵树5(b)和6合并,新树的根节点为11,如图(c);
第三步:选根权值最小的两棵树7(a)和11合并,新树的根节点为18,如图(c);
例2:6个点,a、b、c、d、e、f,权值分别为0.4、0.3、0.1、0.1、0.02、0.08。
构图过程同例1。(如下图)
哈夫曼树的基本概念
树的路径长度PL:从树根到树的每个节点的路径长度(每条边长度为1)之和(完全二叉树为这种路径长度最短的二叉树)。
树的带权路径长度WPL:树的所有叶子节点的带权路径长度(该节点到根节点路径长度与节点上权的乘积)之和。
哈夫曼树:带权路径长度WPL最短的二叉树(最优二叉树)构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用。
例如例1,构造哈夫曼树的WPL为35是最小的。具体比较如下图:
哈夫曼编码
一篇电文,原文为:AMCADEDDMCCAD。现在要把原文转换成01串发送给对方。为了节省资源,我们当然希望翻译好的01串长度尽量的短。怎么办?
研究发现:1、只有5个字母E,M,C,A,D;2、这5个字母的使用频度分别为{E,M,C,A,D}= {1,2,3,3,4}。
用频度为权值生成哈夫曼树,并在叶子上标注对应的字母,在树枝上标注分配码“0”或“1”(注:分配码不是边的长度,而是区分左右孩子代表方向):
哈夫曼编码原则: n个节点的哈夫曼树含有2n-1个节点,没有度为1的节点 编码从叶子节点到根节点,译码从根节点到叶子节点。
从哈夫曼树根节点开始,对左子树分配码“0”,右子树分配码“1”,一直到达叶子节点为止,然后将从树根沿每条路径到达叶子结点的代码排列起来,便得到了哈夫曼编码。
各字母的编码即为哈夫曼编码: EMCAD 所有编码长度和为12位,即PL=12,此时的PL并不是最小的,但此时的WPL一定是最小的。WPL最小才能使得密报翻译的01串长度最短。
例3:对原电文进行哈夫曼编码,如上图,则哈夫曼编码的WPL= 1*3 + 2*3 + 3*2 + 3*2 + 4 *2 = 29 。
例4:对原电文进行等长编码,则:
等长编码的WPL = 1*3 + 2*3 + 3*3 + 3*3 + 4*3 = 39
所以哈夫曼编码可以节省空间。
原电文AMCADEDDMCCAD翻译成01串后为:10001011011000111100101011011。
对方根据事先构造好的哈夫曼树编码表可以还原原电文。
每日练习
1、6个点a、b、c、d、e、f,权值分别为0.5、0.6、0.15、0.1、0.05、0.09,求PL= ( ),WPL=( )。
2、文章中只出现五个字母ABCDE,出现频率={6,2,1,2,5},求PL= ( ),WPL=( ),其中各个字母的哈夫曼编码为A( ),B( ),C( ),D( ),E( )。
3、最优前缀编码,也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码( )
A. (00,01,10,11) B. (0,1,00,11) C. (0,10,110,111) D. (1,01,000,001)