侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

压缩算法的基础(上):赫夫曼树及其构建

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 110 阅读 / 953 字

我们日常使用压缩和解压软件的频率可谓是非常高,而最基本的压缩算法 —— 赫夫曼编码,其中使用的二叉树就是赫夫曼树。在介绍赫夫曼编码之前,我们先来介绍赫夫曼树。

什么是赫夫曼树

我们通过一个例子来引入什么是赫夫曼树。

我们在中小学每年期末考试结束后都会领到成绩单,成绩单上列出我们考试分数的等级,比如优秀(>=90)、良好(>=80)、合格(>=60)、不合格(<60),以某个班为例,总人数是100人,不同成绩区间的比例如下:

1.png

不考虑效率因素的话,我们可以这么实现成绩等级判定:

1.png

这种情况下,比例占80%以上的分数都需要经历三次以上的判断才能得到结果,显然不合理,对此,我们可以对判断逻辑进行改进:

1.png

大部分同学的成绩都在 80 分左右,因此我们判断的逻辑改成了先通过 80 分对成绩进行划分,看起来效率是提升了,这其中的原理是每个分数都要循环调用此逻辑,将 80 分放到入口判断,总体判断次数更少,效率更高。

这就是赫夫曼树的雏形。显然,上述流程图可以抽象为一棵二叉树,每个等级的人数看作路径权重,我们把带权路径长度(权重x路径求和)最小的树叫做赫夫曼树,把上面两个流程图抽象为带路径权重的二叉树如下:

1.png

二叉树 a 的带权路径长度是 1*5+2*15+3*40+4*30+4*10 = 315,二叉树 b 的带权路径长度是 2*40+3*5+15*3+2*30+10*2 = 220,这意味着,对于人数 100 的班级,通过第一种方式要做 315 次比较,对于第二种方式,只需要 220 次比较,显然二叉树 b 比二叉树 a 更优。

赫夫曼树的构建

当然,上述二叉树 b 还不是赫夫曼树,因为它不是最优的,赫夫曼树的构造方式如下:

  1. 把有权值的节点按照从小到大顺序进行排序:A5、E10、B15、D30、C40;
  2. 取最小的两个节点作为某个新节点 N1 的子节点,较小的作为左子结点;
  3. 然后将 N1 替代 A5 和 E10,插入上述有序序列,保持从小到大排序:N115、B15、D30、C40;
  4. 重复步骤2,将 N1 和 B 作为一个新节点 N2 的左右节点,依次类推,直到把所有节点纳入树中。

最终形成的二叉树如下所示:

1.png

对应的带权路径长度是 1*40+2*30+3*15+4*5+4*10 = 205,对于 100 个学生而言,需要进行 205 次判断。比前面的二叉树 b 更优,同时也是最优的二叉树,所以是赫夫曼树。

0

评论区