带权树 -- 哈夫曼树,与它的那张哈夫曼编码表

举报
看,未来 发表于 2020/12/30 01:42:25 2020/12/30
【摘要】 首先我们来看一段代码: ··· if(a<60){···} else if(60<=a && a<70){···} else if(70<=a && a<80){···} else if(80<=a && a<90){···} else{···} ··· 12345678 现在假设a处于0~60的概率为0.1 60~70:0.3 70~80:0.4 80~90:0...

首先我们来看一段代码:

···

if(a<60){···}
else if(60<=a && a<70){···}
else if(70<=a && a<80){···}
else if(80<=a && a<90){···}
else{···}
···

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

现在假设a处于0~60的概率为0.1
60~70:0.3
70~80:0.4
80~90:0.15
大于90:0.05

现在来看看上面那个算法,数据量小的时候自然看不出什么,但是数据量一旦大起来呢?
每次都要经过一堆的判断,明知最上面那个判断发生可能性又不大,岂不是浪费!


在来看个栗子:

对于a、b、c三个字符进行编码,普通情况下将a编成001,b编成010,c编成100,
现在发个aaabbc,那么就是001001001010010100,老长了,18个数。
如果换个思路,将a:11,b:011,c:0010(编码之间不能出现前缀冲撞,譬如把b编成001那等下就和c分不清楚了)。这样子的话刚才那串字符串就可以写成这样:1111110110110010,16个数。字符串一长这空间省下来那就很可观了。

具体怎么可观,有压缩过资源包的都明白。

哈夫曼树

先来看几个概念:
在这里插入图片描述
这是一个带权二叉树的图。

这棵树的路径长度 = 5+15+40+30+10 = 100.
这颗树的带权路径长度(WPL)= 51 + 152 + 403 +304 + 10*4 = 315

通过调整使得这棵树的WPL最小时,那棵树就是哈夫曼树。

这里要强调一下,哈夫曼树不是专门的搜索二叉树。你可以把哈夫曼树和密码学搭上边,因为你没有那个哈夫曼表是无法对一个被哈夫曼树加密(压缩)的文件进行解码的。

哈夫曼编码

这里要提一下哈夫曼编码表:
哈夫曼树当然是一种树,不过这种树有些特殊之处。哈夫曼编码呢,是根据哈夫曼树规则生成的编码!提供一个字符,根据哈夫曼编码规则,你会得到一个哈夫曼编码,不过你提供的字符必须在哈夫曼编码表中有对应的编码才行。

一般常见的编码方式:从根节点开始,向左遍历记为0,向右遍历记为1,遍历到某个字符的过程量即为其编码(这是一种方式而已),对于上面的图来说,编码方式为(虽然它不是哈夫曼树,但是举个例子嘛,物尽其用):

A 0
B 10
C 110
D 1110
E 11110

编码的最重要的原则就是前缀不能有冲撞,你看上面这几个码,没碰着吧。

哈夫曼树构造步骤

根据给定的n个权值{W1,W2,…,Wn}构成n棵二叉的集合F={T1,T2,…Tn},其中每棵二叉树Ti只有一个带权为Wi的根结点,其左右子树均为空。
在F中选取2棵根结点最小的树 作为左右子树 构造一棵新的二叉树,且新的二叉树的根结点左右子树根结点权值之和。
在F中删除这2棵子树,同时将新得到的二叉树加入F中。
重复2和3步骤,直到F只含一棵树为止,这棵树便是哈夫曼树。

代码

这里先贴一份别人的,我复习完数据结构之后会去刷题并手写这些代码。
代码还是要自己写的,书上得来终觉浅。
很完整的一套代码

文章来源: lion-wu.blog.csdn.net,作者:看,未来,版权归原作者所有,如需转载,请联系作者。

原文链接:lion-wu.blog.csdn.net/article/details/105606612

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。