首页 > 其他 > 详细

浅谈哈夫曼编码

时间:2018-10-09 23:32:33      阅读:450      评论:0      收藏:0      [点我收藏+]

做NOIP初赛遇到了,还是填个坑吧


首先,哈夫曼编码是哈夫曼树的应用,不知道什么是哈夫曼树的可以搜一下

具体操作:

(1)我们有一个集合,集合里有一些数,升序排列

(2)每次选出两个最小的数,然后合并,删除,把新生成的数放到集合里

(3)重复步骤2,直到用完所有的数,树也就建好了,然后把左儿子定为0,右儿子定为1

(4)每个元素的哈夫曼编码就是其路径上的数


这样说可能不太明白,我们还是举个例子

现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由
4 个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为 700、600、300、
400。那么,“也”字的编码长度可能是( )。
A. 1 B. 2 C. 3 D. 4

这是NOIP2011提高组初赛的多选

正确答案是BC

我们只举一个来说,另一个就显而易见了

首先集合里有四个数{300,400,600,700}

先取两个300,400

合并,300+400=700

如图

技术分享图片

 

然后放入集合,此时{600,700,700}

取600和我们刚才合并出来的700

技术分享图片

然后是700和700

技术分享图片

树就建好了

然后是标号:

技术分享图片

一一对应,我们得到“也”:111        长度为3

保险起见,我把另一个图画一下:(其实就是把合并的顺序改变一下)

技术分享图片

此时  “也”:01    长度为2

这同时也说明了,在集合中有重复的数时,哈夫曼编码不止一种。

希望对大家有帮助

浅谈哈夫曼编码

原文:https://www.cnblogs.com/WWHHTT/p/9763804.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!