4. Entropy Encoding (熵编码)

Zstandard 格式使用两种类型的熵编码: FSE 和 Huffman 编码。Huffman 用于压缩字面量 (Literals), 而 FSE 用于所有其他符号 (Literals_Length_Code、Match_Length_Code 和 offset codes) 以及压缩 Huffman 头部。

4.1 FSE (有限状态熵)

FSE, 即 Finite State Entropy (有限状态熵) 的缩写, 是一种基于 [ANS] 的熵编解码器。FSE 编码/解码涉及在符号之间传递的状态 (State), 因此解码必须以与编码相反的方向完成。因此, 所有 FSE 位流 (Bitstreams) 都从末尾到开头读取。请注意, 流中位的顺序不会反转; 它们只是以与写入时相反的顺序读取。

有关 FSE 的其他详细信息, 请参见 "FiniteStateEntropy" [FSE]。

FSE 解码涉及一个解码表 (Decoding Table), 该表具有 2 的幂次方大小, 并包含三个元素: Symbol (符号)、Num_Bits (位数) 和 Baseline (基线)。表大小的以 2 为底的对数是其 Accuracy_Log (精度对数)。FSE 状态值表示此表中的索引。

要获得初始状态值, 从流中以小端值 (Little-endian Value) 消耗 Accuracy_Log 位。流中的下一个符号是该状态在表中指示的 Symbol。要获得下一个状态值, 解码器应从流中以小端值消耗 Num_Bits 位, 并将其添加到 Baseline。

4.1.1 FSE Table Description (FSE 表描述)

要解码 FSE 流, 必须构造解码表。Zstandard 格式按此处所述对 FSE 表描述进行编码。

FSE 分布表 (Distribution Table) 描述了从 0 到最后一个出现的符号 (包含) 的所有符号在归一化尺度 (1 << Accuracy_Log) 上的概率。请注意, 必须有两个或更多具有非零概率的符号。

位流以小端方式向前读取。没有必要知道其确切大小, 因为大小将由解码过程发现和报告。位流首先报告它操作的尺度。如果 low4bits 指定第一个字节的最低 4 位, 则 Accuracy_Log = low4bits + 5。

随后是从 0 到最后一个出现的符号的每个符号值。每个字段使用的位数是可变的, 取决于:

剩余概率 + 1 : 例如, 假设 Accuracy_Log 为 8, 并且假设已经分配了 100 个概率点, 解码器可以读取从 0 到 (256 - 100 + 1) == 157 (包含) 的任何值。因此, 它必须读取 log₂(157) == 8 位。

解码值 : 小值使用少 1 位。例如, 假设可能的值从 0 到 157 (包含), 255 - 157 = 98 个值在 8 位字段中保留。前 98 个值 (因此从 0 到 97) 仅使用 7 位, 而从 98 到 157 的值使用 8 位。这是通过表 20 中的方案实现的:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

表 20: 解码值

符号概率按顺序逐个读取。概率从解码值 (Value Decoded) 使用公式 P = Value - 1 获得。这意味着值 0 变成负概率 -1。这是一个特殊概率, 意味着 "小于 1"。它对分布表的影响如下所述。为了计算总分配概率点, 它计为 1。

当符号的概率为零时, 后面跟着一个 2 位重复标志 (Repeat Flag)。此重复标志告诉有多少个零概率跟随当前的概率。它提供从 0 到 3 的数字。如果是 3, 则后面跟着另一个 2 位重复标志, 依此类推。

当最后一个符号达到累积总和 (1 << Accuracy_Log) 时, 解码完成。如果最后一个符号使累积总和超过 (1 << Accuracy_Log), 则分布被认为已损坏。

最后, 解码器可以知道在此过程中使用了多少字节以及存在多少符号。位流消耗整数字节。最后一个字节中的任何剩余位都未使用。

使用表的上下文指定预期的符号数量。该预期符号数量不超过 256。如果解码的符号数量不等于预期数量, 则应将头部视为损坏。

归一化概率的分布足以创建唯一的解码表。表的大小为 (1 << Accuracy_Log)。每个单元格描述解码的符号和获取下一个状态的指令。

符号按其自然顺序扫描如上所述的 "小于 1" 概率。具有此概率的符号被分配一个单元格, 从表的末尾开始并后退。这些符号定义完全状态重置 (Full State Reset), 读取 Accuracy_Log 位。

所有剩余符号按其自然顺序分配。从符号 0 和表位置 0 开始, 每个符号被分配与其概率一样多的单元格。单元格分配是分散的, 而不是线性的; 每个后继位置遵循此规则:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

如果位置已被 "小于 1" 概率符号占据, 则跳过该位置。位置在符号之间不重置; 它只是遍历表中的每个位置, 当为当前符号分配了足够的状态时切换到下一个符号。

结果是状态值列表。每个状态将解码当前符号。

要获取下一个状态所需的 Number_of_Bits 和 Baseline, 首先需要按其自然顺序对所有状态进行排序。较低的状态将需要比较高状态多 1 位。对每个符号重复此过程。

