首页 > 编程语言 > 详细

ZIP压缩算法详细分析及解压实例解释

时间:2019-01-07 10:55:59      阅读:6652      评论:0      收藏:0      [点我收藏+]

标签:time   des   传输   大致   一点   arch   算法复杂度   多个   decrypt   

最近自己实现了一个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。我也写过解