当前位置:   article > 正文

数据结构(36)哈夫曼树和哈夫曼编码_构造哈夫曼树和生成哈夫曼编码

构造哈夫曼树和生成哈夫曼编码

目录

1、哈夫曼树的定义

2、哈夫曼树的构造

3、哈夫曼编码


1、哈夫曼树的定义

在许多应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的权。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为

式中,Wi是第i个叶结点所带的权值,Li是该叶结点到根节点的路径长度。

在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树。例如,图36-1中的3棵二叉树都有4个叶子结点a,b,c,d,分别带权7,5,2,4,他们带权路径长度分别为

                                       图36-1  具有不同带权长度的二叉树

(a)WPL = 7*2 + 5*2 + 2*2 + 4*2 = 36。

(b)WPL = 4*2 + 7*3 + 5*3 + 2*1 = 46;

(c)WPL = 7× I + 5× 2+2× 3 + 4× 3 = 35。

其中,图36-1(c)树的WPL最小。可以验证,它恰好为哈夫曼树。

2、哈夫曼树的构造

给定n个权值分别为W1,W2,...,Wn的结点,构造哈夫曼树的算法描述如下:

1)将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F。

2)构造一个新结点,从F中选取两棵根节点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根节点的权值之和。

3)从F中删除刚才选出的两棵树,同时将新得到的树加入F中。

4)重复步骤2、3,直至F中止剩下一棵树为止。

                     图36-2  哈夫曼树的构造过程

从上述构造过程中可以看出哈夫曼树具有如下特点:

1)每个初始结点最终都成为叶结点,且权值越小的结点到根节点的路径越长。

2)构造过程中共新建了n-1个新结点(双分支结点),因此哈夫曼树的结点总数为2n-1。

3)每次构造都选择2棵树作为新结点的孩子,因此哈夫曼树中不存在度为1的结点。

3、哈夫曼编码

在数据通信中,若对每个字符用相等长度的二进制位表示,称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示,则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好很多,其特点是对频率高的字符赋以短编码,而对频率较低的字符赋以较长一些的编码,从而可以使字符的平均编码长度减短,起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。举例:设计字符A,B和C的对应的编码0,101,100是前缀编码。对前缀编码的解码很简单,因为没有一个编码是其他编码的前缀。所以识别出第一个个编码,将它翻译为原码,再对余下的编码文件重复同样的解码操作。例如,码串00101100可被唯一地翻译为0,0,101,100。另举反例:如果再将字符D的编码设计为00,此时0是00的前缀,码串00101100的前两位就无法唯一翻译。

由哈夫曼树得到哈夫曼编码是很自然的过程。首先,将每个出现的字符当做一个独立的结点,其权值为它出现的频度(或次数),构造出对应的哈夫曼树。显然,所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列,其中边标记为0的表示“转向左孩子”,标记为1的表示“转向右孩子”。图36-3所示为一个由哈夫曼树构造哈夫曼编码的实例,矩形方块表示字符及其出现的次数。

这课哈夫曼树的WPL为:1*45+3*(13+12+16)+4*(5+9) = 224.

此处的WPL可视为最终编码得到二进制编码的长度,共224位。若采用3位固定长度编码,则需要300位。

注意:0和1表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但各哈夫曼树的带权路径长度WPL相同且为最优。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/859286
推荐阅读
相关标签
  

闽ICP备14008679号