一、基本概念
1.1带权路径长度(WPL)
路径长度: 经历的边数
结点的带权路径长度: 从树的根到该结点的路径长度 X 该结点上权值。
举例帮助理解
图中结点A的带权路径长度为:
3
×
5
=
15
3\times5=15
3×5=15
图中结点D的带权路径长度为:
2
×
2
=
4
2\times 2=4
2×2=4
1.2哈夫曼树
树的带权路径长度: 所有叶子结点的带权路径长度之和
哈夫曼树: 在含n个带权结点的二叉树中,带权路径最小的二叉树,又称最优二叉树
【注意】:哈夫曼树是最小带权二叉树,此处指树的带权路径长度(所有叶子结点WPL之和)
二、哈夫曼树的构造
给定n个权值分别为 w 1 , w 2 , w 3 , . . . , w n w_1,w_2,w_3,...,w_n w1,w2,w3,...,wn的结点,构造哈夫曼树的算法描述如下:
- 每次从结点集合中选择最小的两个结点,作为新结点的左右子树。
- 新结点的权值为被选出的两个结点权值之和。
- 删除旧的两个结点,将新结点加入集合
- 重复123步骤,直至集合中只剩一个结点
举例帮助理解:
至此,哈夫曼树构造完毕
W
P
L
=
7
∗
1
+
3
∗
(
1
+
2
+
2
+
3
)
=
31
WPL=7*1+3*(1+2+2+3)=31
WPL=7∗1+3∗(1+2+2+3)=31
三、哈夫曼树的应用
3.1哈夫曼编码与前缀编码
笔者在学习过程中,一直不明白,为什么哈夫曼树中,最小带权路径长度,是指所有叶子结点的WPL之和。也就是说,a,b,c,d都只能为叶子结点。
在此篇文章的案例中给出了答案。
可变长度编码: 允许对不同字符用不等长的二进制位表示
为了使编码的长度更短,进行可变长度编码,频率越高的码,对应的位数越少。根据我们所学的知识,可用哈夫曼树来解决。
举例帮助理解
学霸小甲答应告诉学渣小乙考试答案。他们决定用二进制编码来防止老师发现。
已知:C的出现频率为40%,A为30%,B为20%,D为10%
这里给出了答案。
对同一答案CAAABD
正确的哈夫曼编码应该为
0101010111110
而错误的哈夫曼编码为
01111110
只用肉眼看,是看不出问题在哪里的。一个合格的编码唯一对应一个答案。那么我们就从得到的编码逆向推导答案。
01111110得到的答案不唯一
0 11 11 11 0 = C B B B C??
0 1 1 1 1 1 1 0 = C A A A A A A C??
在读到A时,哈夫曼树仍可往下读得到B,D。(B,D的编码包含A)
因此,无法判断一个答案的范围。
0101010111110得到的答案唯一
0 10 10 10 111 110
= C A A A B D
而在正确编码中,读到A/B/C/D时,均为叶子结点,哈夫曼树不可往下读。也就实现了自动截断。文章来源:https://www.toymoban.com/news/detail-755561.html
总结如上,要使编码之间不冲突,则编码之间是互相独立的,没有一个编码是另一个编码的前缀。这样的编码称之为前缀编码
哈夫曼编码就是一种前缀编码文章来源地址https://www.toymoban.com/news/detail-755561.html
到了这里,关于哈夫曼树、带权路径长度、前缀编码 的概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!