



全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据是怎么被压缩的压缩软件大家想必都不不陌生。甚至是太熟悉而忽略了它的神奇。你有想过为什么压缩软件能把一组数据的体积缩小,并且还能再完整地展开还原吗?多余的体积究竟被藏在了哪里?下面就进来马上解析一哈!首先来看看什么是压缩。打一个比方,当你有天走在路上,碰见熟人对你说:“吃了?”你一定知道他是在打招呼,既不是要请客也不是让你“没吃赶紧回家吃去”。这一句简单的“吃了”是礼貌和问好的体现,也是一种信息的压缩。笼统地说,把一系列已有信息通过一定方法处理,使得其长度缩短,并且信息含量基本或者完全不变,就称之为压缩。在计算机上的压缩过程我们都知道,计算机采用的是2进制系统。一个连续的n位二进制数集,就可以用来表示 2 n 个字符。目前的国际标准是ASCII码:用一个字节即8位数的2进制码,来表示各种字符和字母。现在我们只使用2位二进制码,来简单地演示由4个符号组成的字符串的压缩过程。假设我们有这么一串20个字母的数据:默认情况下,用2位2进制码来表示这四个字母:ABCD00011011每个字符在字符串中各自出现的次数并不相等:A:6次 B:10次 C:3次 D:1次而在计算机中,数据则是以2进制码的形式储存在硬盘上的:00 00 01 00 00 01 01 10 01 00 01 01 01 10 01 01 00 01 11 10压缩过程如下:注明每个字符的出现次数。把两个出现次数最小的字符圈到一起,看作一个新字符,新字符的次数为两个组成字符的次数之和。重复上述操作,直至完成对所有字符的处理。这种操作形成的结构看起来像棵树(如图所示),被称为霍夫曼(Huffman)树。在每一层的分支线上,按下图所示分别标上0和1。从最顶端往下读,每个字符都有唯一的分支编号连到它那里,无重复也无遗漏,这样就得到了ABCD这四个字符的新的代码:ABCD100110111用以上新编码代入原字符串中,得到:10 10 0 10 10 0 0 110 0 10 0 0 0 110 0 0 10 0 111 110整理一下得到新编码:原编码:0000010000010110010001010110010100011110新编码:1010010100011001000011000100111110看!数据成功被压缩。这一段40位长度的内容被压缩到了34位,压缩率是85%。回顾过程容易发现压缩的秘密:出现频率最多的B由一位二进制码“0”来表示,而出现频率较低的C和D,则由长度增加了的三位二进制码来表示。通过合理分配不同长度的编码,肯定可以对数据进行一定程度的压缩。另外可以证明,霍夫曼树就是此类编码替代的最优化的方案之一。因为假如存在一个字符的出现频率高于另一个字符,而它的变长码长度却长于另一个字符,那么必然可以通过交换两者的位置,使得输出结果的总长度变短。有限次操作后可以达到无法再交换的情况,也就是霍夫曼树规则下的情况。进一步思考几个问题在压缩文件的时候,人们不禁会产生一些新想法或者遇到一些疑问:是否可以对压缩后的数据再次压缩?当2 n 的n变大后,遇到A:1010,B:10这样的情况,如何解读10101010?就操作上来说,当然能反复编码,但通过对本文例子中得到的新编码再次操作后会发现,结果是不会有任何变化的。压缩的实质,在于消除特定字符分布上的不均衡,通过将短码分配给高频字符,而长码对应低频字符实现长度上的优化。而数据经过一次压缩后,字符的分布已经几乎平均化了,很难更进一步的压缩了。而第二个问题描述的情况是不会出现的的。从构造霍夫曼树操作上可以看到,一个字符无法在另一个字符的上层。只要操作正确,就一定可以构造出唯一的代码表,不存在歧义。还有一个有趣的问题是:虽然把40字节的内容压缩到了34字节,但需要将相应的码表一并发送给接收方(没有对应码表,无法解压)。这不反而使得压缩后的数据比压缩前的还要长?事实也确实如此。本文例子中,真正的最终结果体积是大于原文的。但这不意味了算法错误。这是因为“n”过小(例子中为2,实际通常为8)导致的。总长度的不够使得节省出来的那部分容量还不足以弥补码表本身的储存空间。实际应用中,如果你非要去压缩一个只有几个字节的文件,得到的压缩包也经常会大于文件本身。通常,压缩软件会在每压缩4kb到32kb数据后,重新生成并保存一个霍夫曼树。当分块过大时,统计上的整体平均,会掩盖小区域内的极度不平均,损失了压缩的空间。比如存在一个这样的文件:AAAAAAAAAA(一万个)BBBBBBBBBB(一万个)ZZZZ(一万个)。如果从整体上进行霍夫曼树操作,将不会产生任何压缩,但是这时候我们把它分成26块,压缩并各自保存相应的重新编码的霍夫曼树,压缩率将非常惊人,约等于12.5%。英语中各字母出现频率示意图通过上面字频图我们知道,在一般文本中,英语字母使用
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 建设工程扬尘污染防治工作方案及计划
- 爆米花逃跑课件
- 2月失智老年人模拟考试题(附答案)
- 焚风效应课件
- 解析卷人教版八年级上册物理声现象《声音的产生与传播》专题测试试题(详解)
- 考点解析人教版八年级上册物理声现象《声音的特性声的利用》专项训练试卷(含答案详解)
- 难点解析人教版八年级上册物理《声现象》同步练习试题(含答案解析)
- 2025及未来5年中国千斤顶密封件市场调查、数据监测研究报告
- 2025及未来5年中国桶装吸汗带市场调查、数据监测研究报告
- 2025年中国三水磷酸钾市场调查研究报告
- 2025道路运输安全员两类人员考试考核题库含答案全套
- 发生特种设备安全事故应急预案模版(4篇)
- 宗春山安全第一课
- 放射性皮肤损伤的护理-中华护理学会团体标准
- 三度房室传导阻滞护理查房
- 五年级科学上册(教科版)第2.5课风的作用教学设计
- 沪教牛津版九年级英语下册单词表默写版
- 浙江路桥中国日用品商城股份有限公司招聘笔试题库2024
- 动物检疫员技能竞赛(理论部分)复习内容
- 2024年秋新人教版七年级上册历史教学课件 第8课 夏商周时期的科技与文化
- 2024年中煤第七十一工程处有限责任公司招聘笔试冲刺题(带答案解析)
评论
0/150
提交评论