DEFLATE Compressed Data Format Specification version 1.3

Abstract

该规范定义了一种无损压缩数据格式，使用LZ77算法和哈夫曼编码的组合压缩数据，效率可与当前可用的最佳通用压缩方法相当。即使是对于一个长度任意的顺序呈现的输入数据流，数据可以被生成或消耗，而只需要有限的中间存储空间。该格式可以轻松地以一种未被专利覆盖的方式实现。

Introduction

Purpose

该规范的目的是定义一种无损压缩的数据格式：

与CPU类型、操作系统、文件系统和字符集相独立；因此可以互换使用；
可以压缩或解压缩一个数据流(与此相对的是随机访问介质文件)来产生另一种数据流，只使用预先限定的中间存储量，因此可以用于数据通信或类似结果，比如Unix过滤器；
数据的压缩效率可以与当前最佳的通用压缩方法相媲美，尤其是比”compress”程序更好;
可以轻易地以专利不涵盖的方式实行，因此可以自由实现;
与当前广泛使用的gzip实用程序生成的文件格式兼容，符合标准的解压器能够读取由现有gzip压缩器生成的数据。

可以压缩或解压缩数据流：

将数据转化为一种更为紧凑的表示形式，以减少其占用空间；

只实用有限量的中间存储空间：

也就是说，数据的大小在一开始就会被计算，不会随着数据流的大小变化而增长；使用缓冲区或许能够提升一定的性能？

专利不涵盖：

该压缩格式没有与之相关的专利保护。换句话说，使用该压缩格式不会侵犯其他人的专利权利，因为该格式的设计没有涉及到受专利保护的技术或方法。这意味着任何人都可以自由地实现、使用和分发这种压缩格式，而不必担心侵犯他人的知识产权。

本规范定义的数据格式不会做出以下尝试：

提供对压缩数据的随机访问;
压缩专用数据以及目前最好的专用算法;

在这上诉的点上，和上一篇规范GZIP一致。一个简单的计数论证表明：任何无损压缩算法都不能压缩每一个可能的输入数据集。对于本文定义的格式，最坏情况下每$32K$字节块的扩展为$5$个字节，即对于大数据集来说，大小增加了$0.015%$。英文文本通常能够压缩为原来的$2.5 \sim 3$倍；可执行文件通常压缩得稍微少一些；类似于光栅图像这样的图形数据可能会压缩的更多。

Intended audience

本规范供软件实现者使用，用于将数据压缩为deflate格式和(或)从deflate格式中解压数据。

本规范的文本假定读者具有编程方面的基础知识，能够理解位和其他基本数据表示级别的概念。熟悉哈夫曼编码技术是有帮助的，但这并非必须的。

Score

本规范规定了一种将字节序列表示为(通常较短的)比特序列的方法，以及将后面的比特序列打包为字节的方法。

Compliance

除非下文另有说明，符合规范的解压器必须能够接收并解压符合本文提出的所有规范的数据集；符合规范的压缩器必须生成符合此处提供的所有规范的数据集。

Definitions of terms and conventions used

byte: 以单位形式存储或传输的8 bit。(对于此规范，一个字节恰好是8位，即使在将字节存储在与8位不同的位数的计算机也是如此。)

String: 任意字节的序列

Changes from previous versions

自从这个规范的1.1版本以来，deflate格式没有发生任何技术变化。在1.2版本中，一些术语被更改了。1.3版本是将规范转换为RFC风格的版本。

Compress representation overview

一个压缩数据集由一系列块组成，对应于输入数据的连续块。块的大小是任意的，除了不可压缩块被限制在$65535$字节之外。

每个块都是用LZ77算法和哈夫曼编码的组合进行压缩。每个块的哈夫曼树与前后块的哈夫曼树无关；LZ77算法可以使用对前一个块中出现的重复字符串引用，最多可以回溯到$32K$个输入字节。

每个块都由两部分组成：一对描述压缩数据部分表示的哈夫曼编码树，以及一个压缩数据部分。(哈夫曼树自身也会使用哈夫曼编码进行压缩。)压缩数据由两种类型的元素组成：文字字节(literal bytes)(即在前$32K$个输入字节中未被检测为重复的字符串)和指向重复字符串的指针，其中指针表示为$<length, backward\ distance>$。deflate格式中使用的表示方法将距离($distance$)限制为$32K$字节，长度($length$)限制为$258$字节，但不限制块的大小，除了上述已经注意到的不可压缩块。

