跳到主要内容

1. 引言 (Introduction)

1. 引言 (Introduction)​

1.1. 目的 (Purpose)​

本规范的目的是定义一种无损压缩数据格式, 它:

  • 独立于 CPU 类型, 操作系统, 文件系统和字符集; 因此可用于数据交换.

  • 即使面对任意长, 按顺序给出的输入数据流, 也能只使用预先有界数量的中间存储来生成或消费; 因此可用于数据通信或类似结构, 例如 Unix 过滤器.

  • 能以接近当前最佳通用压缩方法的压缩率压缩数据, 尤其明显优于 gzip 程序.

  • 解压速度远快于当前 LZMA 实现.

本规范定义的数据格式并不试图:

  • 允许对压缩数据进行随机访问.

  • 像当前最佳专用算法那样高密度地压缩专用数据 (例如光栅图形).

本文档是 Brotli 压缩数据格式的权威规范. 它定义了有效 Brotli 压缩数据流的集合, 以及一种解码器算法, 该算法可从有效的 Brotli 压缩数据流生成未压缩数据流.

1.2. 预期读者 (Intended Audience)​

本规范面向软件实现者, 用于将数据压缩为 Brotli 格式和/或从 Brotli 格式解压数据.

规范文本假定读者具备位和其他原始数据表示层面的基本编程背景. 熟悉 Huffman 编码技术会有所帮助, 但不是必需条件.

本规范大量使用 DEFLATE 格式规范 [RFC1951] 中引入的记号和术语. 为完整起见, 我们始终包含 RFC 1951 相关部分的全部文本; 因此熟悉 DEFLATE 格式会有所帮助, 但不是必需条件.

本规范定义的压缩数据格式是 WOFF File Format 2.0 [WOFF2] 的组成部分; 因此, 本规范也面向 WOFF 2.0 压缩器和解压器的实现者.

1.3. 范围 (Scope)​

本文档规定了一种将字节序列表示为一个 (通常更短的) 位序列的方法, 以及一种将后者位序列打包为字节的方法.

1.4. 符合性 (Compliance)​

除非下文另有说明, 符合规范的解压器必须能够接受并解压任何符合本文所列全部规范的数据集. 符合规范的压缩器必须生成符合本文所列全部规范的数据集.

1.5. 所用术语和约定的定义 (Definitions of Terms and Conventions Used)​

Byte: 作为一个单元存储或传输的 8 位 (与 octet 相同). 对本规范而言, 一个 byte 恰好为 8 位, 即使在以不同于 8 位的若干位存储一个字符的机器上也是如此. 关于 byte 内部位的编号, 见下文.

String: 任意字节的序列.

计算机内存储的字节没有 "bit order", 因为它们总是作为一个单元处理. 但是, 当把一个字节看作 0 到 255 之间的整数时, 它确实有最高有效位和最低有效位 (lsb). 由于书写数字时最高有效数字位于左侧, 我们也把字节的最高有效位 (msb) 写在左侧. 在下面的图中, 我们对一个字节的位进行编号, 使 bit 0 为最低有效位, 即各位编号如下:

+--------+
|76543210|
+--------+

在计算机内部, 一个数可以占用多个字节. 此处描述的格式中的所有多字节数字都以最低有效字节在前 (位于较低内存地址) 的方式存储. 例如, 十进制数 520 的存储方式如下:

    0        1
+--------+--------+
|00001000|00000010|
+--------+--------+
 ^        ^
 |        |
 |        + more significant byte = 2 x 256
 + less significant byte = 8

1.5.1. 打包为字节 (Packing into Bytes)​

本文档不讨论在按位顺序传输的介质上, 一个字节的各位应以何种顺序传输, 因为此处描述的最终数据格式是面向字节而不是面向位的. 但是, 下文把压缩块格式描述为一系列不同位长度的数据元素, 而不是字节序列. 因此, 我们必须规定如何把这些数据元素打包进字节, 以形成最终的压缩字节序列:

  • 数据元素按字节内位编号递增的顺序打包进字节, 即从字节的最低有效位开始.

  • Huffman 码之外的数据元素从该数据元素的最低有效位开始打包.

  • Huffman 码从该码的最高有效位开始打包.

换言之, 如果把压缩数据打印为一串字节, 从右边距处的第一个字节开始并向左推进, 且像通常一样把每个字节的最高有效位放在左侧, 则可以从右向左解析结果: 固定宽度元素保持正确的 MSB 到 LSB 顺序, Huffman 码则以位反转顺序出现 (即该码的第一位处在相对 LSB 位置).

例如, 考虑把以下数据元素打包为 3 个字节的序列:

  • 2-bit value 1 (binary 01)
  • 3-bit value 2 (binary 010)
  • 5-bit value 6 (binary 00110)
  • 4-bit code with bit pattern 1011 (with the first bit being 1, the second bit being 0, the third bit being 1, and the fourth bit being 1)
  • 2-bit value 0 (binary 00)
  • 4-bit code with bit pattern 0011
  • 5-bit value 31 (binary 11111)

下图展示了这些元素的打包方式:

       Byte 0           Byte 1           Byte 2
   +---------------+----------------+----------------+
   |0|1|1|0|0|0|1|0|1|1|0|1|1|0|0|0|0|1|1|1|1|1|1|1|
   +---------------+----------------+----------------+
    ^ ^ ^   ^     ^ ^     ^       ^   ^             ^
    | | |   |     | |     |       |   |             |
    | | |   |     | |     |       |   +-------------|---+ 5-bit value 31
    | | |   |     | |     |       +-----------------|---|-+ 4-bit code 0011
    | | |   |     | |     +-----------------------+     |
    | | |   |     | |                             |     | 2-bit value 0
    | | |   |     | +-----------------------------+-----+ 4-bit code 1011
    | | |   +---+ 5-bit value 6
    | | +-----+ 3-bit value 2
    | +---+ 2-bit value 1

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

最后于 更新