浅学GZIP DEFLATE算法

gzip 通常指的是压缩软件或者其对应格式,而它所使用的算法名为 DEFLATE。
DEFLTE 算法主要结合了 LZ77 与霍夫曼编码,算法中也描述了对应的内容编码格式。

DEFLATE 算法主要用于 gzip、PNG 图片压缩。我们在网站上经常能看到 Content-Encoding: gzip 这个 http 响应头,表示内容使用 gzip 压缩。不过,谷歌页面的压缩编码方式换成了自研的“br”。

本文很多内容来自他人博客,感谢乐于分享的大家,文末有参考资料出处。

1. LZ77算法

LZ77 算法由 Abraham LempelJacob Ziv 在 1977 年提出,相关算法被广泛应用于各种压缩算法中。

TypeScript playground 的分享 URL 就是使用了 lz-string 这个库进行压缩的。虽然相关算法经常被用于文字内容压缩,但是如果将任意文件表示为二进制内容“01”的串,那么这些文本压缩算法也可以被来“压缩”任意文件,只是效果未必很好。

1.1 字典编码

文件中总是会有重复的部分,通过将前面出现过的内容保存到字典并编码索引,后续相同的内容使用索引表示,取代重复的部分。
示例:

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.

将上面的葛底斯堡演说进行字典编码,表示如下:

Four score and seven years ago <4,30>fathe<3,16>brought forth, on this continent, a new nation,<4,25>ceived in Liberty<3,36><3,102>dedicat<3,26>to<3,69>e proposi<4,56><3,85>at all m<3,138>a<3,152>cre<5,44>equal.

这里的索引表示为 <length, distance> 的形式,即向前 distance 个字符,取 length 长度的字符进行填充。

LZ77 提供了一种通用算法,通过加入滑动窗口、缓冲区的概念,让上述索引和编码过程变得高效。感兴趣的话可以参考这篇文章:压缩算法之字典编码(上)_Mica_Dai的博客-CSDN博客_字典编码

可以看出,处理后的内容似乎比原文还长。此外,这种编码方式仅限于文本内容,还需要考虑如何对 <> 符号进行转义。
为了解决这些问题,引入一种变长编码方案。

2. 霍夫曼编码

2.1 前缀编码

我们知道,1byte = 8bit,通常的数据储存使用的是固定长度字节。如 int8 类型,每次读取 8bit 内容进行计算即可。

如果字符的储存位数不固定,如何区分不同的字符呢?
答案是采用前缀编码。

假设需要表示共 4 种字符,采用如下编码方案:

A: 1
B: 0
C: 10
D: 11

显然,读取到“11”时,无法区分被编码的内容是“A”还是“D”。

正确的一种做法如下:

A: 1
B: 01
C: 001
D: 000

这样,在顺序读取内容时,不会产生任何歧义。如“101001”,可以被正确读取为“ABC”。

前缀编码,通过避免较短编码成为较长编码的前缀,保证编码没有歧义。

2.2 霍夫曼编码

霍夫曼编码由 David Huffman 于 1952 年论文中发表,当时他的教授允许学生们解决“最佳编码问题”来代替期末考试。25 岁的霍夫曼为了逃避考试,花费数月,解决了香农(信息论祖师爷)也没能搞定的问题。

2.2.1 构造过程

假设我们要对字符 a、b、c、d、e 进行编码,它们的使用频率如下表所示:

character times
a 1
b 4
c 4
d 3
e 1

按照使用频率,构造一个最小优先级队列。

弹出两个优先级最低的字符作为子节点,构造出第一个二叉树;父节点的优先级视为两个字节优先级之和,然后把父节点插入队列中。

重复该过程,直至构建出一个二叉树。

则编码为:

character code
a 000
b 10
c 11
d 01
e 001

2.2.2 解码示例

有字符串 badbec,编码后得到 10000011000111
解码时,依次读入每个比特,利用霍夫曼树,自根节点开始逢 0 向左逢 1 向右,到达叶子节点即输出相应的字符。然后回到树的根节点,继续扫描输入流。

