跳到正文
01 / 03

基础压缩:LZ77 与 Huffman

压缩文件必须交给一个没有见过原文的接收者,仍能恢复出原文。这一要求决定了整个设计:怎样描述重复,怎样把描述变成位,接收者怎样知道这些位的含义,又怎样知道何时结束。我们先造出一套完整的小型编解码器,再看 zlib 中对应的做法。

找到更短、又能还原的描述

假设要把 ABABABAB 发送给另一台计算机。在这里使用的字节约定中,A 的数值是 65,十六进制写成 41;B 的数值是 66,写成 42。整条消息有八个字节:

41 42 41 42 41 42 41 42

一个字节有八个二进制位,简称“位”,可以表示 0 到 255 的任意整数。十六进制用两位数字写出一个字节,每位数字代表四个二进制位。因此,41 表示位序列 01000001,不是文本字符“4”和“1”。文件就是一串这样的字节值。文本、图片、可执行程序,交给压缩器之前都会成为字节序列。文本还需要字符编码:在 UTF-8 中,一个字符可能占几个字节。这里的压缩方法不要求输入是可打印的字母。

我们的任务是生成另一串字节,再逐字节、连同长度一起恢复原串,包括其中的所有零字节。这叫无损压缩。接收者必须恢复这里的八个字节,不能只得到一段看起来一样的文字。把原始字节叫作 input,压缩数据包叫作 packet,恢复的字节叫作 output,往返目标就是 decode(encode(input)) = input。

把输入照抄到数据包中,容易恢复,却没有节省空间。把它替换成“A 和 B 交替,共八个字节”,人能看懂,计算机却遇到了新问题:A 和 B 怎样表示?八表示字节数还是重复次数?指令到哪里结束?如果原文恰好含有指令使用的标点怎么办?压缩格式必须用精确规则回答这些问题,不能让接收者猜测发送者的意思。

这里有两种不同的机会。重复字符串可以换成指向先前字符串的引用;出现次数不同的符号可以使用长短不同的位编码。我们将同时使用这两种方法。它们解决的问题不同,因此必须看清第二步接收的究竟是哪一种表示。

任何无损方法也不可能把所有输入都变短。一字节的输入有 256 种,而长度为零的字节串只有一种。不同输入必须有能区分开的描述,否则不能唯一恢复。长度更大时,同样的计数困难仍然存在。实用压缩器利用部分输入的规律,也接受另一些输入被元数据撑大的结果,最终比较的是整个传输表示的大小。

把重复字节换成指令

先看一个源串已经完整存在的例子 ABCABC。直接写出前三个字节后,接收者已经有 ABC。此时无需再发送一次 ABC,只要发送“向后找三个字节,再复制三个字节”。直接写出的一个字节叫作字面量。复制指令叫作向后引用,也叫匹配。它的距离说明源位置离下一个输出位置有多远;长度说明要生成多少个字节。

原文:  A B C A B C
指令:  字面量 A,字面量 B,字面量 C,匹配(距离 3,长度 3)
恢复:  A B C → A B C A B C

两个数字缺一不可。距离 3、长度 2 只会生成 AB;长度 3、距离 2 则会生成 BCA。距离相对于匹配开始时的输出位置计算,不是文件中的绝对地址,也不指向压缩包。编码端和解码端可以把存储放在不同位置,仍然对同一串字节达成一致。

这一类方法叫作 LZ77。压缩器在先前的原始字节中寻找有用的出现位置,选择写字面量还是匹配。解码器无需重新搜索,只需执行数据包里实际发送的指令。同一输入可以有多种指令序列。例如,ABCABC 也可以表示成六个字面量。以后,编码器正是利用这种自由,在搜索耗时和压缩率之间取舍,而无需修改解码规则。

复制可以为自己生成后续的源字节

回到 ABABABAB。输出两个字面量后,已有 AB。能不能马上用一个匹配描述剩下六字节?可以:距离 2,长度 6。开始时只有两个源字节,因此必须准确规定复制顺序:从当前输出末尾向后数给定距离,读一个字节,把它追加到输出,再重复。每次追加都会移动末尾。

正在追加的位置,从零计数 读取的源位置 读到的字节 追加后的输出
2 0 A ABA
3 1 B ABAB
4 2 A ABABA
5 3 B ABABAB
6 4 A ABABABA
7 5 B ABABABAB

写位置 4 时,读的是这个匹配刚在位置 2 写出的字节。这叫重叠匹配。它表示一系列前后依赖的单字节复制,不是从某个已有的六字节快照整体搬运。重叠规则不同的批量复制函数不能直接替代它。即使先复制到临时缓冲区,开始时也没有六个已存在的源字节可供读取。

下面这段小型 JavaScript 中,output 是可增长的字节数组,distance 和 length 是匹配的距离和长度。每次追加之后,下一次读取都会重新计算源下标:

if (distance < 1 || distance > output.length || length < 3)
  throw new Error("invalid match");
for (let i = 0; i < length; i++)
  output.push(output[output.length - distance]);

这里规定长度至少为三,这是教学编码器采用的规则,也是 DEFLATE 能表示的最短匹配。距离检查保证第一次读取指向已经存在的字节。此后的源位置一直位于增长中的输出末尾之前,即使长度超过距离也成立。距离零不能表示“重复最后一个字节”:它指向尚未写入的位置。重复最后一个字节应使用距离 1。

于是,八个字节变成三条指令:

字面量 A,字面量 B,匹配(距离 2,长度 6)

这是有用的中间表示,却还不是压缩后的字节序列。“字面量”和“匹配”这些种类、两个整数、消息结束的位置,都还需要表示。如果每条指令都保存成一个很大的程序对象,它占的内存可能比原文还多。要节省空间,还得继续设计传输表示。