例如, 假设一个符号的概率为 5, 它接收五个状态值。状态按自然顺序排序。下一个 2 的幂是 8。概率空间被分为 8 个相等的部分。假设 Accuracy_Log 为 7, 这定义了 128 个状态, 每个份额 (除以 8) 的大小为 16。为了达到 8, 8 - 5 = 3 个最低状态将计数 "双倍", 将份额数量加倍 (宽度为 32), 在此过程中需要多 1 位。

Baseline 从使用较少位的较高状态开始分配, 然后自然进行, 然后从第一个状态恢复, 每个状态从 Baseline 获取其分配的宽度。

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

表 21: Baseline 分配

下一个状态通过读取所需的 Number_of_Bits 并添加指定的 Baseline 从当前状态确定。

有关应用于默认分布的此过程的结果, 请参见附录 A。

4.2 Huffman Coding (哈夫曼编码)

Zstandard Huffman 编码流向后读取, 类似于 FSE 位流。因此, 要找到位流的开始, 必须知道 Huffman 编码流最后一个字节的偏移量。

在写入包含信息的最后一位后, 压缩器写入一个 1 位, 然后用 0 位填充字节的其余部分。因此, 压缩位流的最后一个字节不能为 0。

解压缩时, 包含填充的最后一个字节是要读取的第一个字节。解压缩器需要跳过多达 7 位的 0 填充以及出现的第一个 1 位。之后, 位流的有用部分开始。

位流以小端方式包含 Huffman 编码的符号, 代码由以下方法定义。

4.2.1 Huffman Tree Description (哈夫曼树描述)

前缀编码 (Prefix Coding) 通过位序列 (码字) 表示先验已知字母表中的符号, 每个符号一个码字, 以这样一种方式, 不同的符号可以由不同长度的位序列表示, 但解析器总是可以明确地逐个符号解析编码字符串。

给定具有已知符号频率的字母表, Huffman 算法允许使用该字母表所有可能前缀代码中最少位数构造最优前缀代码。

前缀代码不得超过最大代码长度。更多位提高准确性, 但产生更大的头部大小并需要更多内存或更复杂的解码操作。本规范将最大代码长度限制为 11 位。

从零 (包含) 到最后一个出现的字面值 (不包含) 的所有字面值由值从 0 到 Max_Number_of_Bits 的 Weight (权重) 表示。从 Weight 到 Number_of_Bits 的转换遵循此伪代码:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

最后一个符号的 Weight 从先前解码的符号推导出来, 通过完成到最近的 2 的幂。这个 2 的幂给出 Max_Number_of_Bits, 即当前树的深度。

例如, 假设必须描述以下 Huffman 树:

+===============+================+
| Literal Value | Number_of_Bits |
+===============+================+
|       0       |       1        |
+---------------+----------------+
|       1       |       2        |
+---------------+----------------+
|       2       |       3        |
+---------------+----------------+
|       3       |       0        |
+---------------+----------------+
|       4       |       4        |
+---------------+----------------+
|       5       |       4        |
+---------------+----------------+

表 22: Huffman 树

树深度为 4, 因为其最长元素使用 4 位。(最长元素是那些频率最小的元素。) 值 5 不会被列出, 因为它可以从值 0-4 确定, 值 5 以上的值也不会被列出, 因为它们都是 0。从 0 到 4 的值将使用 Weight 而不是 Number_of_Bits 列出。确定 Weight 的伪代码是:

if Number_of_Bits == 0:
    Weight = 0
else:
    Weight = Max_Number_of_Bits + 1 - Number_of_Bits

它给出以下权重系列:

+===============+========+
| Literal Value | Weight |
+===============+========+
|       0       |   4    |
+---------------+--------+
|       1       |   3    |
+---------------+--------+
|       2       |   2    |
+---------------+--------+
|       3       |   0    |
+---------------+--------+
|       4       |   1    |
+---------------+--------+

表 23: 权重

解码器将执行相反的操作: 收集了从 0 到 4 的字面量权重后, 它知道最后一个字面量 5 存在且具有非零 Weight。5 的 Weight 可以通过前进到下一个 2 的幂来确定。2^(Weight-1) 的总和 (不包括 0) 为 15。最近的 2 的幂是 16。因此, Max_Number_of_Bits = 4 且 Weight[5] = 16 - 15 = 1。

4.2.1.1 Huffman Tree Header (哈夫曼树头部)

这是一个单字节值 (0-255), 描述权重系列的编码方式。

headerByte < 128 : 权重系列使用 FSE 压缩 (见下文)。FSE 压缩系列的长度等于 headerByte (0-127)。

headerByte >= 128 : 这是直接表示, 其中每个 Weight 直接写为 4 位字段 (0-15)。它们向前编码, 每字节 2 个权重, 第一个权重占据高 4 位, 第二个占据低 4 位; 例如, 可以使用以下操作读取权重:

