Gzip是如何压缩文件的

Gzip 是如何工作的

简介

Gzip使用deflate算法对数据流进行压缩，该算法分1-9一共9个压缩等级，等级越低压缩率越低压缩速度越快。下面使用默认的6级来来说明。Deflate算法该分为LZ77和霍夫曼编码两个部分：前者负责压缩，后者负责编码（其实编码和压缩是一个意思）这里使用字符串abcabcaaabaaa为例来描述算法的总体流程：Gzip首先使用LZ77算法来对该字符串做压缩，得到如下的LZZ编码串（括号和逗号只是为了方便理解，不包括在LZZ编码串内）：

1
abc(3,3)aaab(4,3)

这其中的abc就是表示直接把原来的abc复制过来，(4,3)表示从该位置前方4个字符开始往后的三个字符赋值到当前位置，也就是重复一次abc。在这样一个串中，称abc为未匹配的字符串字面量，简称字面量。(distance,length)称为一个有序匹配对，简称匹配对，其中distance表示距离，length表示匹配串的长度。

​

下面针对这两个部分做详细解释。

LZ77算法

在gzip的实现中，LZ77需要对一个串找最短匹配长度为3的匹配长度最长的匹配串（也就是最长的相同子串，但是要求最短长度为3）gzip使用数组实现了一个小型的哈希表，哈希的key是根据子串的前三个字符算出来的一个哈希值（这里为方便起见直接使用字符串本身作为哈希值），value是一个链，链中展示了所有以这个三个字符开始的字串的首字母下标位置，下标越大越排在前面。以

1
2
[a a b c a a b c]
[0 1 2 3 4 5 6 7]

为例，其哈希表是这样的：

1
2
3
4
[aab] -->[4]->[0]
[abc] -->[5]->[1]
[bca] -->[2]
[caa] -->[3]

后面的匹配过程都是根据这个哈希表来完成。当算法扫描到第一个aab时候，发现aab对应的哈希链是空的，也就是说一定不存在与之相匹配的串，就将其插入哈希表中。持续这样操作直扫描到第二个aab时，算法发现该哈希对应的链上已经链接了其它的字符串，这说明前面已经出现过字符串aab了，于是这里可以得到一个匹配对(4,3)，表示该位置前面存在一个长度为3的相同串。但是这时候算法还不能确定(4,3)就是最后的匹配，因为后面可能还有更长的。这里算法使用了懒惰匹配算法：当出现一个的匹配后，算法不会直接确定该匹配，直到下一个匹配比当前匹配更短，这时候就确定上一个匹配为最佳匹配，并将其写入LZ77编码串中。

这里LZ77规定匹配串的最小长度是3，最大长度是258。

每当向LZ77编码串写入一个字符串字面或者写入一个匹配对，Gzip就会对该串频率统计以方便后面的霍夫曼编码。当达到以下条件时算法会对当前的LZ77编码串做一次霍夫曼编码：

这里首先定义LZ77编码串的长度为:字符串字面量的个数+匹配对的个数

  1. 每当len(lz77_string) % 4096 = 0时（也就是编码串的长度达到一次4096时）进行一次的判定：

    1. 预估的压缩数据的长度小于原始长度的一半（这里的预估是使用一种有较多的冗余编码方法对编码串进行编码后的输出长度）
    2. 匹配对的个数少于未匹配对的个数

    如果以上两个条件都满足，就当前编码串的所有内容进行霍夫曼编码，并清空LZ77编码串缓存。

  2. 每次LZ77编码串接收新的字符串字面量或者匹配对时：

    如果LZ77串的长度(字符字面量的个数+匹配对的个数达到了32767)或者匹配对的个数达到了32768就进行一次刷洗，将当前的LZ77压缩串传给霍夫曼编码。

霍夫曼编码实现

前面已经说到，gzip会分别采用静态和动态编码对LZ77压缩串进行压缩，两者唯一的区别是前者如使用内置的固定编码对LZ77的字符串字面量和匹配对进行编码，并将压缩数据写入压缩文件，而后者则使用根据串的频率信息计算出来的编码。

对于静态编码，内置的编码是什么样的这里不做过多赘述。下面简单叙述一下动态编码的规则。

gzip把字面量和匹配的长度放到一棵霍夫曼树中，这些一共有286个节点：

  1. 0-255：对应0x00-0XFF中的256种byte
  2. 256：一共霍夫曼压缩块的结束标记
  3. 257-285表示匹配长度的29个范围。由于匹配长度的范围为[3,258],因此这里这里把258+3-1=256个匹配串的长度分配给这29个编码中（实际的编码后面会再跟特定的bit序列来表明具体是哪个值），具体如何分配的这里不再赘述。

而gzip对距离编码则采用一棵单独的有30个叶子节点的树进行编码，由于距离长度的范围是[1,32768],因此这里也要把32768个距离值分配到这个30个叶子节点中，也和匹配长度一样，编码后面会跟随特定的比特序列来确定具体是哪一个距离值。由于在接收LZ77编码那个步骤中已经完成了基本的频率统计，因此霍夫曼编码这一步就是根据频率统计信息构建一棵特殊的霍夫曼树，并根据树结构赋予不同的叶子节点不同的编码即可。

最后gzip依次将或父母编码的元数据(包括编码信息和编码类型等)写入压缩文件,并写入编码后的数据和结束标记，这样就完成了一个压缩数据块的写入工作。

参考文献

http://staff.ustc.edu.cn/~yuzhang/ds/gzip/gzip_principle.htm

https://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art053