先用最直接的搜索办法。站在下一个尚未编码的输入位置,逐一尝试距离 1 到当前位置的每个候选。对每个距离,从这里开始向前比较原文字节与该距离之前的字节,直到不相等或到达输入结尾。比较可以越过当前起点:这正对应刚才的顺序复制语义。保留最长匹配,长度相同时选择距离最近的那个。长度至少为三就发出匹配,前进整个匹配长度;否则发出一个字面量,只前进一字节。输入用完后追加结束标记。

在位置 2 的 ABABABAB 中,距离 1 立即失败,因为 A 与前面的 B 不同;距离 2 连续比较出六字节,直到输入结尾,于是选中长度 6、距离 2。编码器拥有完整原文,可以直接比较那些字节。解码器没有原文,必须按先前表格依次生成它们。教学交互采用的正是这套搜索和最近距离的平局规则;它容易理解,却会反复检查大量候选,下一篇才能具体说明要优化哪些工作。

让常见指令使用更短的编码

假设某个指令字母表中有四个符号,出现次数分别为 8、4、2、2。这里的字母表指全部可能符号的集合,不限于英文字母。暂时把这四个符号叫作 P、Q、R、S。固定两位的编码 00、01、10、11 足以区分它们,十六次出现共需要 32 位。

根据出现次数,可以做得更好:P 使用 0,Q 使用 10,R 使用 110,S 使用 111。有效载荷需要:

8 × 1 + 4 × 2 + 2 × 3 + 2 × 3 = 28 位

节省来自那个最短的编码使用了八次。这个计算中的 P 和 Q 是抽象符号,不是把前例的 A、B 换了名字。

编码长短不同,会带来边界问题。如果某个符号是 0,另一个是 01,看到第一个零时,接收者不知道一个符号是否已经结束。刚才选择的编码避开了这一困难:没有哪个编码是另一个编码开头的一段,也就是前缀。可以把全部编码画成二叉树:根是尚未读取任何位的位置,零和一各选择一条分支,叶子标出一个完整符号。这样的前缀码可以从左向右读取:沿树走到叶子,输出对应符号,再从树根开始读下一个。例如 010110111 只能切成 0 | 10 | 110 | 111,恢复 P、Q、R、S。空格只用于讲解,数据包不需要它们。

Huffman 编码根据频率构造这样的树。一开始,每个用到的符号各是一片叶子,权重是出现次数。反复合并当前最轻的两棵树。为使教学编码器遇到平局时也有确定结果,同权重时优先选择叶子最小符号编号更小的树。先把 R:2 和 S:2 合成权重 4 的子树,再把它与 Q:4 合成权重 8 的子树,最后与 P:8 合成权重 16 的根。四片叶子的深度分别是 1、2、3、3。给分支标上零和一,就能获得这些长度的前缀码。

加权路径长度说明了这一构造要优化什么。每次合并两棵子树,其中每次符号出现都增加一位编码。把这次额外开销放在较轻的子树上,能让常见叶子靠近根。在没有最大码长等额外限制的二进制前缀码中,Huffman 方法使给定频率的有效载荷加权长度最小。但它不保证整个文件在所有设计中最小:头部、码表描述、匹配选择和格式的码长限制,都还会产生代价。

频率属于正在编码的那一种表示

LZ77 和 Huffman 利用不同规律。LZ77 利用顺序:ABABABAB 中有重复字符串。Huffman 利用符号次数的不均衡。重新排列一段数据,只要次数不变,在同一码表下的 Huffman 有效载荷大小就不变,却可能破坏长匹配。反过来,即使难以找到有用的长重复,只要符号次数足够不均衡,Huffman 仍可能获益。

经过 LZ77 后,Huffman 应描述已经选好的指令,不能再把原来八个字节数一遍。我们的小格式把 0 到 255 号符号留给字面量,256 号表示“后面是匹配”,257 号表示结束。这两个标记编号属于教学格式,DEFLATE 使用不同编号。 匹配标记之后还有距离和长度,我们的简单格式会直接保存这两个数字。结束标记告诉接收者停止读取指令。

对 ABABABAB 已选定的指令序列,Huffman 看见的是 A 一次、B 一次、匹配标记一次、结束标记一次。它不是看见四个 A 和四个 B。四片等权叶子都可以使用两位编码,因此这里的 Huffman 部分没有频率不均衡带来的好处。但 LZ77 已经把重复字节压成了一条复制指令。更长的输入中,如果选出了很多匹配,匹配标记就可能更常见,从而获得更短的码。

这个区别也能避免混淆大小。三条 LZ 指令、包含结束标记的四个 Huffman 符号、八个恢复字节,以及最终数据包的字节数,是四种不同的计数。匹配的距离和长度还要占用额外有效载荷位。下面会把这些开销全部算进去。

发送足够的信息,让接收者重建码表

接收者没有见过原文、原文频率或编码器的树。“使用 Huffman 编码”并没有告诉它 0 代表哪个符号。如果只在编码器内部建好树,然后只发送有效载荷,压缩方法还没有完成。

有两种直接的办法。一种是双方事先约定固定码表,另一种是在包中携带本包所选码表的描述。教学编解码器采用第二种:传输每个已用符号的编码长度,再按双方同意的确定性规则分配编码。接收者不需要原始频率,也不需要知道树是按什么顺序合并出来的。

这个规则叫作规范编码分配。先按码长从短到长排序,同一码长内再按符号编号从小到大排序。第一个符号使用相应位数的全零编码。处理后续符号时,先把前一个编码当作二进制整数加一;如果新码长更长,就在后面补足零。位宽本身是编码的一部分,0 和 00 不是可以互换的写法。

