3. 前缀码的压缩表示 (Compressed Representation of Prefix Codes)
3. 前缀码的压缩表示 (Compressed Representation of Prefix Codes)
3.1. 前缀编码简介 (Introduction to Prefix Coding)
前缀编码 (prefix coding) 使用位序列 (code) 表示来自预先已知 alphabet 的符号, 每个符号对应一个 code. 不同符号可以用不同长度的位序列表示, 但解析器始终能够按符号无歧义地解析一个已编码字符串.
我们用一棵二叉树来定义前缀码 (prefix code). 在这棵树中, 从每个非叶节点向下的两条边分别标记为 0 和 1, 叶节点与 alphabet 中的符号一一对应 (并以这些符号标记). 某个符号的 code 是从根到标记为该符号的叶节点路径上各边的 0 和 1 序列. 例如:
/\ Symbol Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
解析器可以通过从根开始沿树向下行走来从压缩流中解码下一个符号, 每一步都选择与下一个压缩数据位对应的边.
给定一个具有已知符号频率的 alphabet, Huffman 算法可以构造一个最优前缀码, 即在这些符号频率下, 对该 alphabet 的字符串使用的位数少于或等于任何其他可能前缀码的前缀码. 这种前缀码称为 Huffman 码. (关于 Huffman 码的更多信息, 见 [HUFFMAN].)
在 Brotli 格式中, 注意各个 alphabet 的 prefix code 不得超过特定的最大 code length. 这个约束使得从符号频率计算 code length 的算法更复杂. 同样, 详见 [HUFFMAN].
3.2. Brotli 格式中前缀编码的使用 (Use of Prefix Coding in the Brotli Format)
Brotli 格式中用于每个 alphabet 的 prefix code 是规范前缀码 (canonical prefix code), 它还有两条附加规则:
-
给定位长度的所有 code 都具有按字典序连续的值, 且顺序与它们表示的符号顺序相同;
-
较短的 code 在字典序上先于较长的 code.
假设 alphabet 的顺序为 ABCD, 可以把上面的示例重新编码为符合该规则的形式:
Symbol Code
------ ----
A 10
B 0
C 110
D 111
也就是说, 0 先于 10, 10 先于 11x, 且 110 和 111 在字典序上连续.
有了这条规则后, 只需按 alphabet 中每个符号的顺序给出其 code 的 bit length, 就可以定义该 alphabet 的 canonical prefix code; 这些信息足以确定实际 code. 在我们的示例中, code 完全由 bit length 序列 (2, 1, 3, 3) 定义. 以下算法把 code 生成为整数, 其意图是从最高有效位读到最低有效位. code length 初始位于 tree[I].Len; 生成的 code 位于 tree[I].Code.
-
统计每种 code length 的 code 数量. 令 bl_count[N] 为长度为 N 的 code 数量, N >= 1.
-
找出每种 code length 的最小 code 的数值:
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
code = (code + bl_count[bits-1]) << 1;
next_code[bits] = code;
}
- 为所有 code 分配数值, 对同一长度的所有 code 使用连续值, 其基值由步骤 2 确定. 从未使用的 code (bit length 为零的 code) 不得分配值.
for (n = 0; n <= max_code; n++) {
len = tree[n].Len;
if (len != 0) {
tree[n].Code = next_code[len];
next_code[len]++;
}
}
示例:
考虑 alphabet ABCDEFGH, 其 bit length 为 (3, 3, 3, 3, 3, 2, 4, 4). 步骤 1 后得到:
N bl_count[N]
- -----------
2 1
3 5
4 2
步骤 2 计算得到以下 next_code 值:
N next_code[N]
- ------------
1 0
2 0
3 2
4 14
步骤 3 产生以下 code 值:
Symbol Length Code
------ ------ ----
A 3 010
B 3 011
C 3 100
D 3 101
E 3 110
F 2 00
G 4 1110
H 4 1111
3.3. Alphabet 大小 (Alphabet Sizes)
在 Brotli 格式中, prefix code 用于不同目的, 每种目的都有不同的 alphabet size. 对 literal code, alphabet size 为 256. 对 insert-and-copy length code, alphabet size 为 704. 对 block count code, alphabet size 为 26. 对 distance code, block type code 以及用于压缩 context map 的 prefix code, alphabet size 是动态的, 基于后续章节定义的参数. 下表汇总了各种 prefix code 的 alphabet size 以及本文档中定义它们的章节.
+-----------------+-------------------------+------------+
| Prefix Code | Alphabet Size | Definition |
+-----------------+-------------------------+------------+
| literal | 256 | |
+-----------------+-------------------------+------------+
| distance | 16 + NDIRECT + | Section 4 |
| | (48 `<<` NPOSTFIX) | |
+-----------------+-------------------------+------------+
| insert-and-copy | 704 | Section 5 |
| length | | |
+-----------------+-------------------------+------------+
| block count | 26 | Section 6 |
+-----------------+-------------------------+------------+
| block type | NBLTYPESx + 2, | Section 6 |
| | (where x is I, L, or D) | |
+-----------------+-------------------------+------------+
| context map | NTREESx + RLEMAXx | Section 7 |
| | (where x is L or D) | |
+-----------------+-------------------------+------------+
3.4. 简单前缀码 (Simple Prefix Codes)
每个 prefix code 的压缩表示中的前两位用于区分 simple prefix code 和 complex prefix code. 如果该值为 1, 则后面跟随本节所述的 simple prefix code. 否则, 后面跟随 Section 3.5 所述的 complex prefix code.
simple prefix code 最多可以有四个 non-zero code length 的符号. simple prefix code 的格式如下:
2 bits: value of 1 indicates a simple prefix code
2 bits: NSYM - 1, where NSYM = number of symbols coded
NSYM symbols, each encoded using ALPHABET_BITS bits
1 bit: tree-select, present only for NSYM = 4
ALPHABET_BITS 的值取决于 prefix code 的 alphabet: 它是能够表示该 alphabet 中所有符号的最小位数. 例如, 对 literal byte 的 alphabet, ALPHABET_BITS 为 8. 上述每个 NSYM 符号的值都是 ALPHABET_BITS 位宽整数值的值. 如果该整数值大于或等于 alphabet size, 或者该值与先前值相同, 则应将该 stream 拒绝为无效.
注意, NSYM 个符号可以不按排序顺序给出. 具有相同 bit length 的 prefix code 必须按符号排序顺序分配给这些符号.
符号的 (non-zero) code length 可按如下方式重建:
-
如果 NSYM = 1, 则这个唯一符号的 code length 为零. 使用该 prefix code 在 compressed data stream 中编码此符号时, 不实际发出任何位. 类似地, 使用该 prefix code 解码符号时, 不读取任何位并返回这个唯一符号.
-
如果 NSYM = 2, 两个符号的 code length 都为 1.
-
如果 NSYM = 3, 各符号的 code length 按它们在 simple prefix code 表示中出现的顺序为 1, 2, 2.
-
如果 NSYM = 4, code length (按符号被解码的顺序) 取决于 tree-select 位: 2, 2, 2, 2 (tree-select bit 0), 或 1, 2, 3, 3 (tree-select bit 1).
3.5. 复杂前缀码 (Complex Prefix Codes)
complex prefix code 是一种 canonical prefix code, 如 Section 3.2 所述, 由 code length 序列定义. 为了获得更高的紧凑性, code length 序列本身也使用 prefix code 压缩. code length 的 alphabet 如下:
0..15: Represent code lengths of 0..15
16: Copy the previous non-zero code length 3..6 times.
The next 2 bits indicate repeat length
(0 = 3, ... , 3 = 6)
If this is the first code length, or all previous
code lengths are zero, a code length of 8 is
repeated 3..6 times.
A repeated code length code of 16 modifies the
repeat count of the previous one as follows:
repeat count = (4 * (repeat count - 2)) +
(3..6 on the next 2 bits)
Example: Codes 7, 16 (+2 bits 11), 16 (+2 bits 10)
will expand to 22 code lengths of 7
(1 + 4 * (6 - 2) + 5)
17: Repeat a code length of 0 for 3..10 times.
The next 3 bits indicate repeat length
(0 = 3, ... , 7 = 10)
A repeated code length code of 17 modifies the
repeat count of the previous one as follows:
repeat count = (8 * (repeat count - 2)) +
(3..10 on the next 3 bits)
注意, 紧接在前一个 16 之后的 16 code 会修改前一个 repeat count, 修改后的值成为新的 repeat count. 17 跟随 17 时同样如此. 连续三个或更多 16 code, 或连续三个或更多 17 code 都是可能的, 每次都会修改计数. 只使用最终 repeat count. 这种修改只在相同 code 相继出现时适用. 16 repeat 不会修改紧接在前的 17 count, 反之亦然.
code length 为 0 表示 alphabet 中对应符号不会出现在压缩数据中, 且不应参与前面给出的 prefix code 构造算法. complex prefix code 必须至少有两个 non-zero code length.
code length alphabet 上的 prefix code 的 bit length 使用以下 variable-length code 压缩 (这是它在压缩数据中出现的形式, 其中位从右向左解析):
Symbol Code
------ ----
0 00
1 0111
2 011
3 10
4 01
5 1111
现在可以按如下方式定义 complex prefix code 的格式:
-
2 bits: HSKIP, 即跳过的 code length 数量, 其值可以为 0, 2 或 3. 被跳过的 length 视为零. (HSKIP 为 1 表示 Simple prefix code.)
-
上面给出的 code length alphabet 中各符号的 code length, 顺序为: 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15. 如果 HSKIP 为 2, 则符号 1 和 2 的 code length 为零, 第一个 code length 对应符号 3. 如果 HSKIP 为 3, 则符号 3 的 code length 也为零, 第一个 code length 对应符号 4.
code length symbol 的 code length 介于 0 和 5 之间, 并按上面的 variable-length code 用 2..4 位表示. code length 为 0 表示对应的 code length symbol 未使用.
如果 HSKIP 为 2 或 3, 则相应数量的前导 code length 是隐式零, 并且不会出现在上面的 code length 序列中.
如果至少有两个 non-zero code length, 则省略所有尾随 zero code length, 即序列中的最后一个 code length 必须非零. 在这种情况下, 所有 non-zero code length 上的 (32
>>code length) 之和必须等于 32.如果已经读取了整个 code length alphabet 的 length, 且只有一个 non-zero code length, 则该 prefix code 具有一个 code length 为零的符号. 在这种情况下, 压缩器不会因该符号发出任何位, 解压器也不会消耗任何位. 解码该 code 时会立即返回这个单一符号. 这种情况的一个示例是, 要表示的整个 code 具有 length 为 8 的符号. 例如, 一个以相同概率表示所有 literal 值的 literal code. 在这种情况下, 单一符号为 16, 它会重复前一个 length. 在读取任何 code length code length 之前, 前一个 length 视为 8.
-
code length symbol 的序列, 其长度最多为 alphabet 的大小, 使用 code length prefix code 编码. 必须省略任何尾随 0 或 17, 即最后一个已编码 code length symbol 必须介于 1 和 16 之间. alphabet 中所有 non-zero code length 上的 (32768 >> code length) 之和必须等于 32768, 其中包括使用 repeat code 16 编码的那些 length. 如果重复前一个 length 或重复 zero length 的次数会导致总 length 数超过 alphabet 中的符号数, 则应将该 stream 拒绝为无效.
Source: RFC 7932
Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt