ZIP压缩算法详细分析与解压实例解释.docx

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