对 P:1、Q:2、R:3、S:3,且符号顺序如上,计算过程是:先得到 0;加一得 1,补一位零成为 10;加一得 3,再补一位零成为 110;再加一成为 111。只要双方使用这条规则,树图中先前怎样选择左右分支就不再重要。

实际例子中,A 的符号编号为 65,B 为 66,匹配标记为 256,结束标记为 257,码长都是二。排序后得到:

符号含义 符号编号 传输的码长 重建的编码
字面量 A 65 2 00
字面量 B 66 2 01
后面是匹配 256 2 10
消息结束 257 2 11

包中的码表只保存编号和码长,最后一列由接收者独立重建。如果另一份输入用到了值为零的字面量,它的编号就是零,也有自己的码表条目。原始字节不会与控制标记混淆,因为标记编号不在 0 到 255 之间。

不是任意码长列表都能组成前缀码。例如,三个长度为一的码无法容纳,因为一位编码只有两种。解码器检查码长范围,检查是否把二叉树填得过满;对多符号码表,这个教学格式还要求完整填满。等价地,把每项的 2^(-码长) 相加,应恰好等于一。四项长度都是二时,结果是 4/4 = 1。单符号情况单独处理:空输入只有结束标记,给它一位长的编码 0。这样不必使用无法在输入中定位的零位编码。

码表自身也有代价。这个刻意简单的表示中,每个已用符号占三个头部字节。很小的自定义码表,可能比它省下的全部有效载荷还大。因此,实用格式必须认真设计码表描述,也要考虑何时改用固定码表。

规定整个包,而不只是有效载荷

现在可以写出一套字节级规则,让另一份实现独立解码。这是编码器与解码器共同约定的教学格式。它的数据包不是 DEFLATE、zlib 或 gzip 数据流,不能交给 zlib 的解码器。交互最多接受 512 个原始字节,也会拒绝声明输出超过 512 字节的数据包,让搜索过程和完整轨迹保持可读。

数据包从字节边界开始,依次包含原始字节数、码表条目数、码表条目和已编码的指令。计数与符号编号都用两字节无符号整数,采用大端顺序,即高字节在前、低字节在后。因此八写成 00 08,256 写成 01 00,257 写成 01 01。

每个码表条目包含两字节符号编号,随后是一字节码长。条目按符号编号递增排列,每个使用的符号恰好出现一次。码长范围为 1 到 32,必须包含结束标记。重建规范码时,可能需要重新按“码长、符号编号”排序,因为传输的条目本身只按符号编号排序。

最后一个条目之后,有效载荷从下一个字节的最高位开始填充,下一位填到紧邻的较低位置。跨过字节边界后,从新字节的最高位继续。这个高位先行的规则同时用于 Huffman 编码和匹配数字。指令之间,以及匹配数字之前,都不插入对齐位。

如果解出的符号在 0 到 255 之间,就追加这个字面量,再读取下一个 Huffman 符号。如果是匹配标记,就精确读取 16 位作为无符号距离,再读取 16 位作为无符号长度;这两个数字不是 Huffman 符号。下一个 Huffman 编码紧接在这 32 位之后。距离必须至少为 1,且不能超过已经生成的输出长度;匹配长度至少为 3。只有读到结束标记才停止。此时,输出长度必须等于头部声明的计数,最后一字节内剩余的位必须全部是零填充。填充位应少于八位,且不得有多余字节。码字被截断、数字被截断、没有结束标记、非法码表、不可能的距离、输出超量,都是错误。

原始字节计数是额外的边界检查,不能代替结束标记。生成八字节之后直接忽略后续指令,会错误接受不合法的包。结束标记决定指令序列在哪里结束,计数检查它展开的长度,填充把最后几位凑成完整字节。这三者的任务不同。

把八字节例子写成包

前面四个条目占十二字节,加上四字节前缀,头部是:

00 08 | 00 04 | 00 41 02 | 00 42 02 | 01 00 02 | 01 01 02
8 字节  4 条目     A:2        B:2       MATCH:2      END:2

有效载荷也已经完全确定:写出 A 的 00、B 的 01、匹配标记的 10、距离 2 的十六位表示、长度 6 的十六位表示,最后写结束标记的 11:

00 | 01 | 10 | 0000000000000010 | 0000000000000110 | 11

共有 2 + 2 + 2 + 16 + 16 + 2 = 40 位,恰好五字节。把同一串位每八位分组,不加入分隔符或对齐位,得到:

00011000 00000000 00001000 00000000 00011011
   18       00       08       00       1b

整个数据包因此有 21 字节:

00 08 00 04 00 41 02 00 42 02 01 00 02 01 01 02 18 00 08 00 1b

八个输入字节变成了 21 个包字节。这个结果应如实保留:指令序列虽然紧凑,却不足以抵消显式码表和宽数字的开销。第一次构造的目的是让每个依赖都看得见。即使表示变大,解码含义仍然明确。只有能计算整个文件,压缩率才成为可以讨论的设计问题。

只用数据包完成解码

现在把原文、频率统计和已选指令都放在一边。给一个新的接收者的只有这 21 字节,以及上面的格式规则。它先读出期望输出长度 8、码表条目数 4,再读四个条目。根据相同的两位码长和符号顺序,重建出 00→A、01→B、10→匹配标记、11→结束标记。

输出一开始为空,有效载荷的位游标从零开始。游标记录已经消费多少个有效载荷位,不是输出位置。Huffman 解码只消费走到叶子所需的位;遇到匹配,暂时改读固定宽度整数,然后再回到同一个 Huffman 树根。