2.2.3 性质

设二叉树具有 n 个带权叶结点,从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为“树的带权路径长度”(Weighted Path Length of Tree,WPL)。
霍夫曼树是 WPL 最小的二叉树。

显然,这个性质可以帮助减少总体的编码长度,因为权值即字符出现频率、路径长度即编码长度。

2.3 范式霍夫曼编码

不同文件的内容不同,这表示所生成的霍夫曼树也有所区别,因此压缩文件内也要保存霍夫曼树本身。如何以更小的空间储存霍夫曼树?答案是采用范式霍夫曼树。

2.3.1 调整方式

DEFLATE 算法规定,霍夫曼树的每一层的叶子节点必须从这一层的最左侧开始,并按照霍夫曼编码的数值大小从小到大依次排列;内部节点排列在随后。此外,同一层的原始符号应该按照字典序依次排列。

直观一点的表达:短分支往左放,同层叶子字典序递增。

这样前面的范式霍夫曼树就被调整为:

调整后的编码:

character code
a 110
b 00
c 01
d 10
e 111

可以看出,经过调整,每个字母对应的编码长度没有变化,且相同长度的编码都是依次递增的。

2.3.2 编码推算

范式霍夫曼编码中,某长度编码的最小值,取决于上个长度的编码的最小值和数量。
现设长度为 i 的编码的最小值为 mi, 有 ni 个。又设长度为 0 的编码的最小值为 0,有 0 个。那么:

$$$$m_{i+1}=(m_i+n_i)<<1 $$$$

这里的“<< 1”是位进一,也就是在二进制表示时后面加一个 0。
例如 a 是最小的 3 位长编码,它的编码与最小的 2 位长编码 b 关系是 (00 + 3) << 1 = 6,换成二进制即:

其实也可以将公式改为“每个长度的最小值编码 = 上个长度编码最大值 << 1”,但这并不利于接下来要做的事情。

2.4 只存长度

首先进行名词定义

  • symbol:被编码的单个符号,如 a、b、c、d、e 中的单个字母。
  • alphabet:编码空间,涵盖所有 symbol,有顺序。

按理来说,应该存储每种 symbol 对应的霍夫曼编码序列。但是有了范式霍夫曼树,可以将其简化为:只记录每种原始值(symbol)对应的编码的长度。
不过这里的前提是:被编码的 alphebet 是大家所共知的。

以上面的树为例,记录长度序列为:<3, 2, 2, 2, 3>。

首先我们知道 symbol 为 a、b、c、d、e。扫描得知最小长度为 2,那么长度为 2 的编码的最小值,就是 00(b),后面长度为 2 的编码依次是 01(c),10(d);按照公式,可以计算得到长度为 3 的最小编码是 00 + 3 << 1 = 110(a),第二位是 111(e)。

具体如何将编码表进行还原,参考 DEFLATE(RFC1951)速成解读 (一)—范式Huffman树

DEFLATE 中的 symbol,以字节为单位进行处理。1byte = 8bit,取值范围是 0-255。
难道这表示我们要记录完整的(至少)256 个长度信息?DEFLATE 表示:看我操作。

2.4.1 压一压

长度序列中很容易出现连续重复的值。并且由于文件中可能有很多未使用的 symbol,这些 symbol 不需要参与编码,长度序列记为 0。

例如:

symbol(0 - 255): 00000000 00000001 00000010 00000011 00000100 00000101 00000110 ...
code length:     3        0        0        0        0        0        5              

长度序列为 <3, 0, 0, 0, 0, 0, 5, …>。

注意,每个 symbol 都有自己的霍夫曼编码,因此长度序列(算上其中的 0)自身的长度,与 alphabet 容量相等。

DEFLATE 会对这个长度序列进行编码,如下所示:

code meaning
0-15 表示长度 0 至 15(原始值)
16 前面的长度重复 3 到 6 次,接下来两位指示具体重复多少次(00 = 3, ,,, , 11 = 6)
17 长度 0 重复 3 至 10 次,接下来的 3 位指示具体重复多少次
18 长度 0 重复 11 至 138 次,接下来的 7 位指示具体重复多少次

