跳到主要内容

2. 压缩表示概述 (Compressed Representation Overview)

2. 压缩表示概述 (Compressed Representation Overview)​

压缩数据集由一个 header 和一系列 meta-block 组成. 每个 meta-block 压缩一段输入字节序列. 如果未压缩数据的大小可预先获知, header 中包含该大小; 否则 header 中包含零. 因此, 一个压缩流具有零个 header 字节是合法的.

一个 meta-block 由 meta-block header 和 meta-block data 组成. meta-block header 描述应如何解释数据部分. 它包含数据部分的大小, 以及两个用于指示数据是否未压缩, 是否为最后一个 meta-block 的位. meta-block data 的解释取决于这些位.

meta-block 的未压缩大小可以为零. 例如, 可以在一个未压缩类型的前序 meta-block 之后发送一个空 meta-block, 或者仅用它来表示数据结束.

meta-block 分为三种:

Compressed meta-blocks: 这些 meta-block 包含 LZ77 前缀编码数据. 每个 compressed meta-block 分为一个 prefix code section 和一个 data section. prefix code section 包含将在 data section 中使用的前缀码 (prefix code). data section 包含一系列 LZ77 向后引用 (backward reference), 字面量 (literal) 和静态字典引用. 每个 LZ77 向后引用是一个 ⟨length, distance⟩ 对, 其中 length 表示要复制的字节数, distance 表示在未压缩数据流中从当前位置向后多少字节处开始复制. distance 为 1 表示要复制最后一个字节若干次. distance 也可以转换为静态字典中的一个位置. 静态字典引用是经过特殊处理的向后引用; 详见 Section 8. 字面量和向后引用存储在同一种数据结构中, 称为插入与复制长度码 (insert-and-copy length code). 通过这种方式, 一个值同时确定插入长度 (insert length, 即紧随该码之后的字面量数量) 和复制长度 (copy length, 即下一个向后引用的长度). 向后引用的 distance 由下一个 distance code 决定. 最后一个 insert-and-copy length code 可以具有 0 的 copy length; 在这种情况下, 数据中的最后若干符号是 literal 值.

Uncompressed meta-blocks: 这些 meta-block 包含未压缩数据.

Meta-data meta-blocks: 这些 meta-block 保留供将来使用. 解码器会跳过它们. 本文档不定义这些 meta-block 的格式. 应用程序可在需要时定义此类格式.

compressed meta-block 的结构如下:

  • 对 literal, insert-and-copy length 和 distance 三个类别中的每一类, 都有一个 block type 和 block count. block type 是一个小整数值, 标识将用于接下来 block count 个值的一组 prefix code. block count 是一个符号数量, 表示当前 block type 中的 prefix code 和 context model 将用于多少个符号.

  • 用于 literal 的 block type 的 prefix code (BTYPE-L).

  • 用于 literal 的 block count 的 prefix code (BLEN-L).

  • 用于 insert-and-copy length 的 block type 的 prefix code (BTYPE-I).

  • 用于 insert-and-copy length 的 block count 的 prefix code (BLEN-I).

  • 用于 distance 的 block type 的 prefix code (BTYPE-D).

  • 用于 distance 的 block count 的 prefix code (BLEN-D).

  • 可能存在 distance 参数 NPOSTFIX 和 NDIRECT (如果该 meta-block 是第一个, 它们设置为 0; 否则它们可以设置为任意非负值, 见 Section 4).

  • literal block type 的数量 NBLTYPES-L 和 context mode 的数量 CMODE (如果 NBLTYPES-L 为 0, 则解释为 1).

  • 对每个 NBLTYPES-L literal block type:

    • literal 的 context mode (零, 一或二).
    • 可能存在 literal context map (如果 NBLTYPES-L 为 1, 则无需编码 context map; 在这种情况下, context ID 始终为 0).

  • insert-and-copy block type 的数量 NBLTYPES-I (如果它为 0, 则解释为 1).

  • 可能存在 insert-and-copy context map (如果 NBLTYPES-I 为 1, 则无需编码 context map; 在这种情况下, context ID 始终为 0).

  • distance block type 的数量 NBLTYPES-D (如果它为 0, 则解释为 1).

  • 可能存在 distance context map (如果 NBLTYPES-D 为 1, 则无需编码 context map; 在这种情况下, context ID 始终为 0).

  • 一系列用于 literal 的 prefix code, 其数量等于 NBLTYPES-L 乘以不同 context ID 的数量 (每个 literal block type 最多 64 个). 这些 code 用于后续命令中的 literal.

  • 一系列用于 insert-and-copy length 的 prefix code, 其数量等于 NBLTYPES-I 乘以不同 context ID 的数量 (每个 insert-and-copy block type 最多 256 个). 这些 code 用于后续命令.

  • 一系列用于 distance 的 prefix code, 其数量等于 NBLTYPES-D 乘以不同 context ID 的数量 (每个 distance block type 为 4 个). 这些 code 用于后续命令中的 distance.

  • 包含 block-switch command, literal, insert-and-copy length 和 distance 的数据流.

block 结构通过使用 block type 将输入划分为不同 alphabet distribution 来帮助压缩. literal 和 distance 的 block type 还可以借助 context 进一步划分为不同 distribution. 每个 block type 的 context map 控制在不同 context 下使用哪个 prefix code.

block switch 背后的直觉是, 输入中的不同区域很可能具有不同统计特性 (例如网页中的 HTML 与 JavaScript). 在一个给定 meta-block 中, 每个类别 (literal, insert-and-copy length 和 distance) 可以有多个 block type, 因此 block switch 可用于在不开始新 meta-block 的情况下调整 prefix code distribution. 每个 block type 都可以基于 context modeling 为 literal 和 distance 提供多个 prefix code distribution.

Source: RFC 7932, Section 2 Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt

最后于 更新