欢迎来到天天文库
浏览记录
ID:32179437
大小:562.26 KB
页数:25页
时间:2019-02-01
《zip压缩算法详细分析及解压实例解释》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、ZIP压缩算法详细分析及解压实例解释最近自己实现了一个ZIP压缩数据的解压程序,觉得有必要把ZIP压缩格式进行一下详细总结,数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据压缩,两者本质上没啥区别,在数学家看来,都是映射。一方面在进行通信的时候,有必要将待传输的数据进行压缩,以减少带宽需求;另一方面,计算机存储数据的时候,为了减少磁盘容量需求,也会将文件进行压缩,尽管现在的网络带宽越来越高,压缩已经不像90年代初那个时候那么迫切,但在很多场合下仍然需要,其中一个原因是压缩后的数据容量减小后,磁盘访问IO的时间也缩短,尽管压缩和
2、解压缩过程会消耗CPU资源,但是CPU计算资源增长得很快,但是磁盘IO资源却变化得很慢,比如目前主流的SATA硬盘仍然是7200转,如果把磁盘的IO压力转化到CPU上,总体上能够提升系统运行速度。压缩作为一种非常典型的技术,会应用到很多很多场合下,比如文件系统、数据库、消息传输、网页传输等等各类场合。尽管压缩里面会涉及到很多术语和技术,但无需担心,博主尽量将其描述得通俗易懂。另外,本文涉及的压缩算法非常主流并且十分精巧,理解了ZIP的压缩过程,对理解其它相关的压缩算法应该就比较容易了。 1、引子压缩可以分为无损压缩和有损压缩,有损,指的是压缩之后就无法完整还原原始信息,但是压缩率可以很高,
3、主要应用于视频、话音等数据的压缩,因为损失了一点信息,人是很难察觉的,或者说,也没必要那么清晰照样可以看可以听;无损压缩则用于文件等等必须完整还原信息的场合,ZIP自然就是一种无损压缩,在通信原理中介绍数据压缩的时候,往往是从信息论的角度出发,引出香农所定义的熵的概念,这方面的介绍实在太多,这里换一种思路,从最原始的思想出发,为了达到压缩的目的,需要怎么去设计算法。而ZIP为我们提供了相当好的案例。尽管我们不去探讨信息论里面那些复杂的概念,不过我们首先还是要从两位信息论大牛谈起。因为是他们奠基了今天大多数无损数据压缩的核心,包括ZIP、RAR、GZIP、GIF、PNG等等大部分无损压缩格式
4、。这两位大牛的名字分别是JacobZiv和AbrahamLempel,是两位以色列人,在1977年的时候发表了一篇论文《AUniversalAlgorithmforSequentialDataCompression》,从名字可以看出,这是一种通用压缩算法,所谓通用压缩算法,指的是这种压缩算法没有对数据的类型有什么限定。不过论文我觉得不用仔细看了,因为博主作为一名通信专业的PHD,看起来也焦头烂额,不过我们后面可以看到,它的思想还是很简单的,之所以看起来复杂,主要是因为IEEE的某些杂志就是这个特点,需要从数学上去证明,这种压缩算法到底有多优,比如针对一个各态历经的随机序列(不用追究什么叫各
5、态历经随机序列),经过这样的压缩算法后,是否可以接近信息论里面的极限(也就是前面说的熵的概念)等等,不过在理解其思想之前,个人认为没必要深究这些东西,除非你要发论文。这两位大牛提出的这个算法称为LZ77,两位大牛过了一年又提了一个类似的算法,称为LZ78,思想类似,ZIP这个算法就是基于LZ77的思想演变过来的,但ZIP对LZ77编码之后的结果又继续进行压缩,直到难以压缩为止。除了LZ77、LZ78,还有很多变种的算法,基本都以LZ开头,如LZW、LZO、LZMA、LZSS、LZR、LZB、LZH、LZC、LZT、LZMW、LZJ、LZFG等等,非常多,LZW也比较流行,GIF那个动画格式
6、记得用了LZW。我也写过解码程序,以后有时间可以再写一篇,但感觉跟LZ77这些类似,写的必要性不大。ZIP的作者是一个叫PhilKatz的人,这个人算是开源界的一个具有悲剧色彩的传奇人物。虽然二三十年前,开源这个词还没有现在这样风起云涌,但是总有一些具有黑客精神的牛人,内心里面充满了自由,无论他处于哪个时代。PhilKatz这个人是个牛逼程序员,成名于DOS时代,我个人也没有经历过那个时代,我是从Windows98开始接触电脑的,只是从书籍中得知,那个时代网速很慢,拨号使用的是只有几十Kb(比特不是字节)的猫,56Kb实际上是这种猫的最高速度,在ADSL出现之后,这种技术被迅速淘汰。当时记
7、录文件的也是硬盘,但是在电脑之间拷贝文件的是软盘,这个东西我大一还用过,最高容量记得是1.44MB,这还是200X年的软盘,以前的软盘容量具体多大就不知道了,PhilKatz上网的时候还不到1990年,WWW实际上就没出现,浏览器当然是没有的,当时上网干嘛呢?基本就是类似于网管敲各种命令,这样实际上也可以聊天、上论坛不是吗,传个文件不压缩的话肯定死慢死慢的,所以压缩在那个时代很重要。当时有个商业公司提供了一种称为ARC的
此文档下载收益归作者所有