首页 > 编程语言 >6.6 夫曼算法能够大幅提升压缩比率

6.6 夫曼算法能够大幅提升压缩比率

时间:2023-02-11 20:55:39浏览次数:34  
标签:字节 哈夫曼 压缩 6.6 算法 17 数据 夫曼

通过图6-5的步骤2可以发现,在用枝条连接数据时,我们是从出现频率较低的数据开始的,这就意味着出现频率越低的数据到达根部的枝条数就越多。而枝条数越多,编码的位数也就随之增多了。

使用哈夫曼树后,出现频率越高的数据所占用的数据位数就越少,而且数据的区分也可以很清晰地实现。

哈夫曼算法可以对数据进行区分的原因:用哈夫曼算法压缩过的文件中读取数据后,就会以位为单位对该数据进行排查,并与哈夫曼树进行比较看是否到达了目标编码。

例如,10001这个使用图6-5所示的哈夫曼编码作成的5位数据,到达100时,对照哈夫曼树的数据,该数据表示的是B这个字符。至此就找到了1个字符。然后再顺着哈夫曼树寻找剩下的01,会发现它表示的是E这个字符。
接下来,让我们来看一下哈夫曼算法的压缩比率。如下图:

得到的哈夫曼编码表示AAAAAABBCDDEEEEEF,结果为0000000000001001001101011010101010101111,40位=5字节(这里为不包含哈夫曼编码信息的情况)。压缩前的数据是17字符=17字节,也就是说,我们惊奇地得到了5字节÷17字节=29%这样高的压缩率。表6-4是将表6-1中的文件应用哈夫曼算法的LHA进行压缩后的结果。可以看出,不管是哪种类型的文件,都得到了很高的压缩比率。

标签:字节,哈夫曼,压缩,6.6,算法,17,数据,夫曼
From: https://www.cnblogs.com/ttmeng/p/17112537.html

相关文章

  • 6.5 用二叉树实现哈夫曼编码
    莫尔斯编码是根据日常文本中各字符的出现频率来决定表示各字符的编码的数据长度的。不过,该编码体系,对AAAAAABBCDDEEEEEF这样的特殊文本并不是最适合的。在莫尔斯编码中,E的......
  • 代码随想录算法训练营第二十三天|LeetCode 669. 修剪二叉搜索树 、LeetCode 108.将有
    669.修剪二叉搜索树文章:代码随想录(programmercarl.com)视频:你修剪的方式不对,我来给你纠正一下!|LeetCode:669.修剪二叉搜索树_哔哩哔哩_bilibili思路:从图中可以看出......
  • 算法刷题-四数之和、缺失的第一个正数、N 皇后
    四数之和给定一个包含n个整数的数组nums和一个目标值target,判断nums中是否存在四个元素a,b,c和d,使得a+b+c+d的值与target相等?找出所有满足条件且不重复......
  • 6.3 RLE算法的缺点
    在实际的文本文件中,同样字符多次重复出现的情况并不多见。虽然针对相同数据经常连续出现的图像、文件等,RLE算法可以发挥不错的效果,但它并不适合文本文件的压缩。不过,因为该......
  • 6.2 RLE算法的机制
    把文件内容用“数据×重复次数”的形式来表示的压缩方法称为RLE(RunLengthEncoding,行程长度编码)算法(图6-2) RLE算法是一种很好的压缩方法,经常被用于压缩传真的图像......
  • 从0到1一步一步玩转openEuler--11 openEuler基础配置-设置磁盘调度算法
    11openEuler基础配置-设置磁盘调度算法11.1设置磁盘调度算法本节介绍如何设置磁盘调度算法。11.1.1临时修改调度策略例如将所有IO调度算法修改为mq-deadline,此修改......
  • 算法题
    回文数给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数publicbooleanisPalindrome(intx)......
  • 代码随想录算法训练营第十一天【栈与队列】20.有效的括号、1047.删除字符串中的所有相
    20.有效的括号力扣题目链接心得:栈的经典题目,先进后出,有三种return false的情况。1)遍历字符串完成,但是栈不为空。说明左括号比右括号多,导致栈中多存了数据2)遍......
  • 菜鸟角度简单分析BP算法(Error Back Propagation)
    PS:要转载请注明出处,本人版权所有。PS:这个只是基于《我自己》的理解,如果和你的原则及想法相冲突,请谅解,勿喷。前置说明  本文作为本人csdnblog的主站的备份。(BlogID......
  • 路径规划的最优算法实现
    项目背景与简介在生活当中,我们经常面对了许多路径规划问题,通常会考虑下列几种因素:红绿灯多少,道路长短,车流量多少。一般都是应用程序在帮我们做出判断和选择,而我们减少了......