步骤 本步消费的位 随后的有效载荷位游标 动作 输出
1 00 2 追加字面量 A A
2 01 4 追加字面量 B AB
3 10,随后 16 位距离和 16 位长度 38 向后找 2 字节,复制 6 字节 ABABABAB
4 11 40 读到结束标记,检查长度和填充 ABABABAB

第三步的数字读取会跨过字节边界。如果按“接下来的两个字节”读取,就错了:距离起始于有效载荷已经消费六位的位置,并没有对齐字节。位读取器必须保留游标,逐位收集十六位。收到的数字仍然是 2;把它写作 00 02 只是说明它在字节对齐时的数值表示,不意味着可以跳到下一个字节再读。

匹配严格按照先前表格中的六次依赖复制展开。此时长度已经达到八,接收者仍要继续读结束标记。游标最终等于 40,没有剩余填充位或多余字节,于是接受数据包,返回恢复的八字节。整个过程不需要向编码器索取树,也不需要查看原文来选择匹配。

下面的伪代码展示一种解码组织方式。readSymbol 从树根出发,用当前位游标沿规范码分支走到叶子;readBits(16) 按约定的位序读取无符号整数。进入循环前,头部解析已经构造好码表;最后的检查确认结束标记之后只剩允许的零填充。

output = []
重复:
    symbol = readSymbol(book)
    如果 symbol == END:退出循环
    如果 symbol < 256:把 symbol 追加到 output
    否则:
        distance = readBits(16)
        length = readBits(16)
        检查 1 <= distance <= output.length 且 length >= 3
        重复 length 次:追加 output[output.length - distance]
    检查 output.length <= expectedLength
检查 output.length == expectedLength
检查剩余部分只有到下一个字节边界的零填充

每次读取还必须在位不足时报错,而码表已经排除了字面量、匹配标记、结束标记以外的编号。循环之所以短,是因为格式已经消除了歧义:标记决定下一步解析什么,前缀码决定符号边界,固定宽度决定数字边界,结束标记决定消息何时完成。

修改输入,查看每一层表示

下面的交互运行独立编写的教学编码器,以及只接收序列化数据包的另一套解码过程。指令轨迹按原有顺序列出字面量和匹配;码表显示传输的码长与重建的编码;数据包视图显示真正交给解码器的字节;解码轨迹显示位游标和恢复输出怎样前进。“编码并从头查看”会从可编辑输入重新生成这些视图。“下一步”依次查看指令、码表、数据包和接收端写入;“上一步”或位置滑块可以回看这次已完成运行的先前步骤。

先用 ABABABAB,再试 ABCABC,比较没有重叠的匹配;或者输入 AAAAAAAA,观察距离 1。十六进制输入能表示任意字节值,每两位数字提供一个字节。空输入仍然需要包含结束标记的码表,以及它的一位有效载荷编码。也可以试试彼此无关的字节:即使找不到有用匹配,头部开销仍然存在。

输入 ABABABAB 时,教学编码器选择字面量 A、字面量 B 和距离 2、长度 6 的匹配。规范码表为 A=00、B=01、匹配标记=10、结束标记=11。数据包的 21 字节是 00 08 00 04 00 41 02 00 42 02 01 00 02 01 01 02 18 00 08 00 1b。接收者从传输的四个码长重建码表,读出两个字面量和匹配的两个十六位数字,按顺序复制得到 ABABABAB,最后在有效载荷第 40 位消费完结束标记。这些字节属于教学格式,不是 DEFLATE。

基本编解码器到这里已经闭合:原始字节变成指令,指令变成可独立解码的数据包,数据包再变回原始字节。理解这个完整转换,不需要先加入流式传输、文件接口或校验和。这些功能解决额外的实际问题,而不是替前面的构造补上一张缺失的码表。

对照真正的 DEFLATE

zlib 是实现压缩与解压缩的库,核心压缩数据格式叫作 DEFLATE。在 zlib 的命名中,deflate 是压缩器,inflate 是解码器。原文仍然是一串字节;匹配搜索仍然把它变成按顺序排列的字面量和回退复制指令。接下来改变的是,这串指令怎样写进实际发送的字节。

DEFLATE 把一条流分成若干块,每个块为其中的数据选择一套表示规则。先看一个使用 Huffman 编码的块:读取这一个块期间,它的一对码表保持不变。后面再展开它的头部,以及其他块的形式。

先把一直使用的例子放在眼前:

原文:  A B A B A B A B
指令:  字面量 A,字面量 B,匹配(长度 6,距离 2)

教学格式用一个通用的 MATCH 码字标记匹配,再附上两个较宽的整数。DEFLATE 把这部分表示做得更紧凑:长度和距离各自分组,再对两种分组分别进行 Huffman 编码。我们先把码表画出来,走通这串指令的读取过程,然后再说明接收者怎样从块中获得这些码表。

两个字母表表示匹配的数字

先看要编码的对象。每个字面量提供一个字节值。每个匹配提供两个用途不同的数字:要产生多少字节,以及到多远之前寻找来源。块结束标记则说明这块的指令已经结束。这些对象在指令序列中的顺序已经确定,Huffman 编码负责给它们安排位表示。

DEFLATE 把这些符号放进两个字母表,也就是两个可编码的符号集合。字面量/长度字母表包含字面量、块结束标记和长度分组。距离字母表包含距离分组。每个集合都有自己独立的 Huffman 树;把树中每个叶子的名称与从根走到它的零、一分支记下来,就得到这棵树的码表。这里的表列出符号与码字的对应关系;下一篇解码优化中的快速查找表,是用数组加速走树的另一种实现。

