野兽'' 2019-07-21 674浏览量
哈夫曼树,又称最优二叉树,是一棵带权值路径长度(WPL,Weighted Path Length of Tree)最短的树,权值较大的节点离根更近。
首先介绍一下什么是 WPL,其定义是树的所有叶结点的带权路径长度之和,称为树的带权路径长度
,公式为 WPL = W1 L1 + W2 L2 + W3 L3 + ... + Wn Ln。
下面是个最简单且最直观的案例,通过实际案例能够更清晰的表示 WPL 和哈夫曼树。
百分制的成绩转换成五分制的成绩,伪代码如下:
if (score < 60) grade = 1;
else if (score < 70) grade = 2;
else if (score < 80) grade = 3;
else if (score < 90) grade = 4;
else grade = 5;
通过这个规则,可以生成一棵判定树,如下:
score < 60
/ \
grade = 1 score < 70
/ \
grade = 2 score < 80
/ \
grade = 3 score < 90
/ \
grade = 4 grade = 5
根据判定树可以看出:对于 60 分以下的分数,只需要一次就能够给出结果;对于 60~70 分的成绩,需要判断 2 次给出结果;对于 70~80 的成绩则需要判断 3 次,依次类推。
那么问题来了,绝大多数成绩处于 80~90 分,只有少数成绩处于 60 分以下及 90 分以上,那判断的次数是不是有点多呢?其中这个"绝大多数"和"少数"就是一个权值的概念了。
比如成绩分布如下:
| 成绩 | 0~59 | 60~70 | 70~80 | 80~90 | 90~100 |
| 比例 | 0.05 | 0.15 | 0.30 | 0.40 | 0.10 |
那么判断次数等于: WPL = 0.05 1 + 0.15 2 + 0.30 3 + 0.40 4 + 0.10 * 5 = 3.35
这里产生一个想法:假如把 80~90 的判断拿到最前面,不就能够减少大部分成绩的计算路径了吗?
修改后的判定树应该是这样的
score < 80
/ \
score < 70 score < 90
/ \ / \
score < 60 grade = 3 grade = 4 grade = 5
/ \
grade = 1 grade = 2
其判断次数等于:WPL = 0.40 2 + 0.30 2 + 0.10 2 + 0.15 3 + 0.05 * 3 = 2.2
通过上面的案例,就能够得出结论,哈夫曼树能够根据节点的查找频率来构造更有效的搜索树,是 WPL 最小的树。
哈夫曼树的构造可以理解为将权值最小的两棵二叉树合并,这个树的权值等于 2 个子树的和。
关于如何选取两个权值最小的二叉树,可以使用最小堆实现,复杂度是 O(N log N)。
比如权值:{1,2,3,4,5},可以得出:
15 // 输出 15
/ \
6 9 // 取出 4,5 ;输出 9,得出 {6,9}
/ \ / \
3 3 4 5 // 取出 3,3 ;输出 6,得出 {6,4,5}
/ \
1 2 // 取出 1,2 ;输出 3,得出 {3,3,4,5}
计算以下 WPL = 2 3 + 2 4 + 2 5 + 3 1 + 3 * 2 = 33
哈夫曼树的特点:
n 个叶子节点的哈夫曼树,总节点数为 2n-1
哈夫曼编码用于数据存储中做压缩,如下案例:
给定一段包含 50 个字符的字符串,由 {a,b,c,d,e,f}构成,且每个字符出现次数不同,会有如下几种存储方式。
第三种便可以使用哈夫曼树来实现,假如给定:
| 字符 | a | b | c | d | e | f |
| 次数 | 18 | 4 | 16 | 1 | 1 | 10 |
构成哈夫曼树:
50
0/ \1
a(18) 32
0/ \1
c(16) 16
0/ \1
6 f(10)
0/ \1
2 b(4)
0/ \1
d(1) e(1)
所以:a:0; b:1101; c:10; d:11000; e:11001; f:111 。
长度为:1 18 + 4 4 + 16 2 + 1 5 + 1 5 + 10 3 = 106 字符。
emmm... 大概就是这么个东西。好了,笔记写完了,继续学习...
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目