7. 上下文建模
- 上下文建模
如第 2 节所述, 用于编码字面量字节或距离码的前缀树取决于块类型和上下文 ID. 本节规定如何为特定字面量和距离码计算上下文 ID, 以及如何编码上下文映射. 该映射把 <block type, context ID> 对映射到字面量和距离前缀码数组中的前缀码索引.
7.1. 字面量的上下文模式和上下文 ID 查找
编码下一个字面量时使用的上下文由流中的最后两个字节定义 (p1, p2, 其中 p1 是最近的字节), 无论这些字节是由未压缩元块, 向后引用, 静态字典引用还是字面量插入产生. 在流开始处, p1 和 p2 初始化为零.
计算上下文 ID 有四种方法, 称为上下文模式:
* LSB6, 其中上下文 ID 是 p1 的六个最低有效位的值,
* MSB6, 其中上下文 ID 是 p1 的六个最高有效位的值,
* UTF8, 其中上下文 ID 是 p1, p2 的复杂函数, 针对文本压缩优化, 以及
* Signed, 其中上下文 ID 是 p1, p2 的复杂函数, 针对有符号整数序列压缩优化.
UTF8 和 Signed 上下文模式的上下文 ID 使用以下查找表 Lut0, Lut1 和 Lut2 计算.
Lut0 :=
0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0, 4, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12, 0,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3
Lut1 :=
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
Lut2 :=
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7
将这些表各自视为字节序列时, 其长度和 CRC-32 校验值 (见 Appendix C) 如下:
Table Length CRC-32
----- ------ ------
Lut0 256 0x8e91efb7
Lut1 256 0xd01a32f4
Lut2 256 0x0dd7a0d6
给定 p1 是最后一个未压缩字节, p2 是倒数第二个未压缩字节, 可按如下方式计算上下文 ID:
For LSB6: Context ID = p1 & 0x3f
For MSB6: Context ID = p1 >> 2
For UTF8: Context ID = Lut0[p1] | Lut1[p2]
For Signed: Context ID = (Lut2[p1] `<<` 3) | Lut2[p2]
从上面定义的查找表和用于计算上下文 ID 的操作可以看出, 字面量的上下文 ID 位于 0..63 范围内.
上下文模式 LSB6, MSB6, UTF8 和 Signed 分别由整数 0, 1, 2, 3 表示.
每个字面量块类型都有一个上下文模式, 它们存储在元块头部中的一个连续位数组中, 每个块类型始终占两位.
7.2. 距离的上下文 ID
编码距离码时使用的上下文由该距离对应的复制长度定义. 对于复制长度 2, 3, 4 以及大于 4 的情况, 上下文 ID 分别为 0, 1, 2 和 3.
7.3. 上下文映射的编码
有两个上下文映射, 一个用于字面量, 一个用于距离. 字面量上下文映射的大小为 64 * NBLTYPESL, 距离上下文映射的大小为 4 * NBLTYPESD. 上下文映射中的每个值都是 0 到 255 之间的整数, 表示编码下一个字面量或距离时要使用的前缀码索引.
上下文映射是二维矩阵, 但编码为一维数组:
CMAPL[0..(64 * NBLTYPESL - 1)]
CMAPD[0..(4 * NBLTYPESD - 1)]
对于块类型 BTYPE_x 和上下文 ID CIDx, 编码字面量或距离码所用前缀码的索引为:
index of literal prefix code = CMAPL[64 * BTYPE_L + CIDL]
index of distance prefix code = CMAPD[4 * BTYPE_D + CIDD]
上下文映射的值使用针对零值的游程长度编码与前缀编码组合进行编码. 令 RLEMAX 表示游程长度码的数量, NTREES 表示上下文映射中的最大值加一. NTREES 必须等于上下文映射中不同值的数量. 换言之, 上下文映射中的不同值必须构成 [0..NTREES-1] 区间. 该前缀码的字母表包含以下 RLEMAX + NTREES 个符号:
0: 零值
1: 将零重复 2 到 3 次, 读取 1 位作为重复长度
2: 将零重复 4 到 7 次, 读取 2 位作为重复长度
...
RLEMAX: 将零重复 (1 `<<` RLEMAX) 到 (1 `<<` (RLEMAX+1))-1
次, 读取 RLEMAX 位作为重复长度
RLEMAX + 1: 值 1
...
RLEMAX + NTREES - 1: 值 NTREES - 1
如果 RLEMAX = 0, 则不使用游程长度编码, 字母表中的符号直接就是上下文映射中的值. 现在可以定义上下文映射的格式 (字面量和距离上下文映射使用相同格式):
1..5 bits: RLEMAX, 0 使用一个 0 位编码, 值 1..16
使用位模式 xxxx1 编码 (因此 01001 为 5)
字母表大小为 NTREES + RLEMAX 的前缀码
使用上述前缀码以及针对零值的游程长度编码, 对上下文映射大小个值进行编码. 如果某个游程长度会导致总长度超过上下文映射的大小, 则应将该流拒绝为无效.
1 bit: IMTF 位, 如果置位, 则对上下文映射中的值执行逆 move-to-front 变换, 以得到前缀码索引.
注意, RLEMAX 可能大于表示最长零值序列所必需的值. 另外, 如第 9.2 节所述, NTREES 值编码在上下文映射之前.
本规范使用的逆 move-to-front 变换由以下 C 语言函数定义:
void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
uint8_t mtf[256];
int i;
for (i = 0; i < 256; ++i) {
mtf[i] = (uint8_t)i;
}
for (i = 0; i < v_len; ++i) {
uint8_t index = v[i];
uint8_t value = mtf[index];
v[i] = value;
for (; index; --index) {
mtf[index] = mtf[index - 1];
}
mtf[0] = value;
}
}
注意, 逆 move-to-front 变换不会产生 [0..NTREES-1] 区间之外的值.
Source: RFC 7932
Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt