Gzip 格式和 DEFLATE 压缩算法
1. 引言
当你键入 tar -zcf src.tar.gz src, 就可以将 src 下的所有文件打包成一个 tar.gz 格式的压缩包. 这里的 “tar” 是归档格式, 将多个文件组合成一个文件; 而 “gz” 指的就是 gzip 压缩格式, 使用 DEFLATE 算法压缩得到. 作为使用最广泛的无损压缩算法, DEFLATE 是怎样工作的, 背后的原理是什么? 这篇文章我们来讨论下这个问题.
DEFLATE 算法结合了 LZ77 算法和 Huffman 编码, 由 Phil Katz 设计, 并被 RFC1951 标准化. 本文是笔者对 RFC1951 和 zlib 研究的总结, 首先介绍 LZ77 算法, 再阐述 Huffman 编码在 DEFLATE 中的作用; 最后介绍 gzip 的格式.
2. LZ77 算法
J. Ziv 和 A. Lempel 在 1977 发表了一篇名为 A Universal Algorithm for Sequential Data Compression 的论文, 提出了一种顺序数据的通用压缩算法. 这个算法后来被称为 LZ77 算法. 事实上 DEFLATE 算法使用的 LZ77 跟原版有所不同, 这里我们以 DEFLATE 中的为准.
2.1 基本原理
我们平时使用的文件总是会有很多重复的部分, LZ77 压缩算法正是利用了这一点. 它会试图尽可能地找出文件中重复的内容, 然后用一个标记代替重复的部分, 这个标记能够明确地指示这部分在哪里出现过. 举个例子, 以 葛底斯堡演说 的第一段为例:
Four score and seven years ago our fathers brought forth, on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.
我们可以找出不少重复的片段. 我们规定, 只要有两个以上的字符与前文重复, 就使用重复标记 <d,l> 代替它. <d,l> 表示这个位置的字符串等价与 d 个字符前, 长度为 l 的字符串. 于是上面的内容就可以表示为:
Four score and seven years ago <30,4>fathe<16,3>brought forth, on this continent, a new nation,<25,4>ceived in Liberty<36,3><102,3>dedicat<26,3>to<69,3>e proposi<56,4><85,3>at all m<138,3>a<152,3>cre<44,5>equal.
呃, 你可能已经发现了这样 “压缩” 后的结果比原文还长. 别急, 这只是个演示, 稍后我们能看到如何解决这个问题.
实现这个算法最简单的方式就是遍历字符串, 对于每个字符都在前文中顺序查找是否有重复的字符, 然后求出最长重复子串. 这种做法时间复杂度为 \(\mathrm{O}(n^2)\), 效率较低, 特别是在处理大文件的时候. 为了提高效率, 我们使用哈希表和滑动窗口优化.
2.2 使用哈希表
顺序查找过于缓慢, 我们可以使用哈希表来提升效率. 我们使用一个哈希表把一个长度为三的字符串映射成一个列表, 包含这个字符串所有曾经出现过的位置. 压缩时从头到尾扫描字符串. 假设接下来的三个字符为 XYZ, 首先检查字符串 XYZ 是否在哈希表中. 如果不在, 则原样输出字符 X 并移动到下一个字符. 否则把当前位置开始的字符串与所有 XYZ 出现过的位置开始的字符串相比较, 寻找出一个长度为 N 的最长的匹配并输出重复标记, 然后向后移动 N 个字符. 无论能否在哈希表中找到匹配, 都会把当前位置插入到 XYZ 在哈希表映射的列表中.
举个例子, 考虑字符串 abcabcdabcde, 算法运行时有以下几步:
扫描到第 0 个字符
a, 哈希表为空, 原样输出字符a, 并且将字符串abc插入哈希表中.1
2
3
4hash table: {}
abcabcdabcde
^
output: a扫描到第 3 个字符
a, 哈希表指示abc在0处出现过. 最长的匹配就是abc, 因此输出<3,3>. 同时把当前位置插入到abc映射的列表中.1
2
3
4hash table: {"abc":[0],"bca":[1],"cab":[2]}
abcabcdabcde
^
output: abc<3,3>扫描到第 7 个字符
a, 哈希表指示abc在0,3处出现过. 依次与当前位置匹配,0处只能匹配到abc, 而3处能匹配到abcd, 最长的匹配为abcd, 于是输出<4,4>. 同时把当前位置插入到abc映射的列表中.1
2
3
4hash table: {"abc":[0,3],"bca":[1],"cab":[2],"bcd":[4],"cda":[5],"dab":[6]}
abcabcdabcde
^
output: abc<3,3>d<4,4>
BTW, zlib 中这个哈希表的实现非常精妙, 关于它的详细实现超出了本文的讨论范围. 对 C 语言感兴趣的同学一定要去看看这个实现.
2.3 滑动窗口
即使有了哈希表, 过长的文件仍然会导致效率问题. 为此我们使用滑动窗口, 查找重复内容时仅在窗口中查找. 窗口的长度是固定的, 通常是 32KB. 在 zlib 的实现中, 使用一个两倍窗口大小的缓冲区, 如下所示:
1 | |
初始时将待压缩数据填入缓冲区, 指针位于缓冲区的开始处; 随后指针向后扫描, 对数据进行压缩. 我们把指针扫描过的的部分称为 search 区, 未扫描过的部分称为 lookahead 区. 对于每个扫描的字符, 算法都只会在 search 区中寻找匹配. 当 lookahead 区长度不足(小于一个固定值)时, 算法就会移动窗口以继续扫描更多的数据. 具体的做法时将缓冲区后半部分的数据复制到前半部分并移动指针, 然后在缓冲区的后半部分读入新数据, 接着还要更新哈希表, 因为数据的位置发生了改变.
2.4 惰性匹配(lazy matching)
有的时候这种策略并不能得到最优的压缩结果. 举个例子, 考虑字符串 abcbcdabcda, 当扫描到第 6 个字符的时候是这样的:
1 | |
哈希表指示 abc 在 0 处出现过, 最长匹配为 abc, 于是输出 <6,3>; 后面的 da 没有与之重复的内容, 原样输出. 因此压缩的结果是 abcbcd<6,3>da. 然而在第 7 个字符的位置能在前文找到一个更长的匹配 bcda, 更好的压缩结果应该是 abcbcda<4,4>.
为了解决这个问题, DEFLATE 采用一叫做惰性匹配的策略优化. 每当算法找到一个长度为 N 的匹配后, 就会试图在下一个字符寻找更长的匹配. 只有当没有找到更长的匹配时, 才为当前匹配输出重复标记; 否则就会丢弃当前匹配, 使用更长的匹配. 注意惰性匹配可以连续触发, 如果一次惰性匹配发现了更长的匹配, 仍会继续进行惰性匹配, 直到无法在下一个字符找到更长匹配为止.
惰性匹配能够提高压缩率, 但是会让压缩变慢. 运行时的参数会控制惰性匹配, 只有在当前匹配不够长, i.e. 小于某个配置的值的时候, 才会触发惰性匹配. 可以根据需求是压缩率优先还是速度优先来调整这个值, 或者关闭惰性匹配.
3. Huffman 编码
如果我们真的使用 <d,l> 这样的格式表示重复的内容, 那就太愚蠢了. 首先是这样的格式太占空间了, 2.1 节中使用这种方式 “压缩” 的 葛底斯堡演说 比甚至原文还长. 其次这种格式让尖括号变成了特殊字符, 还得设法转义它们. 那么应该如何表示重复部分距离和长度呢? DEFLATE 的做法是打破旧秩序, 建立新秩序 – – 使用 Huffman 编码对数据重新编码.
Huffman 编码由美国计算机科学家 David A. Huffman 于 1952 年提出, 它是根据字符出现频率构造而成的前缀编码. 与我们平时常用的固定位编码(每个字符占 8 位)不同, Huffman 编码中每个字符的编码的位数都可能不同, 却能够明确地区分每个字符, 不会有任何歧义.
3.1 前缀编码
为什么每个字符占的位数都不同却能明确地区分它们呢? 这就是前缀编码的作用. 为了说明什么是前缀编码, 试想我们在打电话. 电话号码的长度是不一样的: 有三位的, 如 110, 119; 有五位的, 如 10086, 10010; 有 7 位或 8 位的固定电话, 又有 11 位的手机号码等等. 然而拨号的时候依次输入号码, 总能正确识别 (固定电话摘机拨号无需按呼叫键). 这是因为除了匪警 110 之外不会有任何一个电话号码以 110 开头, 任何一个固定电话号都不可能是某个手机号的前缀. 电话号码就是一种前缀编码. 所以, 虽然 Huffman 编码中每个字符的编码位数都不同, 但是短的编码不会是长的编码的前缀. 这样就保证了 Huffman 编码没有歧义.
我们使用 Huffman 树构造 Huffman 编码. 前文说了, Huffman 编码有长有短, 那么显然让使用频率高的字符编码短, 使用频率高的字符编码长比较合理. 假设我们要对字符 a, b, c, d, e 进行编码, 它们的使用频率如下表所示:
| character | times |
|---|---|
| a | 1 |
| b | 4 |
| c | 4 |
| d | 3 |
| e | 1 |
构造方式非常简单. 我们把字符的出现频率视为优先级, 放入一个最小优先队列中:
然后弹出两个优先级最低的字符作为子节点, 构造出第一个二叉树; 父节点的优先级视为两个字节优先级之和, 然后把父节点插入队列中:
重复这个操作, 最后我们会得到一颗二叉树. 这便是 Huffman 树.
我们把这棵树的左支编码为 0, 右支编码为 1, 那么从根节点向下遍历到叶子节点, 即可得出相应字符的 Huffman 编码. 因此我们得到上面例子的 Huffman 编码表为:
| character | code |
|---|---|
| a | 000 |
| b | 10 |
| c | 11 |
| d | 01 |
| e | 001 |
假设有字符串 badbec, 使用 Huffman 编码后得到 10000011000111. 解码也很简单, 依次读入每个比特, 利用 Huffman 树, 自根节点开始逢 0 向左逢 1 向右, 到达叶子节点即输出相应的字符, 然后回到根节点继续扫描.
3.2 对距离和长度进行编码
一个字节有 8 位, 因此我们需要 0 至 255 一共 256 个 Huffman 编码. 统计文件各个字符的使用频率, 构造出 Huffman 树即可计算出这 256 个编码. 那么如何用 Huffman 编码表示重复标记中的距离和长度呢? DEFLATE 算法是这样做的:
对于距离, 它有 0 至 29 一共 30 个编码. 距离编码的含义如下表所示:
code extra distance code extra distance code extra distance 0 0 1 10 4 33-48 20 9 1025-1536 1 0 2 11 4 49-64 21 9 1537-2048 2 0 3 12 5 65-96 22 10 2049-3072 3 0 4 13 5 97-128 23 10 3073-4096 4 1 5,6 14 6 129-192 24 11 4097-6144 5 1 7,8 15 6 193-256 25 11 6145-8192 6 2 9-12 16 7 257-384 26 12 8193-12288 7 2 13-16 17 7 385-512 27 12 12289-16384 8 3 17-24 18 8 513-768 28 13 16385-24576 9 3 25-32 19 8 769-1024 29 13 24577-32768 每个编码都表示一个或多个距离. 当它表示多个距离时, 意味着接下来会有 extra 位表示具体的距离是多少. 例如假设编码 14 接下来的 6 位为
011010, 则表示距离为 129 + 0b011010 = 129 + 26 = 155. 这样距离编码能表示的距离范围为 1 至 32768.对于长度, 它与普通字符共用同一编码空间. 这个编码空间一共有 286 个编码, 范围是从 0 至 285. 其中 0 至 255 为普通字符编码, 256 表示压缩块的结束; 而 257 至 285 则表示长度. 长度编码的含义如下表所示:
code extra length(s) code extra length(s) code extra length(s) 257 0 3 267 1 15,16 277 4 67-82 258 0 4 268 1 17,18 278 4 83-98 259 0 5 269 2 19-22 279 4 99-114 260 0 6 270 2 23-26 280 4 115-130 261 0 7 271 2 27-30 281 5 131-162 262 0 8 272 2 31-34 282 5 163-194 263 0 9 273 3 35-42 283 5 195-226 264 0 10 274 3 43-50 284 5 227-257 265 1 11,12 275 3 51-58 285 0 258 266 1 13,14 276 3 59-66 与距离编码类似, 每个编码都表示一个或多个长度, 表示多个长度时后面会有 extra 位指示具体的长度. 长度编码能表示的长度范围为 3 至 258.
解压时, 当读到编码小于等于 255, 则认为这是个普通字符, 原样输出即可; 若在 257 至 285 之间, 则说明遇到了一个重复标记, 这意味着当前编码表示的是长度, 且下一个编码表示的是距离. 解码得到长度和距离, 再在解压缓冲区中找到相应的部分输出即可; 若为 256, 则说明压缩块结束了.
3.2 Huffman 编码表的存储
我们知道, Huffman 编码是根据字符的出现频率构造的. 不同的文件字符出现的频率都不同, 因此 Huffman 编码也不同. 为了能够正确地解压, 压缩块中还必须存储 Huffman 编码表. 这一节我们来讨论如何用最小的空间存储这个 Huffman 编码表.
3.2.1 将 Huffman 编码表表示为长度序列
为了高效地存储 Huffman 编码表, DEFLATE 算法规定, Huffman 树的每一层的叶子节点必须从这一层的最左侧开始, 按照 Huffman 编码的数值大小从小到大依次排列; 内部节点排列在随后. 此外同一层的字符应该按照字符表(如 ASCII 码表)的顺序依次排列. 这样 3.1 节中的 Huffman 树就应该调整为:
调整后的 Huffman 编码表就是:
| character | code |
|---|---|
| a | 110 |
| b | 00 |
| c | 01 |
| d | 10 |
| e | 111 |
注意调整后的 Huffman 编码并不影响压缩率: 各个字符编码的长度不变, 最常用的字符的编码仍是最短的. 不难发现, 相同长度的编码都是依次递增的, 且某个长度的编码的最小值取决于上个长度的编码的最小值和数量. 现设长度为 \(i\) 的编码的最小值为 \(m_i\), 有 \(n_i\) 个; 又设长度为 0 的编码的最小值为 0, 有 0 个. 那么易得
\[m_{i+1} = (m_i + n_i) \ll 1\]
这里的 “\(\ll\)” 表示左移. 这样, 我们只需要知道每个字符的 Huffman 编码长度, 即可推算出所有字符的 Huffman 编码了. 对如上面的例子, 我们只需存储长度序列 \(<3, 2, 2, 2, 3>\) 即可. 解压时扫描这个序列, 得到各个长度的编码的数量, 即可求算出各个长度的编码的最小值; 相同长度的编码都是依次递增的, 所以依次加一, 即可得出所有字符的 Huffman 编码. 特别地, 长度 0 表示这个字符没有在压缩块中出现过, 构造 Huffman 编码的时候会排除它.
3.2.2 对长度序列编码
长度序列中很容易出现连续重复的值; 并且由于文件中可能有很多未使用的字符, 也会出现很多 0. 因此 DEFLATE 会对这个长度序列编码, 如下所示:
| code | meaning |
|---|---|
| 0-15 | 表示长度 0 至 15 |
| 16 | 前面的长度重复 3 到 6 次. 接下来的两位指示具体重复多少次, 这与 3.2 节中的长度和距离编码类似. |
| 17 | 长度 0 重复 3 至 10 次. 接下来的 3 位指示具体重复多少次. |
| 18 | 长度 0 重复 11 至 138 次. 接下来的 7 位指示具体重复多少次. |
3.2.3 使用 Huffman 编码压缩 Huffman 编码表
将 Huffman 编码表表示成编码后的长度序列已经比较精简了, 但是 DEFLATE 算法认为这还不够. 它决定对这个编码后的长度序列再次使用 Huffman 编码压缩. 这一步就有一点点绕了. 为了做到这一点, 我们需要为长度序列的编码 – – 0 至 18, 构造 Huffman 编码表(然而这个长度序列表示的就是一个 Huffman 编码表, 等于我们是在为一个 Huffman 编码表构造 Huffman 编码表). 问题来了, 怎么表示这个 Huffman 编码表的 Huffman 编码表呢? 首先, DEFLATE 算法定义了一个神秘数组:
\[A = \{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15\}\]
因为有可能不是所有的长度都能用上, 因此我们会先用一个数字标识使用这个数组中的前 k 个编码. 例如长度序列编码只使用了 2, 3, 4, 16, 17, 则 k = 16. 接下来会有 k 个数字, 第 \(i\) 个数字表示长度序列编码 \(A[i]\) 的 Huffman 编码的长度, 0 表示相应的编码未使用. 因为只要知道了每个字符的 Huffman 编码长度, 就能推算出所有字符的 Huffman 编码. 这样我们就得到了编码后的长度序列的 Huffman 编码表.
在压缩数据中先存储编码后的长度序列的 Huffman 编码表, 紧接着再存储编码后的长度序列的 Huffman 编码数据. 这样我们就在压缩块中用较小的空间存储了压缩数据的 Huffman 编码表.
4. Gzip 格式
最后我们再简单描述下 gzip 的格式.
Gzip 格式由头部信息, 压缩主体和尾部信息组成. 头部包括文件基本信息, 时间, 压缩方法, 操作系统等; 尾部则包含校验和与原始大小. 这些信息与压缩算法无关, 这里就不深入讨论了, 需要了解的同学可直接参阅 RFC1952.
压缩主体由一个或多个区块(block)组成. 每个区块的长度不固定, 都有自己的压缩和编码方式. 区块可能起始或结束于任何一个比特, 不必对齐字节. 需要说明的是, 重复标记指示的距离有可能跨越区块.
上文阐述的都是使用动态 Huffman 编码压缩. 事实上一个区块还有可能使用静态 Huffman 编码压缩或者不压缩. 使用静态 Huffman 编码压缩的区块会使用算法预设的 Huffman 编码进行压缩和解压, 不需要存储 Huffman 编码表.
所有的区块都以一个 3 位的头部开始, 包含以下数据:
| name | length | description |
|---|---|---|
| BFINAL | 1 位 | 标识是否是最后一个区块 |
| BTYPE | 2 位 | 标识类型. 00: 未压缩; 01: 静态 Huffman 编码压缩; 10: 动态 Huffman 编码压缩; 11: 保留 |
4.1 未压缩区块
未压缩区块包含以下数据(紧接着头部):
| name | length | description |
|---|---|---|
| LEN | 2 位 | 区块数据长度 |
| NLEN | 2 位 | LEN 的补码 |
| DATA | LEN 字节 | 有效数据 |
4.2 压缩区块
动态 Huffman 编码压缩区块包含以下数据(紧接着头部):
| name | length | description |
|---|---|---|
| HLIT | 5 位 | 长度/字符编码的最大值减 257. 因为并不是所有的长度编码都被使用, 因此这里标记最大的长度/字符编码(长度与普通字符共用同一编码空间). |
| HDIST | 5 位 | 距离编码最大值减 1. 原理同上. |
| HCLEN | 4 位 | 3.2.3 节中的 k 减 4. 标识使用了神秘数组中的前几个编码. |
| 编码后的长度序列的 Huffman 编码表 | (HCLEN + 4) * 3 位 | 如 3.2.3 节所述的 “k 个数字”. 因为长度序列编码只有 19 个, 因此每个数字 3 位就够了. |
| 长度/字符编码的 Huffman 编码表 | 变长 | 根据上述 Huffman 编码表编码的长度序列, 用于表示长度/字符编码的 Huffman 编码表. |
| 距离编码的 Huffman 编码表 | 变长 | 根据上述 Huffman 编码表编码的长度序列, 用于表示距离编码的 Huffman 编码表. |
| DATA | 变长 | 有效压缩数据 |
| 256 结束标记 | 变长 | 标识区块的结束 |
静态压缩区块比较简单, 头部后紧接着就是有效压缩数据, 最后在加一个 256 结束标记.
5. 总结
DEFLATE 算法为了尽可能地压缩数据可谓是煞费苦心, 整体看下来还是比较复杂的. 由于时间和精力有限, 笔者也没有仔细阅读 zlib 源码, 因此本文主要基于 RFC1951, 对于实现细节讨论较少. 如有错误或者讲得不明白的地方, 欢迎指正. 对实现感兴趣的同学可以参阅 zlib 源码.
BTW, LZ77 算法还有个简单高效的实现: ariya/FastLZ. FastLZ 未使用 Huffman 编码, 仅使用 LZ77. 用它压缩文本又快又好, 不过二进制数据的压缩率不够理想. FastLZ 的实现比较简洁, 建议大家阅读.
参考资料