所以上面的例子会被表示为:3, 0, 16, 10, 5, …

稍等,你还记得我们现在正在压缩的内容是什么吗?霍夫曼编码表里的“编码长度序列”,然而上表里所能表示的最大长度是 15——这说明 DEFLATE 算法所允许的霍夫曼树最大深度为 15,也就是霍夫曼编码值的最大长度是 15。
这也表明,DEFLATE 算法对于被编码数据的长度有一定限制,否则可能出现超出编码范围的情况。此外,由于大文件内不同部分的内容不同,DEFLATE 也会灵活选择分块的具体位置与处理方式。

2.4.2 再压一压

虽然已经进行了一定程度的压缩,但是 DEFLATE 仍然认为不够。“长度序列”本身是霍夫曼编码的产物,何妨再把它用霍夫曼编码压缩一下呢?

DEFLATE 给出了一个特定顺序的 alphabet(根据统计得来的经验值):

$$$$A=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15] $$$$

假设手上的长度序列并不均匀,内容仅包含 2, 3, 4, 16, 17
对长度序列使用范式霍夫曼编码,获得“二阶长度序列”。
二阶长度序列统一记录为 3 bit,按照 alphabet A 进行排列。没有出现的长度序列记录为 0,即000

   [16, 17, 18, 0, 8, 7, 9, 6, 10, 5,  11, 4,  12, 3,  13, 2,  14, 1, 15]
idx:1    2   3  4  5  6  7  8   9  10  11  12  13  14  15  16  17  18  19
   16   17                                 4       3       2
                                                           ↑ k = 16

可以看到二阶长度序列在上表中很稀疏,最右侧 14、1、15 号编码的位置都是 0,记录最右侧有效值的序数 k = 16。

定义 HCLEN = k – 4,后面有用。

所谓的“二阶长度序列”本身是用来压缩原始长度序列的霍夫曼编码表。在文件存放时,后面跟着的是使用该编码表编码后的长度序列。(详细格式参考第 4 节)

再看一下之前的例子:

3, 0, 16, 10, 5, ...
          ↑ 还记得它吗?

额外的位信息依次摆放,对长度序列解码时,如遇到 16、17、18 指令值,读取对应长度并展开即可(与后文的长度与距离码的 Extra bits 类似)。

3. 长度与距离码

“长度码”与“距离码”的说法是我杜撰出来的,以方便与其他编码概念区分。

除了基本的 0-255 的一字节字面量,还需要存储 LZ77 压缩后的 <长度,位置>,因此实际使用的编码范围需要扩大,大于 255 的数值被赋予额外的含义。

注意下面描述的“编码”,与字面量 symbol 一样,也都是需要使用霍夫曼编码处理的。

3.1 长度码

长度与普通字符共用同一编码空间,也就是同一个霍夫曼编码树(literal huffman tree)进行编码。这个编码空间一共有 286 个编码,范围是从 0 至 285。其中 0-255 为普通字符编码,256 表示压缩块的结束;而 257 至 285 则表示长度。长度码的含义如下表所示:

实际上并非直接使用这些编码指代距离,而是需要额外的映射处理。也就是说,长度码其实充当了索引的角色。

每个编码都表示一个(code <= 264)或多个长度(code > 264)。当 code > 264,表示需要继续读取接下来的“Extra Bits”个 bit 参与计算,而这些位按照正常的 int 类型处理。

举例:读取到长度码 275,且接下来的 3 位为 011,则表示实际长度为 51 + 0b011 = 51 + 3 = 54。也就是说,275 自身映射到 51,接下来 3 位的取值范围从 000111,因而总的范围是 51 到 51 + 7 = 58。

3.2 距离码

对于距离码,它有 0 至 29 一共 30 个编码。距离码使用的单独霍夫曼编码树进行编码

距离码的含义如下表所示,使用方式与长度码相同:

这样,30 种距离码,配合一段额外编码长度,能表示的距离范围为 1 至 32768。