为什么把字面量与长度放在一起?因为每条新指令开始时,接收者首先要决定追加一个字节,还是执行一次匹配。解出长度分组,就同时知道“这是一条匹配”及其长度的一部分,替代了教学格式中通用 MATCH 标记的作用。距离则只在已经读到长度之后才需要,所以可以在另一棵树中独立编码。Huffman 方法本身允许我们设计多种字母表,这一对字母表是 DEFLATE 选择的解析组织方式。

构造动态块时,编码器分别统计这两类符号的出现次数,为每一类建立自己的码表。

在八字节例子中,第一个集合收到四次符号:字面量 A、字面量 B、长度 6、块结束。第二个集合只收到一次:距离 2。每个匹配给第一个集合贡献一个长度符号,给第二个集合贡献一个距离符号。字面量和块结束只进入第一个集合。输入更长时,许多匹配可能都使用距离 1,长度却各不相同;这两类符号的频率分布就会明显不同。

LZ77 选好的记录

A · B · 匹配(6,2)

记录仍按原有顺序排列。
按符号的用途计频

字面量/长度:A、B、长度 6、结束

距离:距离 2

写入一个有效载荷

A 的码 · B 的码 · 长度码 · 距离码 · 结束码

两张码表共用一个向前移动的位游标。
编码器会追加一个块结束标记。分开的符号集合决定各自的码字。原有指令顺序决定这些码字在同一串传输位中出现的位置。

符号编号把这些用途确定下来。在字面量/长度字母表中,0–255 号表示字面量字节,256 号表示块结束,257–285 号选择长度分组,覆盖长度 3–258。在距离字母表中,0–29 号选择距离分组,覆盖距离 1–32768。所以编号要连同所属字母表一起理解:字面量/长度符号 65 表示字节 A,距离符号 1 表示距离 2,后者不会把值为 1 的字节追加到输出。

指令中的部分 使用的字母表 本例的符号编号
追加 A 字面量/长度 65
追加 B 字面量/长度 66
用复制产生 6 个字节 字面量/长度 260
从向后 2 个字节的位置开始复制 距离 1
结束这一个块 字面量/长度 256

暂时让收发双方都拿到下面两张合法码表。四个用到的字面量/长度符号按编号分别获得两位码字。距离表只有一个实际使用的符号,给它一位码字 0。只有一个符号的距离表仍要消费一位,不会变成零位指令。这里选定这组合法码长,使两棵树足够小,便于看清格式;下一篇再展开 zlib 的构造器如何选择码长及计算代价。后面会用动态块头完整地构造出这一对码表。

字面量/长度树
010101根··6566256260

叶子编号对应上表的 A、B、块结束、长度 6。

距离树
01根1×

叶子编号 1 表示距离 2,× 表示未分配的分支。读出长度后,才进入这棵树。

每棵树都有自己的根。沿边上的位从根走到叶子,得到这个符号的码字。字面量/长度树决定下一条指令,距离树补全一条已经开始的匹配。

使用这两张码表,有效载荷只需九位:

00  | 01  | 11     | 0      | 10
A     B     长度 6   距离 2   结束

实际传输的仍然是一串连续的位,解码器只有一个向前移动的游标。先从字面量/长度树的根读 00,追加 A;再从同一个根读 01,追加 B。接着在这棵树中读到 11,知道下一条是匹配,先记住长度 6,再切换到距离树的根。在距离树读 0,得到距离 2。两个数字都齐了,执行六次逐字节复制。随后回到字面量/长度树的根,读 10,结束这个块。

解码器在读取一个码字之前,就已经知道要使用哪棵树。当前任务决定根的位置:读到长度后,任务变为“读取距离”;匹配完成后,任务变回“读取下一个字面量、长度或结束”。无需在每个码字前额外插入“选择哪张表”的标志。格式的解析规则已经提供了这个信息。因此,距离码字 0 可以与以零开头的字面量/长度码字同时存在。

分组缩短数字,额外位补全数值

刚才的长度 6 和距离 2 各自占有一个分组,Huffman 符号已经确定了完整数字。较大的数值经常共用一个分组。这样就能控制字母表的大小,无需给每个可能的长度、距离都单独安排一个符号。

每组规定两个固定事实:一个基础值,以及后面紧跟多少个原始额外位。接收者先解出一个 Huffman 符号来选择分组,再把指定数量的额外位读成无符号整数,加到基础值上。分组规则由 DEFLATE 事先规定;用来选择这些分组的 Huffman 码字则可以随块改变。

种类 符号 基础值 额外位数量 表示的数值
长度 260 6 0 6
长度 265 11 1 11–12
长度 266 13 1 13–14
距离 1 2 0 2
距离 4 5 1 5–6
距离 5 7 1 7–8

假设接收者已经输出了 ABCDEF,现在要执行一条长度 12、距离 6 的匹配。它会追加 ABCDEFABCDEF,使全部输出变成 ABCDEFABCDEFABCDEF。这条指令的表示分为四步:

  1. 从字面量/长度表解出符号 265。这一组的基础长度为 11,要求一位额外位。
  2. 直接把随后这一位读成数值 1,得到长度 11 + 1 = 12。
  3. 从距离表解出符号 4。这一组的基础距离为 5,要求一位额外位。
  4. 直接把随后这一位读成数值 1,得到距离 5 + 1 = 6。

这两个额外位直接进入整数读取过程,不沿任何一棵 Huffman 树行走。四步提供了两个完整数字之后,解码器复制十二个字节,再回到字面量/长度树的根。遇到额外位数量为零的组,整数读取过程不消费任何位,补充的数值就是零。

