哈夫曼树的基本概念
哈夫曼树的定义是对一组具有确定权值的叶子节点,选出最小带权路径长度的二叉树为哈夫曼树(WPL最小),也称最优二叉树
哈夫曼算法的实现
注意:哈夫曼树在构造时选择两个最小的权值点,默认小的在左边大的在右边,但实际上并没有硬性规定,可以互换,对长度没有影响,但本文默认小的在左边大的在右边。
1.对权值节点排序,在n个权值节点中选出两个最小的,这两个节点作为左右子树形成一棵新的二叉树,根节点的值是左右子树权值的加和
2.将原序列中最小的两个权值删除,将新的权值加入到序列中(原最小两个权值的和),并排序
3.不断重复1和2步骤,直至只剩下一棵树**(结束的表示是序列只剩1个节点值)**,此树为所构造的哈夫曼树
下面用图说明哈夫曼树的构造过程,给定权值1 5 2 6 10 7,要求构造出哈夫曼树
初始状态为
1.将权值进行排序得到1 2 5 6 7 10,选出权值最小的两个节点分别是1和2,将1和2作为左右子树生成一棵二叉树,根节点值为3
2.将最小的两个节点(1,2删除),将节点3加入到序列中,此时序列为3 5 6 7 10,即
3.由于序列中的所有节点(剩余5个)大于1个,继续循环上述1和2过程,此时序列为3 5 6 7 10,将权值最小的两个节点3和5作为左右子树生成新的一棵二叉树,根节点为3+5=8
4.将3和5节点删除,将节点8加入到序列中,重新排序,此时序列为6 7 8 10,如下图
5.由于并没有消耗完序列中的所有节点(剩余4个)大于1个,继续循环上述1和2过程,此时序列为6 7 8 10,将权值最小的两个节点6和7作为左右子树生成新的一棵二叉树,根节点为6+7=13
6.将6和7节点删除,将节点13加入到序列中,重新排序,此时序列为8 10 13,如下图
7.由于序列中的所有节点(剩余3个)大于1个,继续循环上述1和2过程,此时序列为8 10 13,将权值最小的两个节点8和10作为左右子树生成新的一棵二叉树,根节点为8+10=18
8.将6和7节点删除,将节点18加入到序列中,重新排序,此时序列为13 18,如下图
9.由于序列中的所有节点(剩余2个)大于1个,继续循环上述1和2过程,此时序列为13 18,将权值最小的两个节点13和18作为左右子树生成新的一棵二叉树,根节点为13+18=31
10.将13和18节点删除,将节点31加入到序列中,此时序列为31,如下图
11.此时序列只剩1个元素,循环结束,所生成的树即为哈夫曼树。
哈夫曼编码
在通信传送时,数据表现为0和1的二进制形式。为了提高传输的速度,通常会进行数据压缩。同时,要保证编码不存在二义性。哈夫曼编码符合上述要求,能达到较优的编码方式,其原理就是自底向上构建哈夫曼树。
例:假设某报文由{‘l’,‘m’,‘y’,‘z’,‘j’,‘h’}六个字符组成,每个字符出现的频率分别是{0.24,0.16,0.2,0.08,0.02,0.3},为这6个字符设计哈夫曼编码
数据预处理
首先可以将字符出现的频率转换为整数,即每个概率乘100,得到相应权值
字符 | 权值 |
---|---|
l | 24 |
m | 16 |
y | 20 |
z | 8 |
j | 2 |
h | 30 |
构造哈夫曼树
此时l字符对应权值为24,m字符对应权值为16.等,得到6个节点的权值后,按照上文讲到的方法构造哈夫曼树(不断循环方式1和方式2直至只剩下一棵树),具体细节不再赘述。
生成的哈夫曼树如下:
按照哈夫曼编码的规则,每个根节点的左子树编码为0 每个根节点的右子树编码为1。
根据上述规则可以生成每个字符(即出现频率的节点 如l为24的节点为01)对应的编码文章来源:https://www.toymoban.com/news/detail-510574.html
字符 | 编码 |
---|---|
l | 01 |
m | 101 |
y | 00 |
z | 1001 |
j | 1000 |
h | 11 |
用哈夫曼编码得到的序列长度应为24 * 2+16 * 3 + 20 * 2 + 8 * 4 + 2 * 4 + 30 * 2 = 236
而利用等长编码由于字符数为6位,需要用3位二进制数表示,因此序列长度为300
可以看到哈夫曼编码的序列明显小于等长编码得到的序列,比例为236/300。文章来源地址https://www.toymoban.com/news/detail-510574.html
到了这里,关于哈夫曼树及哈夫曼编码(考试常考版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!