距离码(0-29)难道不会与普通字面量 symbol(0-285)搞混吗?别忘了距离码紧跟在长度码之后,因此读取后续的输入内容以后,需要使用距离编码树进行解码,获得 <长度,距离> 指针,再依据缓冲区内容输出即可。

4.动态霍夫曼压缩

有了以上知识,可以一窥动态霍夫曼压缩的过程。

4.1 过程简述

Snipaste_2023-01-06_19-34-23.png

前文提到,literal data 与长度码共用编码空间,距离码单独使用编码空间。对原始数据执行一次霍夫曼编码后,得到压缩数据 * 1 份,编码长度序列 * 2 份。
此处注意,虽然距离码使用单独的编码空间,但是它编码处理的也是原始数据的一部分,最终的纯数据部分里 literal/长度码/距离码 是连续存储在一起的(图中的数据 C)。

前文提到,长度序列自身长度与 alphabet 容量相等,但是通常会有一些没用到的 symbol 在长度序列中被记录为 0。DEFLATE 勤俭持家,决定将末尾的 0 截取掉,因此得到了 HLIT,HDIST(计算方式见下表)。

将被截取处理后的两段长度序列合并,执行 2.4.1 与 2.4.2 节内容里的压缩操作,得到拼接长度序列的压缩编码与压缩后数据。
还记得吗,这里的二阶压缩长度序列也是被截取过的,截取位置为 k。

4.2 区块结构

这样就得到了动态霍夫曼编码所需要的几个关键值,以如下方式排布:

name length description
HLIT 5 bit literal data & 长度码的最大值减 257(原始范围 257-286)
HDIST 5 bit 距离编码最大值减 1(原始范围 1-32)
HCLEN 4 bit k – 4(原始范围 4-19)

HCLEN 限定了 k 的取值范围是 4-19。回顾 2.4 节的内容,序列 A 的前 4 位分别是指令码 16、17、18 与空编码 0。因为几乎一定要用到这几个编码,所以它们被安置在了 A 的前 4 位;考虑到最大“一阶编码长度”限制为 15,而 A 的总长度为 19,正好是 HCLEN 这 4bit 编码所能表示的最大范围(以 4 开始)。

而 HLIT、HDIST 的长度与取值设计,也对应考虑了其编码空间、数据特征。可以说每个 bit 都被压榨干净了。

继续上表:

name length description
处理后的二阶霍夫曼编码表-数据 A (HCLEN + 4) * 3 bit 长度序列编码只有 19 个,每个数字对应的编码长度固定位 3 位。这表示树的深度为 23 = 8,如果是完全二叉树就有 28 = 256 个编码空间。不过霍夫曼树是最优二叉树,但是肯定也够用了。注:最终的一份长度解密数据不可能是以变长编码存储的,否则解码将无从下手。
字符/长度码编码表-数据 B HLIT + 256 个 symbol 使用二阶编码表编码的编码长度序列,literal/长度码 的长度序列编码
距离编码的 Huffman 编码表-数据 B HDIST + 1 个 symbol 使用二阶编码表编码的编码长度序列,距离码 的长度序列编码
DATA-数据 C 变长 有效压缩数据
256 标记 变长 标识区块结束,其实是上面 DATA 的最后一个 symbol

4.3 解码过程

  1. 读取区块的头信息,确认当前是动态霍夫曼编码区块
  2. 读取 5 bit,值 + 257 = HLIT
  3. 读取 5 bit,值 + 1 = HDIST
  4. 读取 4 bit,值 + 4 = HCLEN
  5. 读取 HCLEN * 3 bit(数据 A),对照 alphabet 序列 A,并进行 2.4.1 中的展开操作,还原二阶长度编码序列。基于该序列,构造二阶长度编码树
  6. 读取数据,使用二阶长度编码树,解码出 HLIT + 257 个 literal & 长度码的一阶长度编码序列。基于该序列,构造原始的 literal/长度码 编码树
  7. 读取数据,同样解码出 HDIST + 1 个距离码的长度编码序列。基于该序列,构造原始的距离码编码树
  8. 手握两个编码树,读取实际的压缩数据,解码出 literal symbol;或得到 <长度,距离> 指令,输出对应的前置内容
  9. 直至读取到 256 literal symbol,结束当前区块的处理