这里要区分两种“表”。Huffman 码表把变长码字对应到符号;分组表把该符号对应到基础值和额外位数量。先通过码表回答“是哪一个符号”,再通过格式固定的分组规则回答“完整数字是多少”。zlib 的 inftrees.c 中的基础值与额外位数组实现的是第二层对应关系,不是在描述当前 Huffman 树。本文的源码链接指向上游 zlib 提交 757f0527。本项目所验证的源码是它的子提交 99623ef7(zlib 1.4)加上本项目的补丁。在链接所指的各行中,两者只有一处不同:长度额外位数组的最后两项,这两项属于非法的长度符号 286 和 287。

下面的交互把两张码表摆在同一个位游标旁边。先走八字节例子,再选择长度 12/距离 6 的匹配。依次读取字面量/长度码字、原始长度额外位、距离码字、原始距离额外位。当前树根和当前字段的高亮会说明,每一段位为什么按这样的方式解释。第二个例子从已经拥有 ABCDEF 的状态开始,并提供另一对小码表:长度符号从 260 换成 265,距离符号从 1 换成 4。它专门展开这条匹配,不再重新传输这个前缀。

DEFLATE 使用一个有效载荷游标和两张 Huffman 码表。在 A、B、长度 6/距离 2、块结束这串指令中,字面量/长度表提供 A、B、长度 6 和结束;距离表提供距离 2。读到长度后,先读取它的原始额外位,再读取一个距离符号及其原始额外位,按两个完整数字执行复制,然后回到字面量/长度表。长度 12/距离 6 则先用符号 265 加原始额外值 1 得到长度 12,再用距离符号 4 加原始额外值 1 得到距离 6,把已有的 ABCDEF 延长为 ABCDEFABCDEFABCDEF。

编码器也遵循这个顺序。匹配搜索已经给出长度和距离,compress_block把它们依次转成长度符号与额外位、距离符号与额外位。解码器反过来恢复这些表示,并执行匹配,无需重新进行编码器做过的匹配搜索。

块先说明码表从哪里获得

我们已经用两张码表读通了有效载荷。接收者还需要知道这次该拿哪两张表。DEFLATE 在块的边界提供这个信息。一条流包含一个或多个相接的块,每个块先声明后续数据采用哪种表示。

开头的一位说明它是否为最后一块,接着两位说明块的形式。固定 Huffman 块选择格式规定的两张码表;动态 Huffman 块先传输描述,由接收者重建两张表;原样存储块直接提供原文字节。这两位表示的数值为 0 时采用原样存储,为 1 时采用固定码表,为 2 时采用动态码表,为 3 时保留,解码器遇到保留值就报错。

读取三位块头

最后块标志 + 块的形式

获得这个块的表示

固定:使用约定码表

动态:先重建码表

原样:读取指定数量的字节

完成这一个块

恢复出的字节追加到同一份输出。

除非最后块标志已置位,否则继续读取下一个块头。
块边界改变后续输入位的解释方式。已经恢复的输出仍然可以成为后来匹配的来源。

所以这里要识别两种边界。块结束符号结束当前这块的 Huffman 指令序列;最后块标志说明它结束后是否还要读取下一块。后一个块的匹配可以使用前一个块产生的字节,即使两个块使用不同的码表。码表负责解释压缩位,保留的输出负责提供匹配字节;这两类对象有不同的有效范围。

固定块直接取得两张约定码表

固定块使用格式内置的码长。字面量/长度树由下面四段编号的码长构造:

符号位置 这些位置的含义 码长
0–143 前一部分字面量值 8
144–255 其余字面量值 9
256–279 块结束与一部分长度分组 7
280–287 其余长度位置,包含保留的 286–287 8

把前面讲过的规范编码分配用在这些位置上,收发双方就得到同一棵树。例如 A 的编号为 65,获得 01110001;B 获得 01110010;块结束符号 256 获得 0000000;长度 6 的符号 260 获得 0000100。286、287 号在约定树中占有位置,但不能表示合法长度。

固定距离树有 32 个位置,每个位置的码长都为 5。它的规范码字就是符号编号的五位表示:距离符号 1 为 00001,符号 4 为 00100。30、31 号保留,不能用来提供匹配距离。固定块只需三位块头就选定了这两棵树,无需另外携带码长列表。

留意这些固定码字与刚才四叶子例子的区别。字面量/长度符号 260 的含义仍然是长度 6,但它的写法现在是 0000100,先前则是 11。原因是这个块选择了另一张码表。符号含义与符号的码字属于不同层次。

动态块先重建两张数据码表

动态块可以为数据选择码表,所以接收者要先获得这些码表的描述。选择最后块标志为 1、块形式的数值为 2,再来构造九位例子中使用的那一对:A、B、块结束、长度 6 的码长都是 2;唯一使用的距离符号码长为 1。

接收者需要知道每个码长属于哪个符号。DEFLATE 传输的是按符号编号排列的码长数组。从零号到声明的最后一个位置,每个位置都有一个码长;没有使用的符号填零。所以,实际使用四个叶子,并不意味着数组只有四个位置:

字面量/长度位置: 0 … 64 | 65 | 66 | 67 … 255 | 256 | 257 … 259 | 260
对应码长:        0 …  0 |  2 |  2 |  0 …   0 |   2 |   0 …   0 |   2

距离位置:        0 | 1
对应码长:        0 | 1

本例需要的最大字面量/长度编号为 260,因此这部分数组有 261 个位置,编号为 0–260。最大距离编号为 1,因此距离数组有两个位置。恢复这些码长后,分别对两个数组进行规范编码分配,就得到 A=00、B=01、结束=10、长度 6=11,以及距离 2=0。

怎样传输这 263 个码长,又不让每个零都占用一整个字节?DEFLATE 先把两个数组接成一串码长,再压缩这串数字。于是引入一个较小的描述字母表,其中的符号描述单个码长,或者重复的码长。它使用第三棵 Huffman 树,只在读取块头时工作。它解出的数字用来填充两张数据码表的码长数组,不会追加原文字节。

