压缩可以分为无损压缩和有损压缩，有损，指的是压缩之后就无法完整还原原始信息，但是压缩率可以很高，主要应用于视频、话音等数据的压缩，因为损失了一点信息，人是很难察觉的，或者说，也没必要那么清晰照样可以看可以听；无损压缩则用于文件等等必须完整还原信息的场合，ZIP自然就是一种无损压缩，在通信原理中介绍数据压缩的时候，往往是从信息论的角度出发，引出香农所定义的熵的概念，这方面的介绍实在太多，这里换一种思路，从最原始的思想出发，为了达到压缩的目的，需要怎么去设计算法。而ZIP为我们提供了相当好的案例。
有两种形式的重复存在于计算机数据中，zip 就是对这两种重复进行了压缩。
一种是短语形式的重复短语形式的重复，即三个字节以上的重复，对于这种重复，zip用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩。
第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。其中，某些字节出现次数可能较多，另一些则较少，在统计上有分布不均匀的倾向，这是容易理解的，比如一个 ASCII 文本文件中，某些符号可能很少用到，而字母和数字则使用较多，各字母的使用频率也是不一样的，据说字母 e 的使用概率最高；许多图片呈现深色调或浅色调，深色（或浅色）的像素使用较多（这里顺便提一下：png 图片格式是一种无损压缩，其核心算法就是 zip 算法，它和 zip 格式的文件的主要区别在于：作为一种图片格式，它在文件头处存放了图片的大小、使用的颜色数等信息）；上面提到的短语式压缩的结果也有这种倾向：重复倾向于出现在离当前压缩位置较近的地方，重复长度倾向于比较短（20字节以内）。这样，就有了压缩的可能：给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。
实例- ZIP中对CL进行再次压缩的方法
CL序列表示一系列整数对应的码字长度，对于literal/length来说，总共有0-285这么多符号，所以这个序列长度为286，每个符号都有一个码字长度，当然，这里面可能会出现大段连续的0，因为某些字符或长度不存在，尤其是对英文文本编码的时候，非ASCII字符就根本不会出现，length较大的值出现概率也很小，所以出现大段的0是很正常的；对于distance也类似，也可能出现大段的0。PK于是先进行了一下游程编码。在说什么是游程编码之前，我们谈谈PK对CL序列的认识。
literal/length的编码符号总共286个，distance的编码符号总共30个，所以这颗码树不会特别深，Huffman编码后的码字长度不会特别长，PK认为最长不会超过15，也就是树的深度不会超过15，这个是否是理论证明我还没有分析，有兴趣的同学可以分析一下。因此，CL1和CL2这两个序列的任意整数值的范围是0-15。0表示某个整数没有出现。
什么叫游程呢？就是一段完全相同的数的序列。什么叫游程编码呢？说起来原理更简单，就是对一段连续相同的数，记录这个数一次，紧接着记录出现了多少个即可。David的书中举了这个例子，比如CL序列如下：
4, 4, 4, 4, 4, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2
那么，游程编码的结果为：
4, 16, 01（二进制）, 3, 3, 3, 6, 16, 11（二进制）, 16, 00（二进制）, 17,011（二进制）, 2, 16, 00（二进制）
这是什么意思呢？因为CL的范围是0-15，PK认为重复出现2次太短就不用游程编码了，所以游程长度从3开始。用16这个特殊的数表示重复出现3、4、5、6个这样一个游程，分别后面跟着00、01、10、11表示。于是4,4,4,4,4,这段游程记录为4,16,01，也就是说，4这个数，后面还会连续出现了4次。6,16,11,16,00表示6后面还连续跟着6个6，再跟着3个6；因为连续的0出现的可能很多，所以用17、18这两个特殊的数专门表示0游程，17后面跟着3个比特分别记录长度为3-10的游程；18后面跟着7个比特表示11-138的游程。17,011表示连续出现6个0；18,0111110表示连续出现62个0。总之记住，0-15是CL可能出现的值，16表示除了0以外的其它游程；17、18表示0游程。因为二进制实际上也是个整数，所以上面的序列用整数表示为：
4, 16, 1, 3, 3, 3, 6, 16, 3, 16, 0, 17, 3, 2, 16, 0
我们又看到了一串整数，这串整数的值的范围是0-18。这个序列称为SQ。因为有两个CL1、CL2，所以对应的有两个SQ1、SQ2。
针对SQ1、SQ2，PK用了第三个Huffman码表来对这两个序列进行编码。通过统计各个整数的出现次数，按照相同的思路，对SQ1和SQ2进行了Huffman编码，得到的码流记为SQ1 bits和SQ2 bits。同时，这里又需要记录第三个码表，称为Huffman码表3。同理，这个码表也用相同的方法记录，也等效为一个码长序列，称为CCL，因为至多有0-18个，PK认为树的深度至多为7，于是CCL的范围是0-7。
当得到了CCL序列后，PK决定不再折腾，对这个序列用普通的3比特定长编码记录下来即可，即000代表0,111代表7。但实际上还有一点小折腾，就是最后这个序列如果全部记录，那就需要19*3=57个比特，PK认为CL序列里面CL范围为0-15，特殊的几个值是16、17、18，如果把CCL序列位置置换一下，把16、17、18这些放前面，那么这个CCL序列就很可能最后面跟着一串0，所以最后还引入了一个置换，其示意图如下，分别表示置换前的CCL序列和置换后的CCL。可以看出，16、17、18对应的CCL被放到了前面，这样如果尾部出现了一些0，就只需要记录CCL长度即可，后面的0不记录。可以继续节省一些比特，不过这个例子尾部置换后只有1个0：
不过粗看起来，这个置换效果并不好，我一开始接触这个置换的时候，我觉得应该按照16、17、18、0、1、2、3、。。。这样的顺序来存储，如果按照我理解的，那么置换后的结果如下：
2、4、0、4、5、5、1、5、0、6、0、0、0、0、0、0、0、0、0
这样后面的一大串0直接截断，比PK的方法更短。但PK却按照上面的顺序。我总是认为，我觉得牛人可能出错了的时候，往往是我自己错了，所以我又仔细想了一下，上面的顺序特点比较明显，直观上看，PK认为CL为0和中间的值出现得比较多，但CL比较小的和比较大的出现得比较少，在文件比较小的时候，这种方法效果不算好，上面就是一个典型的例子，但文件比较大了以后，CL1、CL2码树比较大，码字长度普遍比较长，大部分很可能接近于中间值，那么这个时候PK的方法可能就体现出优势了。不得不说，对一个算法或者数据结构的优化程度，简直完全取决于程序员对那个东西细节的理解的深度。
,