压缩数据中的每种值类型(literal, distance和lengths)都是用哈夫曼编码表示，使用一个用于文字(literal)和长度(length)的编码树，以及一个用于距离(distance)的单独编码树。每个块的编码树都以紧凑形式出现在该块的压缩数据之前。

Detailed specification

Overall conventions

在下方的图示中，一个这样的box表示一个字节：

1
2
3

+---+ 
|   | <-- the vertical bars might be missing 
+---+

而类似于这样的box表示可变的字节数：

1
2
3

+==============+ 
|              | 
+==============+

存储在计算机中的字节不具有“位序”，因为它们总是被视作一个单位来处理。然而，将字节视为介于$0 \sim 255$之间的整数确实具有最高有效位和最低有效位，因为我们总是以最高有效数字在左侧的方式书写数字，因此我们也以最高有效位在左侧的方式书写字节。

在下方的图示中，我们对一个字节的比特进行编号，使得比特0是最低有效位。

1
2
3

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

在计算机中，一个数字可能占据多个字节。在这里描述的格式中，所有的多字节数字都是以最低有效位优先的方式存储(即在较低的内存地址处)。

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

#### Packing into bytes

**由于本文描述的数据格式是面向字节的，而不是面向比特的；因此，本文没有解决字节的比特在比特序列介质上传输的顺序问题**。然而，**我们将在下文中将压缩快格式描述为各种比特长度的数据元素的序列，而不是字节的序列。因此，我们必须指定如何将这些数据元素打包成字节，以形成最终的压缩字节序列**。

- 数据元素按照字节内位序递增的顺序打包到字节中，即从字节的最低有效位开始
- 哈夫曼编码以外的数据元素从数据元素的最低有效位开始打包
- 哈夫曼编码从编码的最高有效位开始打包

换句话说，如果将压缩数据按字节序列打印出来，从右边界开始的第一个字节，然后向左边进行，每个字节的最高有效位通常在左边，那么可以从右到左解析结果，固定宽度的元素按照正确的最高有效位到最低有效位的顺序排列，而哈夫曼编码则按位逆序排列（即，编码的第一位在相对的最低有效位位置）。

```text
假设我们有一个字节序列，其中每个字节包含以下数据元素：
- 3位长度（LSB至MSB）
- 2位距离（LSB至MSB）
- 3位文字（LSB至MSB）
现在让我们考虑一个示例字节：10110010。

根据先前的说明，我们从右到左解析：
- 最右侧的位（最低有效位）表示文字的最低位。
- 接下来的2位表示距离。
- 接下来的3位表示长度。
- 最左侧的3位表示文字的最高位。
所以，10110010字节可以解析为：
- 文字：010
- 距离：01
- 长度：100

Compressed block format

Synopsis of prefix and Huffman coding

前缀编码(prefix code)通过位序列(代码)来表示来自已知字母表的符号，每个符号对应一个代码，以一种方式进行，以便不同的符号可以由不同长度的位序列表示，但解析器始终可以逐个符号无歧义的解析编码的字符串。

我们将前缀码定义为一种二叉树，其中每个非叶节点下降的两条边分别标记为0和1，叶节点与字母表中的符号一一对应（用标签标记）；然后，符号的编码是从根节点到标记为该符号的叶节点的边上的0和1序列。例如：

      /\          Symbol      Code 
     0  1         ------      ----
    /    \            A        00 
   /\     B           B         1 
  0  1                C       011 
 /    \               D       010 
A     /\ 
     0  1 
    /    \ 
   D      C

解析器可以通过从根节点开始沿着树向下移动，在每一步选择与下一个输入位对应的边来从编码的输入流中解码下一个符号。

在已知符号频率的字母表中，哈夫曼算法允许构建最佳前缀码(使用最少位数表示具有该字母表符号频率的字符串的前缀码)。这样的代码称为哈夫曼码。(有关赫夫曼码的更多信息，请参见参考文献<Huffman, D. A., “A Method for the Construction of Minimum Redundancy Codes”, Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101>)

请注意，在deflate格式中，各种字母表的哈夫曼码长度不能超过某些最大码长。这个约束条件使得从符号频率计算码长的算法变得更加复杂。详细信息请参见上述的参考文献。