cisen
commented
4 years ago 压缩可以分为无损压缩和有损压缩，有损，指的是压缩之后就无法完整还原原始信息，但是压缩率可以很高，主要应用于视频、话音等数据的压缩，因为损失了一点信息，人是很难察觉的，或者说，也没必要那么清晰照样可以看可以听；无损压缩则用于文件等等必须完整还原信息的场合，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实际上就没出现，浏览器当然是没有的，当时上网干嘛呢？基本就是类似于网管敲各种命令，这样实际上也可以聊天、上论坛不是吗，传个文件不压缩的话肯定死慢死慢的，所以压缩在那个时代很重要。当时有个商业公司提供了一种称为ARC的压缩软件，可以让你在那个时代聊天更快，当然是要付费的，Phil Katz就感觉到不爽，于是写了一个PKARC，免费的，看名字知道是兼容ARC的，于是网友都用PKARC了，ARC那个公司自然就不爽，把哥们告上了法庭，说牵涉了知识产权等等，结果Phil Katz坐牢了。。。牛人就是牛人， 在牢里面冥思苦想，决定整一个超越ARC的牛逼算法出来，牢里面就是适合思考，用了两周就整出来的，称为PKZIP，不仅免费，而且这次还开源了，直接公布源代码，因为算法都不一样了，也就不涉及到知识产权了，于是ZIP流行开来，不过Phil Katz这个人没有从里面赚到一分钱，还是穷困潦倒，因为喝酒过多等众多原因，2000年的时候死在一个汽车旅馆里。英雄逝去，精神永存，现在我们用UE打开ZIP文件，我们能看到开头的两个字节就是PK两个字符的ASCII码。
总结