Weight[0] = (Byte[0] >> 4)
Weight[1] = (Byte[0] & 0xf)
// 等等

完整表示占用 ceiling(Number_of_Symbols/2) 字节, 这意味着即使 Number_of_Symbols 是奇数, 它也只使用完整字节。Number_of_Symbols = headerByte - 127。请注意, 最大 Number_of_Symbols 为 255 - 127 = 128。如果任何字面量的值超过 128, 则原始头部模式不可能, 必须使用 FSE 压缩。

4.2.1.2 FSE Compression of Huffman Weights (Huffman 权重的 FSE 压缩)

在这种情况下, Huffman 权重系列使用 FSE 压缩进行压缩。它是具有两个交错状态的单个位流, 共享一个分布表。

要解码 FSE 位流, 必须知道其压缩大小。压缩大小由 headerByte 提供。还需要知道其最大可能解压缩大小, 即 255, 因为字面值从 0 到 255, 并且不表示最后一个符号的 Weight。

FSE 位流以头部开始, 描述概率分布。它将创建解码表。对于 Huffman 权重列表, 最大精度对数为 6 位。有关更多详细信息, 请参见第 4.1.1 节。

Huffman 头部压缩使用两个状态, 它们共享相同的 FSE 分布表。第一个状态 (State1) 编码偶数索引符号, 第二个 (State2) 编码奇数索引符号。State1 首先初始化, 然后 State2, 它们轮流解码单个符号并更新其状态。有关这些 FSE 操作的更多详细信息, 请参见第 4.1 节。

要解码的符号数量通过跟踪位流溢出条件确定: 如果在解码符号后更新状态需要的位数超过流中剩余的位数, 则假定额外位为零。然后, 解码每个最终状态的符号, 过程完成。

4.2.1.3 Conversion from Weights to Huffman Prefix Codes (从权重转换为哈夫曼前缀码)

所有出现的符号现在都将具有 Weight 值。可以使用此公式将权重转换为 Number_of_Bits:

if Weight > 0:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight
else:
    Number_of_Bits = 0

符号按 Weight 排序。在相同 Weight 内, 符号保持自然顺序。权重为零的符号被删除。然后, 从最低 Weight 开始, 按顺序分配前缀码。

例如, 假设已解码以下权重列表:

+=========+========+
| Literal | Weight |
+=========+========+
|    0    |   4    |
+---------+--------+
|    1    |   3    |
+---------+--------+
|    2    |   2    |
+---------+--------+
|    3    |   0    |
+---------+--------+
|    4    |   1    |
+---------+--------+
|    5    |   1    |
+---------+--------+

表 24: 解码的权重

按权重排序然后按自然顺序产生以下分布:

+=========+========+================+==============+
| Literal | Weight | Number_Of_Bits | Prefix Codes |
+=========+========+================+==============+
|    3    |   0    |       0        |     N/A      |
+---------+--------+----------------+--------------+
|    4    |   1    |       4        |     0000     |
+---------+--------+----------------+--------------+
|    5    |   1    |       4        |     0001     |
+---------+--------+----------------+--------------+
|    2    |   2    |       3        |     001      |
+---------+--------+----------------+--------------+
|    1    |   3    |       2        |      01      |
+---------+--------+----------------+--------------+
|    0    |   4    |       1        |      1       |
+---------+--------+----------------+--------------+

表 25: 按权重排序

4.2.2 Huffman-Coded Streams (哈夫曼编码流)

给定 Huffman 解码表, 可以解码 Huffman 编码流。

每个位流必须向后读取, 从末尾开始直到开头。因此, 必须知道每个位流的大小。

还必须准确知道哪一位是最后一位。这由最终位标志检测: 最后一个字节的最高位是最终位标志。因此, 最后一个字节不可能为 0。最终位标志本身不是有用位流的一部分。因此, 最后一个字节包含 0 到 7 个有用位。

从末尾开始, 可以以小端方式读取位流, 跟踪已使用的位。由于位流以相反顺序编码, 从末尾开始, 以正向顺序读取符号。

例如, 如果字面序列 "0145" 使用上述前缀码编码, 它将 (以相反顺序) 编码为:

+=========+==========+
|  Symbol | Encoding |
+=========+==========+
|    5    |   0001   |
+---------+----------+
|    4    |   0000   |
+---------+----------+
|    1    |    01    |
+---------+----------+
|    0    |    1     |
+---------+----------+
| Padding |  00001   |
+---------+----------+

表 26: 字面序列 "0145"

这导致以下 2 字节位流:

00010000 00001101

这是一个替代表示, 符号代码用下划线分隔:

0001_0000 00001_1_01

读取最高 Max_Number_of_Bits 位, 可以将提取的值与解码表进行比较, 确定要解码的符号和要丢弃的位数。

该过程继续读取每个流所需的符号数量。如果位流没有完全且恰好消耗完, 因此恰好到达其开始位置并消耗所有位, 则解码过程被认为是错误的。

---