这棵额外的树也需要描述,而且这份描述必须在还没有树时就能读懂。DEFLATE 的做法是,把这个小字母表的码长直接写成三位整数。这就给依赖关系找到了起点:

原始三位码长

无需任何 Huffman 树,直接读取。

描述用的树

解码并展开出 263 个数据码长。

两棵数据树

取前 261 个码长作为一组,再分别建树。

原来的指令

用字面量/长度表和距离表解出有效载荷。

块头中临时使用的树负责描述后面的两棵树。原始码长先把它建立起来,因此没有任何一棵树需要先描述自己。

描述字母表共有 19 个符号。0–15 号表示“追加一个数值等于编号的码长”。16 号把前一个码长重复 3–6 次,用两位原始额外位选择次数。17 号插入 3–10 个零,用三位额外位选择次数。18 号插入 11–138 个零,用七位额外位选择次数。接收者不断追加,直到恰好得到声明的两个数组长度之和。一次重复可以跨过最后的数组分界,全部展开后再进行切分。

为这个例子选择下面这张合法的描述码表:

描述符号 它的码字 解出它之后的动作
2 0 追加一个值为 2 的码长
18 10 读七位额外位,追加“11 加额外值”个零
17 110 读三位额外位,追加“3 加额外值”个零
0 1110 追加一个零码长
1 1111 追加一个值为 1 的码长

描述符号 2 自己用一位 0 编码,解出它却会向数据码长数组写入数字 2。描述符号、这个符号自己的码长、它的码字,以及它产生的数据码长,是四个不同的对象。把这些对象摆在一起,“对码长编码”才不再隐藏一层转换。

下面十个描述符号就能恢复全部 263 个位置。额外值一栏写的是数值;接下来再说明数字字段和 Huffman 码字怎样放入实际字节。

描述符号 原始额外值 追加的码长 这步之后已有多少个码长
18 54 65 个零 65
2 无 一个 2:字面量 A 的码长 66
2 无 一个 2:字面量 B 的码长 67
18 127 138 个零 205
18 40 51 个零 256
2 无 一个 2:块结束符号的码长 257
17 0 3 个零 260
2 无 一个 2:长度 6 符号的码长 261
0 无 一个零:距离符号 0 不使用 262
1 无 一个 1:距离符号 1 的码长 263

计数达到 261 时,字面量/长度数组已经完整;最后两个值组成距离数组。接收者分别构造两张规范码表,现在就能把 00 | 01 | 11 | 0 | 10 还原成那八个原文字节。块头只需提供码长,不必提供原文的频率统计;选好的指令已经表示在随后的有效载荷里,无需另附一份匹配记录数组。

要把这份块头描述也闭合,还需要交代它自己的计数和小码表。三位块头之后,DEFLATE 按下面的顺序提供这些信息:

字段 读取规则 本例的数值
字面量/长度位置数 五位数值加 257 4 + 257 = 261
距离位置数 五位数值加 1 1 + 1 = 2
接下来提供多少个描述码长 四位数值加 4 14 + 4 = 18
这些描述码长 按约定符号顺序,每个直接占三位 共 18 个码长,见下方

257 的下界保证数组包含块结束符号所在的 256 号位置。描述字母表则采用一个固定顺序,把有用的重复符号放在前面:

符号顺序: 16,17,18, 0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
本例码长:  0, 3, 2, 4,0,0,0,0, 0,0, 0,0, 0,0, 0,1, 0,4

这里只提供前 18 个码长。最后没有提供的 15 号位置,码长默认为零。现在做规范编码分配,就重建出前面那张五行的描述码表,再由它的符号展开 263 个数据码长。距离位置数字段能表示 1–32 个位置,其中距离符号 30、31 保留;选定默认 zlib 解码器会拒绝大于 30 的位置数,本例两个位置使用它的普通路径。实际 inflate.c 的 TABLE、LENLENS 和 CODELENS 阶段正按这个依赖顺序读计数、建立描述码表,再恢复两张数据码表。

下面的交互会把整条构造过程走一遍。先前进到描述树出现,再展开连续的零,看码长数组怎样逐段填满。在 261 处分开,就得到有效载荷使用的两张码表。直到这一步完成,同一个位游标才开始把后面的九位解释成真正的原文指令。

这个动态块声明 261 个字面量/长度位置和两个距离位置。先直接读取三位码长,建立临时的描述树:符号 2 的码字为 0,18 为 10,17 为 110,0 为 1110,1 为 1111。十个描述符号展开出 263 个码长:字面量/长度数组在 65、66、256、260 号位置的码长为 2,距离数组为 [0,1]。分别规范化后,A=00、B=01、结束=10、长度 6=11、距离 2=0。有效载荷 00|01|11|0|10 因而还原为 ABABABAB。完整的十六字节流为 25 c1 31 11 00 00 00 40 c0 6c f4 0f 65 70 8f 0b。

这份选定的块头占 116 位:3 位块头字段、14 位计数、54 位原始描述码长,以及 45 位压缩后的 263 项码长描述。再加九位有效载荷和最后补齐的三位零,总共十六字节:

25 c1 31 11 00 00 00 40 c0 6c f4 0f 65 70 8f 0b

有效载荷变短了,描述却更长。本例完整的动态表示,比下面的五字节固定块更大,而两者恢复出的原文相同。要比较完整块的成本,不能只比较有效载荷的码长;这会成为下一篇文章里的一项优化问题。