5. 补充信息

5.1 压缩区块

受各种因素影响(例如编码过程的缓冲区长度、标记位长度、长度序列的编码长度考量等),DEFLATE 并不是完全将所有文件使用动态霍夫曼压缩处理,而是对文件分块进行压缩,且可能采用不同的策略。

每个压缩后的文件至少有一个区块。

区块类型包括:

  • 无压缩区块(Non-compressed blocks)
  • 动态霍夫曼压缩区块(Compressed blocks)
  • 固定霍夫曼压缩区块(Compression with fixed Huffman codes)

5.1.1 区块头

每个区块头部 3 bit 信息:

长度 名称
1 bit BFINAL
2 bit BTYPE

如果 BFINAL 取值为 1,表明这是最后一个区块。

BTYPE 的取值与含义:

取值 含义
00 无压缩
01 固定霍夫曼压缩
10 动态霍夫曼压缩
11 保留值(错误)

不同区块的内容格式不尽相同。

例如,无压缩区块在前 3 个 bit 头后还有一些固定格式的字节,用于声明区块长度。而另外两种使用霍夫曼压缩的区块,则是在 3 bit 之后立即开始。

5.1.2 编码方式

DEFLATE 对字节流的编码定义比较特别,当然这主要是受到人类阅读习惯和其他编程语言的影响。

例如使用 nodejs 读取 gzip 文件,读取一个固定霍夫曼压缩区块的 buffer 值是 4be4

对应的二进制值如下:

01001011 11100100
     ^^^

其实前 3 个 bit 是 011,而且 BFINAL 取值是最右侧的 1,BTYPE 的取值是接下来的 01。是的,这里 BTYPE 的高位在左。

RFC1951 原文描述如下:

  • Data elements are packed into bytes in order of increasing bit number within the byte, i.e., starting with the least-significant bit of the byte.
  • Data elements other than Huffman codes are packed starting with the least-significant bit of the data element.
  • Huffman codes are packed starting with the most-significant bit of the code.

5.1.3 固定霍夫曼压缩

顾名思义,使用一个固定的霍夫曼编码表来进行编码。

literal value 286-287 并不会出现,只是在这里展示。
距离码 0-31 使用 5 bit 固定长度编码,前文的 Extra bits 规则仍然生效。

对于内容特别简单的文件,可能仅含有一个固定霍夫曼压缩区块。

5.2 文件头

实际使用中的 gzip 数据/文件是有额外的数据头、尾信息的,具体在 RFC1952 中规定。

  • RFC 1951 Raw Deflate
  • RFC 1950 Raw Deflate wrapped in zlib header and zlib trailer
  • RFC 1952 Raw Deflate wrapped in Gzip header and Gzip trailer

参考资料

这篇文章基本是拾人牙慧,拿别人的解读拼接起来的,不过我感觉清晰度还不错。希望你能有所收获。

Gzip 格式和 DEFLATE 压缩算法 – Luyu Huang’s Tech Blog
DEFLATE(RFC1951)速成解读 (一)—范式Huffman树
DEFLATE(RFC1951)速成解读 (三)—无压缩及固定huffman压缩
DEFLATE(RFC1951)速成解读 (四)—动态huffman压缩
Dissecting the GZIP format
霍夫曼树 – OI Wiki
RFC ft-deutsch-deflate-spec: DEFLATE Compressed Data Format Specification version 1.3
LiveVideoStack » 灵光一现的创造——霍夫曼编码
The structure of Deflate compressed block
.Net Deflate 压缩与 zlib 的差异
范氏霍夫曼編碼 – 维基百科,自由的百科全书
https://en.wikipedia.org/wiki/Deflate
数据压缩入门
压缩算法之字典编码(上)_Mica_Dai的博客-CSDN博客_字典编码
madler/infgen

© 版权声明
THE END
喜欢就支持一下吧
点赞6 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容