简述

压缩可分为无损压缩和有损压缩。有损是指压缩后不能完全恢复原始信息，但压缩率可以很高，主要用于视频、语音等数据的压缩，因为人们很难察觉到一点信息的损失，或者不需要那么清晰，仍然可以观看和收听；当文件和其他信息必须完全恢复时，使用无损压缩。ZIP自然是一种无损压缩。在《通信原理》中介绍数据压缩时，常常从信息论的角度引入香农的熵的概念。这方面的介绍太多了。这里要换个思路，如何设计算法才能达到压缩的目的。ZIP为我们提供了一个非常好的案例。

原理

在计算机数据中有两种形式的重复，zip压缩这两种重复。

一种是短语形式的重复，即三个字节以上的重复。对于这种重复，zip使用两个数字：1。重复位置和当前压缩位置之间的距离；2.重复的长度，来表示这个重复，假设这两个数各占一个字节，所以数据被压缩。

第二种重复是单字节重复，一个字节只有256个可能值，所以这种重复是不可避免的。其中，有些字节可能出现的次数较多，有些则较少，在统计上趋于不均匀分布，这很容易理解。例如，在一个ASCII文本文件中，有些符号可能很少使用，而字母和数字使用较多，每个字母的使用频率也不一样。据说字母E的使用概率最高；很多图片或暗或亮，暗(或亮)像素使用较多(这里顺便说一下：png图片格式是一种无损压缩，其核心算法是zip算法，与zip格式的文件主要区别在于，作为一种图片格式，它存储了图片的大小、文件头使用的颜色数量等信息)；上述短语压缩的结果也有这种趋势：重复往往出现在当前压缩位置附近，重复长度往往更短(20字节以内)。这样就可以压缩：重新编码256种字节，使出现较多的字节用较短的码，出现较少的字节用较长的码。这样，当较短的字节比较长的字节多的时候，文件的总长度就会减少，字节使用率越不均匀，压缩比就会越大。

实例

ZIP: CL序列再压缩CL的方法表示一系列整数对应的码字长度。对于literal/length，从0到285总共有这么多符号，所以这个序列的长度是286，每个符号都有一个码字长度。当然，里面可能会有一大段连续的零，因为有些字符或长度是不存在的，尤其是英文文本编码时，非ascii字符根本不会存在。类似地，对于距离，也可能有一大段0。然后PK先把旅程编码了。在说什么是游程编码之前，先说一下PK对CL序列的理解。

文字/长度有286个编码符号，距离有30个编码符号，所以这个码树不会特别深，霍夫曼编码后的码字长度也不会特别长。PK认为最大长度不会超过15，也就是树的深度不会超过15。我没有分析这是否是一个理论证明。有兴趣的同学可以分析一下。因此，序列CL1和CL2的任意整数值的范围是0-15。0表示不出现整数。

什么是旅游？是一系列完全相同的数字。什么是游程编码？原理比较简单，就是对于一个连续的数，记录这个数一次，然后记录出现了多少次。大卫的书中给出了这个例子。例如，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，6，16，11(二进制)，16，00(二进制)，17，011(二进制)，2，16，00(二进制)

这是什么意思？因为CL的范围是0-15，PK认为太短，不能重复两次，所以游程长度从3开始。特殊数字16表示有3、4、5和6次这样的运行，后面分别是00、01、10和11。所以4，4，4，4，4，这个运行记录就是4，16，01，也就是说数字4会连续出现四次。6，16，11，16，00表示6后面是6个连续的6，然后是3个6；因为可能有很多连续的零，所以用两个特殊的数字17和18来表示零游程，17后面是三位，分别记录长度为3-10的游程。18后跟7位表示11-138的游程。17011表示连续出现6个零；18，0111110表示连续出现62个零。总之，记住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使用第三个霍夫曼码表对这两个序列进行编码。通过统计每个整数出现的次数，按照同样的思路对SQ1和SQ2进行霍夫曼编码，得到的码流记为SQ1bits和SQ2bits。同时，这里需要记录第三个码表，称为霍夫曼码表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的方法可能就体现出优势了。不得不说，对一个算法或者数据结构的优化程度，简直完全取决于程序员对那个东西细节的理解的深度。