块头解析也会先检查表示是否合法,再使用它:提供的码长必须能组成格式接受的前缀码,重复次数不能超出声明的总数,符号 16 必须已有前一个码长可供重复。字面量/长度表要包含块结束符号,数据码长不得超过 15。随后解码有效载荷时,解出保留符号、缺少必需的输入位,或者匹配没有可用来源,都应当报错;接收者不会靠猜测码表或来源字节来修补这样的流。

原样块直接表示字节

有些数据在编码上付出的开销会超过收益。原样存储块为它们提供直接的表示。读完三位块头,先跳到下一个字节边界;然后读取一个十六位字节数,再读一个把该数字每一位取反的十六位数,等价于 65535 − 字节数。这两个字段都先放低字节。检查两者吻合后,直接复制指定数量的原文字节。

字节数确定这个块何时结束,所以原样块没有 Huffman 有效载荷,也没有编码后的块结束符号。它产生的字节仍然扩展输出,可以供后来匹配引用。长度取反字段能检查长度声明是否一致,不能据此判断原始内容是否就是发送者想要的内容。端到端的内容校验会作为第三篇文章中的一项功能展开。

用真正的固定块恢复同样八个字节

回到固定码表,以及同一串指令:字面量 A、字面量 B、长度 6/距离 2、块结束。第一个字段选择“最后一个固定块”。下表的码字按照 Huffman 树遇到各位的顺序书写,左边第一个字符最先被读取:

字段 含义 按读取顺序排列的位
头部 最后块标志为 1,固定类型为 1 1,然后 1 0
字面量/长度码字 字面量 A,符号 65 01110001
字面量/长度码字 字面量 B,符号 66 01110010
字面量/长度码字 长度 6,符号 260 0000100
距离码字 距离 2,符号 1 00001
字面量/长度码字 块结束,符号 256 0000000

长度 6 与距离 2 都不需要额外位。有效位总数为 3 + 8 + 8 + 7 + 5 + 7 = 38。距离码字仍由它自己的树解释;块头没有把两张码表合成一张。

现在把这些位放进字节。每个字节的位置编号为 0–7,0 号位贡献数值 1,7 号位贡献数值 128。DEFLATE 先填 0 号位,再填 1 号位,直到 7 号位,再继续下一个字节的 0 号位。通常把字节打印成二进制时,却把 7 号位放在最左边。所以,填入一个字节的顺序,与纸上显示这八位的顺序相反。

最先到达的八位为 1 1 0 0 1 1 1 0:三位块头,接着是 A 码字的前五位。把它们放进下面的位置:

字节中的位号76543210
第几个到达87654321
存入的位01110011
按 7 号位到 0 号位打印最后一行,得到 01110011,也就是十六进制 73。解码时从 0 号位向上取位,就恢复了原先的到达顺序。

继续填入,不在字段之间补齐。A 剩下的三位与 B 的开头共用第二个字节。38 个有效位全部放完后,最后一个字节还剩两个位置,填入两位零。完整的原始 DEFLATE 流为:

73 74 82 40 00

还要区分字段本身的位序。多位数字字段先提供低位,例如数值为 1 的块类型先读 1,0,得到 1 + 0 × 2 = 1。Huffman 码字则按规范码字的顺序提供位,例如 A 依次遇到 0,1,1,1,0,0,0,1。这两类字段都把位写入同样的、从低到高的字节位置;区别在于每个字段按什么顺序提供这些位。所以不能把每段打印出的二进制一律反转。

现在,一个全新的解码器已经拥有完成工作的全部信息。位读取器先提供三位块头,选择固定码表。在字面量/长度树,它读出 A、B,再读出长度 6;在距离树,它读出距离 2。执行六次前后依赖的逐字节复制,再回到字面量/长度树读块结束符号。最后块标志说明后面没有下一块。只凭这串输入和格式规则,它就从五个压缩字节恢复出了八个原文字节。

这是人为选定的一种合法编码。zlib 某次实际压缩可能选择另一条合法匹配或另一种块。接收者只需要遵循输入中实际表示的选择,无论它由哪一个合法编码器产生。

实际解码器用移动指针表示同一件复制工作。在直接从已有输出复制的分支,put 指向下一个输出字节,state->offset 保存解出的距离。源起点位于 put 向后这个距离的位置;from 表示它当前的位置,copy 记录本段还要追加多少字节。inflate.c 的核心复制循环保留了先前推导的逐字节含义:

            do {
                *put++ = *from++;
            } while (--copy);

一次迭代把一个源字节写到目标位置,并推进两个指针。循环先前写出的字节,可以在后续迭代中成为来源,与距离 2 的表格完全相同。即使高效解码器每次处理几个字节,也必须保留这个含义。

先提高效率,再扩展任务

基本过程现在已经完整:编码器选择字面量和匹配,为得到的符号编码,提供或指定码表,并确定消息边界;解码器重建码表,解析实际收到的位,从自己的输出展开匹配,再识别完成。接收者独立工作之前,每一项都不可缺少。

下一步是效率。逐个搜索所有先前位置很费时;尝试更多匹配可能改善压缩率,也会花更多时间。自定义码表能缩短有效载荷,却可能让小块整体变大。每读一位就沿树走一条边的解码器容易理解,但其中一些工作可以用查表省掉。下一篇关于时间、内存与压缩率的文章从这套完整编解码器出发,推导 deflate 和 inflate 两侧的取舍。

之后,第三篇实用功能文章再扩展任务:分批接受输入,在输出空间有限时暂停并继续,要求刷新边界,复用字典,以及给 DEFLATE 加上 zlib 或 gzip 封装,用 Adler-32 或 CRC-32 检查恢复出的字节。这些功能建立在这里已经说明的字节转换之上,让相同的压缩机制适应不同应用的交付、复用与完整性需求。

ZLIB × LEAN

目录

正在阅读基础压缩:LZ77 与 Huffman