Huffman 编码与 DEFLATE

数据压缩是计算机科学中少数同时具备深厚理论根基与广泛工程实践的领域。从 Shannon 在 1948 年奠定信息论，到 Huffman 在 1952 年发明最优前缀码，再到 DEFLATE 在 1993 年成为 RFC 标准——这条路走了近半个世纪，却至今仍是互联网基础设施的核心组成。本文将从信息论基础出发，逐层剖析 Huffman 编码的原理、规范化实现以及 DEFLATE 格式的完整细节，并附上可编译运行的 C 代码和实测数据。

一、信息熵与信源编码定理

1.1 信息的度量

Claude Shannon 在其划时代论文 A Mathematical Theory of Communication 中提出了用概率来度量信息的方法。对于一个离散无记忆信源，其字母表为 \(\{s_1, s_2, \ldots, s_n\}\)，每个符号出现的概率为 \(p_i\)，则 Shannon 熵定义为：

\[ H(S) = -\sum_{i=1}^{n} p_i \log_2 p_i \]

直觉上，熵衡量的是”平均每个符号携带多少比特的不确定性”。若所有符号等概率出现，熵取最大值 \(\log_2 n\)；若某个符号概率为 1，熵为 0——毫无悬念的信源不需要任何比特来描述。

1.2 信源编码定理

Shannon 第一定理（无噪声编码定理）告诉我们：

对于离散无记忆信源，存在一种编码方案使平均码长 \(\bar{L}\) 满足 \(H(S) \le \bar{L} < H(S) + 1\)。但不存在任何无损编码能使 \(\bar{L} < H(S)\)。

这给出了压缩的理论极限。Huffman 编码之所以重要，正是因为它是达到这个下界的最简单的实用方法之一。

1.3 一个具体的例子

考虑如下信源：

计算信息熵：

\[ H = -(0.45 \log_2 0.45 + 0.13 \log_2 0.13 + 0.12 \log_2 0.12 + 0.16 \log_2 0.16 + 0.09 \log_2 0.09 + 0.05 \log_2 0.05) \approx 2.23 \text{ bits/symbol} \]

定长编码需要 \(\lceil \log_2 6 \rceil = 3\) bits/symbol。而 Huffman 编码可以做到约 2.24 bits/symbol，非常接近理论极限。

二、Huffman 编码算法

2.1 贪心构造

David Huffman 在 MIT 读研期间（1952 年）提出了这个算法。其核心是一个自底向上的贪心过程：

1. 为每个符号创建一个叶节点，权重等于其频率。
2. 将所有节点放入一个最小优先队列（min-heap）。
3. 重复以下操作直到队列中只剩一个节点：
   • 取出权重最小的两个节点 \(x\) 和 \(y\)。
   • 创建一个新内部节点 \(z\)，左子为 \(x\)，右子为 \(y\)，权重为 \(w(x) + w(y)\)。
   • 将 \(z\) 放回队列。
4. 最后剩下的节点即为 Huffman 树的根。
5. 从根到每个叶的路径上，左分支记 0，右分支记 1，即为该符号的编码。

2.2 构造过程示意

以上述 6 个符号为例，构造过程如下：

初始队列: [F:5, E:9, C:12, B:13, D:16, A:45]

Step 1: 合并 F(5) + E(9) = 14
        [C:12, B:13, (FE):14, D:16, A:45]

Step 2: 合并 C(12) + B(13) = 25
        [(FE):14, D:16, (CB):25, A:45]

Step 3: 合并 (FE)(14) + D(16) = 30
        [(CB):25, (FED):30, A:45]

Step 4: 合并 (CB)(25) + (FED)(30) = 55
        [A:45, (CBFED):55]

Step 5: 合并 A(45) + (CBFED)(55) = 100
        [(ACBFED):100]    -- 完成

最终得到的编码表为：

下图是完整的 Huffman 树结构：

2.3 时间复杂度

使用二叉堆实现优先队列时，每次 extract-min 和 insert 均为 \(O(\log n)\)，总共执行 \(2(n-1)\) 次 extract-min 和 \(n-1\) 次 insert，因此总时间复杂度为 \(O(n \log n)\)。

若使用两个队列的技巧（先排序，然后用两个 FIFO 队列），可以在 \(O(n)\) 时间内完成构造（排序为 \(O(n \log n)\) 的瓶颈）。对于字节字母表（\(n = 256\)），计数排序可以将总复杂度降到 \(O(n)\)。

三、Huffman 编码的最优性证明

3.1 前缀码与 Kraft 不等式

Huffman 编码产生的是前缀码（prefix-free code）：没有任何码字是另一个码字的前缀。这保证了解码的唯一性——逐位读入，一旦匹配到某个码字，就输出对应符号，无需回溯。

Kraft 不等式指出，对于码字长度为 \(l_1, l_2, \ldots, l_n\) 的前缀码，必须满足：

\[ \sum_{i=1}^{n} 2^{-l_i} \le 1 \]

反过来，只要满足 Kraft 不等式，就存在一组对应长度的前缀码。

3.2 最优性证明思路

Huffman 编码的最优性可以通过以下步骤证明：

引理 1：在最优前缀码中，频率最低的两个符号必定拥有相同的最大码长，且它们的码字仅在最后一位不同（即它们是兄弟节点）。

证明：反证法。若频率最低的符号 \(x\) 的码长不是最长的，则可以将 \(x\) 与最长码的符号交换位置（深度更大的位置分配给频率更低的符号），交换后平均码长不会增加，甚至会减少——与原来就是最优矛盾。

引理 2：设 \(x, y\) 为频率最低的两个符号，将它们合并为一个新符号 \(z\)（频率为 \(f(x) + f(y)\)），则在缩减后的信源上的最优前缀码也是原信源最优前缀码的一部分。

主定理：由引理 1 和引理 2，归纳可得 Huffman 贪心策略构造的码恰好是最优前缀码。每一步合并都保持最优性，直到只剩一个符号。

3.3 关于”最优”的注意事项

Huffman 编码是在逐符号编码约束下的最优方案。但它有两个局限：

1. 码长只能是整数比特，这意味着当某符号概率不是 2 的负整数次幂时，不可避免地存在冗余。
2. 它假设信源是无记忆的——符号之间没有相关性。

算术编码（Arithmetic Coding）和非对称数字系统（ANS）可以突破第一个限制，达到任意接近熵的平均码长。而 LZ 系列算法通过字典匹配隐式地处理了第二个限制——这正是 DEFLATE 将两者结合的原因。

四、规范 Huffman 编码

4.1 为什么需要规范化

标准 Huffman 树的形状不唯一——同频率的符号可以任意交换位置，导致不同实现可能生成不同的树。这意味着编码器和解码器必须传输完整的树结构，代价高昂。

规范 Huffman 编码（Canonical Huffman Code）通过施加额外约束消除了这种歧义：

1. 相同码长的符号按字母序排列。
2. 较短的码字在数值上小于较长的码字（左对齐比较）。
3. 同一码长内的码字连续递增。

这样，只需传输每个符号的码长即可完全重建编码表——无需传输树结构本身。

4.2 规范编码的构造算法

输入：每个符号的码长数组 code_lengths[0..n-1]
输出：每个符号的规范编码 code[0..n-1]

Step 1: 统计每个码长出现的次数
        bl_count[l] = |{i : code_lengths[i] == l}|

Step 2: 计算每个码长的起始编码
        next_code[0] = 0
        for l = 1 to MAX_BITS:
            next_code[l] = (next_code[l-1] + bl_count[l-1]) << 1

Step 3: 按符号顺序分配编码
        for i = 0 to n-1:
            if code_lengths[i] != 0:
                code[i] = next_code[code_lengths[i]]
                next_code[code_lengths[i]] += 1

4.3 一个规范化的例子

沿用之前的例子，码长分布为：

按规范化算法：

bl_count = [0, 1, 0, 3, 2]

next_code[1] = (0 + 0) << 1 = 0
next_code[2] = (0 + 1) << 1 = 2
next_code[3] = (2 + 0) << 1 = 4    -- 二进制 100
next_code[4] = (4 + 3) << 1 = 14   -- 二进制 1110

分配：
A (码长1): code = 0        -> 0
B (码长3): code = 4        -> 100
C (码长3): code = 5        -> 101
D (码长3): code = 6        -> 110
E (码长4): code = 14       -> 1110
F (码长4): code = 15       -> 1111

注意到这与非规范版本的编码略有不同（B 和 C 的编码互换了），但总码长完全相同。规范化的好处是解码器只需要码长数组即可重建编码。

4.4 快速解码

规范 Huffman 编码的一个关键优势是可以用查表法实现极快的解码。最常见的方法是多级查表：

1. 取输入比特流的前 \(k\) 位（通常 \(k = 9\) 或 \(k = 11\)）。
2. 查表得到符号和实际码长。
3. 若码长 \(\le k\)，直接输出符号，消耗对应位数。
4. 若码长 \(> k\)，进入二级表继续查找。

这种方法在大多数情况下只需一次表查找即可解码一个符号，远快于逐位遍历树的方法。zlib 的实现正是采用了这种策略。

五、LZ77：字典压缩的基石

5.1 滑动窗口

DEFLATE 的第一阶段并不是 Huffman 编码，而是 LZ77 字典压缩。LZ77 的核心思想是：如果当前要编码的字符串在之前已经出现过，就用一个 (distance, length) 对来引用它，而不是逐字节存储。

在 DEFLATE 中：

• 滑动窗口大小为 32KB（32768 字节）。
• 距离（distance）范围为 1 到 32768。
• 匹配长度（length）范围为 3 到 258 字节。
• 不能匹配的字节作为字面量（literal）直接输出。

5.2 匹配查找

高效的匹配查找是 LZ77 实现的关键。常见策略包括：

• 哈希链（Hash Chain）：以 3 字节为单位计算哈希，将相同哈希的位置链成链表。查找时沿链遍历，取最长匹配。zlib 的默认实现就是这种方法。
• 后缀数组/树：理论上更优，但实现复杂度高，不适合流式处理。
• 二叉搜索树：7-Zip 使用的方法，在高压缩级别下效果较好。

压缩级别的差异主要体现在匹配查找的努力程度上：

5.3 懒惰匹配

zlib 实现了一种称为懒惰匹配（lazy matching）的优化：在找到一个匹配后，不立即输出，而是检查下一个位置是否有更长的匹配。如果有，则放弃当前匹配，先输出一个字面量，再使用更长的那个匹配。

输入: ...ABCDEABCDFABCDE...

位置 10: 找到匹配 (distance=10, length=4) "ABCD"
位置 11: 检查——找到匹配 (distance=5, length=5) "BCDE"（更长）
决策: 输出位置 10 的 'A' 作为字面量，使用位置 11 的匹配

这种策略以少量时间开销换取更好的压缩率。

六、DEFLATE 格式详解

6.1 整体结构

DEFLATE（RFC 1951）将输入数据分成若干块（block），每个块独立压缩。每个块的头部包含：

• BFINAL（1 bit）：是否为最后一个块。
• BTYPE（2 bits）：块类型。
  • 00：无压缩（stored）。
  • 01：使用静态 Huffman 编码。
  • 10：使用动态 Huffman 编码。
  • 11：保留（错误）。

6.2 LZ77 输出的编码

LZ77 阶段的输出是一系列字面量和 (length, distance) 对的混合序列。DEFLATE 用两棵 Huffman 树来编码它们：

Literal/Length 树（树 1）： - 编码值 0-255 表示字面量字节。 - 编码值 256 表示块结束。 - 编码值 257-285 表示匹配长度（附加额外比特）。

Distance 树（树 2）： - 编码值 0-29 表示距离（附加额外比特）。

长度和距离都使用了基值+额外比特的编码方式来覆盖较大的范围：

Length codes (部分):
Code  Extra bits  Length range
257   0           3
258   0           4
259   0           5
...
265   1           11-12
266   1           13-14
...
285   0           258

Distance codes (部分):
Code  Extra bits  Distance range
0     0           1
1     0           2
2     0           3
3     0           4
4     1           5-6
5     1           7-8
...
29    13          24577-32768

6.3 静态 Huffman 块

DEFLATE 定义了一组固定的 Huffman 编码，称为静态 Huffman 编码。当数据量较小或数据分布接近均匀时，使用静态编码可以避免传输码表的开销：

Literal/Length:
  0-143   : 8 bits  (00110000 - 10111111)
  144-255 : 9 bits  (110010000 - 111111111)
  256-279 : 7 bits  (0000000 - 0010111)
  280-287 : 8 bits  (11000000 - 11000111)

Distance:
  0-31    : 5 bits  (固定)

6.4 动态 Huffman 块

动态 Huffman 块在块头部传输自定义的码表。为了节省空间，码表本身也经过编码，形成了三层嵌套的 Huffman 结构：

1. 第三层（CL 码表）：用于编码前两棵树的码长序列。只有 19 个可能的符号（0-15 表示码长，16 表示重复上一个码长，17 表示重复 0 若干次，18 表示重复 0 更多次）。
2. 第二层：Literal/Length 树和 Distance 树的码长序列，用 CL 码表编码。
3. 第一层：实际数据，用上述两棵树编码。

动态块头部的完整布局：

HLIT   (5 bits):  Literal/Length 码的数量 - 257 (范围 257-286)
HDIST  (5 bits):  Distance 码的数量 - 1      (范围 1-32)
HCLEN  (4 bits):  CL 码长度的数量 - 4        (范围 4-19)

CL 码长序列 (每个 3 bits，按特定顺序):
  顺序: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

接下来是用 CL Huffman 编码的:
  HLIT + 257 个 Literal/Length 码长
  HDIST + 1 个 Distance 码长

CL 码长的传输顺序是经过精心设计的：先传输最常用的码长值（0、8 等），这样尾部的零可以省略，进一步节省空间。

七、gzip、zlib 与 PNG 中的 DEFLATE

7.1 封装格式对比

DEFLATE 只定义了压缩数据流本身，不包含任何元数据。实际应用中，它被不同的封装格式包裹：

gzip 头部包含魔数（1f 8b）、压缩方法、时间戳、操作系统标识等。zlib 头部更简洁，只有压缩方法和标志字节。ZIP 格式则在自己的 Local File Header 中封装 raw DEFLATE 流。

7.2 gzip 格式细节

+---+---+---+---+---+---+---+---+---+---+
|ID1|ID2| CM|FLG|     MTIME     |XFL| OS|   10 bytes
+---+---+---+---+---+---+---+---+---+---+
|...compressed data (DEFLATE)...|
+---+---+---+---+---+---+---+---+
|     CRC32     |     ISIZE     |          8 bytes trailer
+---+---+---+---+---+---+---+---+

ID1 = 0x1f, ID2 = 0x8b    (魔数)
CM  = 8                    (DEFLATE)
FLG = 各种标志位 (FTEXT, FHCRC, FEXTRA, FNAME, FCOMMENT)

7.3 PNG 中的 DEFLATE

PNG 图像格式在 IDAT chunk 中使用 zlib 封装的 DEFLATE 流。PNG 对原始像素数据先做行滤波（Sub, Up, Average, Paeth），将像素差值化以降低熵，然后再交给 DEFLATE 压缩。

这是一个教科书式的预处理+压缩的管线：

原始像素 -> 行滤波(差值化) -> zlib/DEFLATE 压缩 -> IDAT chunk

行滤波的效果非常显著。对于摄影图片，滤波后的数据熵通常能降低 30-50%，大幅提升压缩率。

7.4 HTTP Content-Encoding

现代 Web 几乎全部使用 DEFLATE（以 gzip 封装）来压缩传输内容：

请求:
GET /api/data HTTP/1.1
Accept-Encoding: gzip, deflate, br

响应:
HTTP/1.1 200 OK
Content-Encoding: gzip
Content-Length: 1234

<gzip 压缩的数据>

值得注意的是，HTTP 中的 Content-Encoding: deflate 实际上是 zlib 格式（带 zlib 头部），而不是 raw DEFLATE。这是一个历史遗留的命名混淆，曾导致许多互操作性问题。现代实践中建议直接使用 gzip，避免使用 deflate。

八、完整的 C 实现

以下是一个完整的 Huffman 编解码器实现，包含频率统计、树构建、规范编码生成、编码和解码功能。

/* huffman.c -- Huffman 编解码器完整实现
 * 编译: gcc -O2 -o huffman huffman.c
 * 用法: ./huffman < input > output
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define MAX_SYMBOLS   256
#define MAX_CODE_LEN  15

/* ---------- 数据结构 ---------- */

typedef struct {
    uint32_t freq;
    int16_t  left;
    int16_t  right;
    int16_t  parent;
} HuffNode;

typedef struct {
    uint16_t code;
    uint8_t  len;
} HuffCode;

typedef struct {
    uint8_t *buf;
    size_t   cap;
    size_t   byte_pos;
    uint8_t  bit_pos;
} BitStream;

/* ---------- 比特流操作 ---------- */

static void bs_init(BitStream *bs, size_t cap) {
    bs->buf = (uint8_t *)calloc(cap, 1);
    bs->cap = cap;
    bs->byte_pos = 0;
    bs->bit_pos = 0;
}

static void bs_write_bit(BitStream *bs, int bit) {
    if (bs->byte_pos >= bs->cap) {
        bs->cap *= 2;
        bs->buf = (uint8_t *)realloc(bs->buf, bs->cap);
        memset(bs->buf + bs->cap / 2, 0, bs->cap / 2);
    }
    if (bit)
        bs->buf[bs->byte_pos] |= (1 << bs->bit_pos);
    bs->bit_pos++;
    if (bs->bit_pos == 8) {
        bs->bit_pos = 0;
        bs->byte_pos++;
    }
}

static void bs_write_bits(BitStream *bs, uint16_t val, uint8_t nbits) {
    for (uint8_t i = 0; i < nbits; i++)
        bs_write_bit(bs, (val >> i) & 1);
}

static int bs_read_bit(BitStream *bs) {
    if (bs->byte_pos >= bs->cap)
        return -1;
    int bit = (bs->buf[bs->byte_pos] >> bs->bit_pos) & 1;
    bs->bit_pos++;
    if (bs->bit_pos == 8) {
        bs->bit_pos = 0;
        bs->byte_pos++;
    }
    return bit;
}

static size_t bs_total_bits(BitStream *bs) {
    return bs->byte_pos * 8 + bs->bit_pos;
}

static void bs_free(BitStream *bs) {
    free(bs->buf);
}

/* ---------- 频率统计 ---------- */

static void count_freq(const uint8_t *data, size_t len, uint32_t freq[]) {
    memset(freq, 0, MAX_SYMBOLS * sizeof(uint32_t));
    for (size_t i = 0; i < len; i++)
        freq[data[i]]++;
}

/* ---------- Huffman 树构建 ---------- */

static int build_tree(uint32_t freq[], HuffNode nodes[], int *root) {
    int heap[MAX_SYMBOLS * 2];
    int heap_size = 0;
    int node_count = 0;

    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (freq[i] == 0) continue;
        nodes[node_count].freq   = freq[i];
        nodes[node_count].left   = -1;
        nodes[node_count].right  = -1;
        nodes[node_count].parent = -1;
        heap[heap_size++] = node_count++;
    }

    if (node_count == 0) return 0;
    if (node_count == 1) {
        *root = 0;
        return node_count;
    }

    /* 简单的选择式最小堆（适用于小字母表） */
    for (int step = 0; step < node_count - 1; step++) {
        /* 找最小的两个 */
        int min1 = -1, min2 = -1;
        for (int i = 0; i < heap_size; i++) {
            int idx = heap[i];
            if (idx < 0) continue;
            if (min1 < 0 || nodes[idx].freq < nodes[heap[min1]].freq) {
                min2 = min1;
                min1 = i;
            } else if (min2 < 0 || nodes[idx].freq < nodes[heap[min2]].freq) {
                min2 = i;
            }
        }

        int left  = heap[min1];
        int right = heap[min2];

        nodes[node_count].freq   = nodes[left].freq + nodes[right].freq;
        nodes[node_count].left   = (int16_t)left;
        nodes[node_count].right  = (int16_t)right;
        nodes[node_count].parent = -1;
        nodes[left].parent  = (int16_t)node_count;
        nodes[right].parent = (int16_t)node_count;

        heap[min1] = node_count;
        heap[min2] = -1;
        node_count++;
    }

    *root = node_count - 1;
    return node_count;
}

/* ---------- 从树提取码长 ---------- */

static void extract_lengths(HuffNode nodes[], int root, int node_count,
                            uint8_t code_len[], int sym_map[]) {
    /* BFS/DFS 计算深度 */
    uint8_t depth[MAX_SYMBOLS * 2];
    memset(depth, 0, sizeof(depth));

    for (int i = node_count - 1; i >= 0; i--) {
        if (nodes[i].left >= 0)
            depth[nodes[i].left] = depth[i] + 1;
        if (nodes[i].right >= 0)
            depth[nodes[i].right] = depth[i] + 1;
    }

    memset(code_len, 0, MAX_SYMBOLS);
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].left == -1 && nodes[i].right == -1) {
            int sym = sym_map[i];
            code_len[sym] = depth[i];
        }
    }
}

/* ---------- 规范 Huffman 编码 ---------- */

static void canonical_codes(uint8_t code_len[], HuffCode codes[]) {
    uint16_t bl_count[MAX_CODE_LEN + 1] = {0};
    uint16_t next_code[MAX_CODE_LEN + 1] = {0};

    for (int i = 0; i < MAX_SYMBOLS; i++)
        if (code_len[i] > 0)
            bl_count[code_len[i]]++;

    uint16_t code = 0;
    for (int bits = 1; bits <= MAX_CODE_LEN; bits++) {
        code = (code + bl_count[bits - 1]) << 1;
        next_code[bits] = code;
    }

    for (int i = 0; i < MAX_SYMBOLS; i++) {
        codes[i].len = code_len[i];
        if (code_len[i] > 0) {
            codes[i].code = next_code[code_len[i]]++;
        } else {
            codes[i].code = 0;
        }
    }
}

/* ---------- 编码 ---------- */

static void huff_encode(const uint8_t *data, size_t len,
                         HuffCode codes[], BitStream *out) {
    /* 先写入原始数据长度（32 bits） */
    bs_write_bits(out, (uint16_t)(len & 0xFFFF), 16);
    bs_write_bits(out, (uint16_t)((len >> 16) & 0xFFFF), 16);

    /* 写入码长表（每个符号 4 bits，最大码长 15） */
    for (int i = 0; i < MAX_SYMBOLS; i++)
        bs_write_bits(out, codes[i].len, 4);

    /* 写入编码后的数据（注意：规范码按 MSB 顺序写入） */
    for (size_t i = 0; i < len; i++) {
        uint8_t sym = data[i];
        uint16_t c = codes[sym].code;
        uint8_t  l = codes[sym].len;
        /* MSB-first: 反转比特顺序写入 */
        for (int b = l - 1; b >= 0; b--)
            bs_write_bit(out, (c >> b) & 1);
    }
}

/* ---------- 解码 ---------- */

static size_t huff_decode(BitStream *in, uint8_t *out, size_t out_cap) {
    /* 读取原始数据长度 */
    uint32_t lo = 0, hi = 0;
    for (int i = 0; i < 16; i++)
        lo |= (uint32_t)bs_read_bit(in) << i;
    for (int i = 0; i < 16; i++)
        hi |= (uint32_t)bs_read_bit(in) << i;
    size_t orig_len = lo | (hi << 16);

    if (orig_len > out_cap)
        return 0;

    /* 读取码长表 */
    uint8_t code_len[MAX_SYMBOLS];
    for (int i = 0; i < MAX_SYMBOLS; i++) {
        code_len[i] = 0;
        for (int b = 0; b < 4; b++)
            code_len[i] |= (uint8_t)(bs_read_bit(in) << b);
    }

    /* 重建规范编码 */
    HuffCode codes[MAX_SYMBOLS];
    canonical_codes(code_len, codes);

    /* 构建解码查找表 */
    int16_t decode_sym[1 << MAX_CODE_LEN];
    memset(decode_sym, -1, sizeof(decode_sym));

    for (int s = 0; s < MAX_SYMBOLS; s++) {
        if (codes[s].len == 0) continue;
        int pad_bits = MAX_CODE_LEN - codes[s].len;
        uint16_t base = codes[s].code << pad_bits;
        for (int p = 0; p < (1 << pad_bits); p++)
            decode_sym[base | p] = s;
    }

    /* 逐符号解码 */
    size_t decoded = 0;
    while (decoded < orig_len) {
        uint16_t bits = 0;
        size_t save_byte = in->byte_pos;
        uint8_t save_bit = in->bit_pos;

        for (int i = 0; i < MAX_CODE_LEN; i++) {
            int b = bs_read_bit(in);
            if (b < 0) return decoded;
            bits = (bits << 1) | b;
        }

        int16_t sym = decode_sym[bits];
        if (sym < 0) return decoded;

        out[decoded++] = (uint8_t)sym;

        /* 回退多读的比特 */
        int consumed = codes[sym].len;
        int overread = MAX_CODE_LEN - consumed;
        in->byte_pos = save_byte;
        in->bit_pos  = save_bit;
        for (int i = 0; i < consumed; i++)
            bs_read_bit(in);
    }

    return decoded;
}

/* ---------- 主函数 ---------- */

int main(int argc, char *argv[]) {
    /* 读取输入 */
    size_t cap = 1 << 20;  /* 1 MB 初始缓冲 */
    uint8_t *data = (uint8_t *)malloc(cap);
    size_t len = 0;
    int ch;

    while ((ch = fgetc(stdin)) != EOF) {
        if (len >= cap) {
            cap *= 2;
            data = (uint8_t *)realloc(data, cap);
        }
        data[len++] = (uint8_t)ch;
    }

    if (len == 0) {
        fprintf(stderr, "空输入\n");
        free(data);
        return 1;
    }

    /* 统计频率 */
    uint32_t freq[MAX_SYMBOLS];
    count_freq(data, len, freq);

    /* 构建 Huffman 树 */
    HuffNode nodes[MAX_SYMBOLS * 2];
    int sym_map[MAX_SYMBOLS * 2];
    int node_idx = 0;
    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (freq[i] > 0)
            sym_map[node_idx++] = i;
    }

    int root;
    int total_nodes = build_tree(freq, nodes, &root);

    /* 提取码长并生成规范编码 */
    uint8_t code_len[MAX_SYMBOLS];
    extract_lengths(nodes, root, total_nodes, code_len, sym_map);

    HuffCode codes[MAX_SYMBOLS];
    canonical_codes(code_len, codes);

    /* 打印编码表到 stderr */
    fprintf(stderr, "=== Huffman 编码表 ===\n");
    fprintf(stderr, "%-6s %-6s %-8s %-18s\n", "符号", "频率", "码长", "编码");
    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (codes[i].len == 0) continue;
        char bits[MAX_CODE_LEN + 1];
        for (int b = codes[i].len - 1; b >= 0; b--)
            bits[codes[i].len - 1 - b] = ((codes[i].code >> b) & 1) ? '1' : '0';
        bits[codes[i].len] = '\0';

        if (i >= 32 && i < 127)
            fprintf(stderr, "'%c'    %-6u %-8u %s\n", i, freq[i], codes[i].len, bits);
        else
            fprintf(stderr, "0x%02X   %-6u %-8u %s\n", i, freq[i], codes[i].len, bits);
    }

    /* 编码 */
    BitStream encoded;
    bs_init(&encoded, len);
    huff_encode(data, len, codes, &encoded);

    size_t encoded_bits  = bs_total_bits(&encoded);
    size_t encoded_bytes = (encoded_bits + 7) / 8;

    fprintf(stderr, "\n原始大小:   %zu bytes\n", len);
    fprintf(stderr, "压缩大小:   %zu bytes (含头部)\n", encoded_bytes);
    fprintf(stderr, "压缩率:     %.2f%%\n", 100.0 * encoded_bytes / len);
    fprintf(stderr, "平均码长:   %.3f bits/symbol\n",
            (double)(encoded_bits - 32 - MAX_SYMBOLS * 4) / len);

    /* 解码验证 */
    uint8_t *decoded = (uint8_t *)malloc(len);
    encoded.byte_pos = 0;
    encoded.bit_pos  = 0;
    size_t dec_len = huff_decode(&encoded, decoded, len);

    if (dec_len == len && memcmp(data, decoded, len) == 0)
        fprintf(stderr, "解码验证:   通过\n");
    else
        fprintf(stderr, "解码验证:   失败 (decoded %zu / %zu bytes)\n", dec_len, len);

    /* 输出压缩数据 */
    fwrite(encoded.buf, 1, encoded_bytes, stdout);

    /* 清理 */
    free(data);
    free(decoded);
    bs_free(&encoded);
    return 0;
}

代码说明

上述实现包含以下核心模块：

1. BitStream：比特级读写，支持动态扩容。DEFLATE 规范中比特是 LSB-first 的，但规范 Huffman 码是 MSB-first 的，编码时需要注意这一差异。
2. build_tree：使用简单选择法实现最小优先队列，对于 256 个符号的字母表足够高效。
3. canonical_codes：严格按照 RFC 1951 的算法生成规范 Huffman 码。
4. huff_encode/huff_decode：编码器直接查表，解码器使用前缀查找表实现快速解码。

九、压缩率与速度：实测数据

9.1 测试方法

使用 zlib 1.3 在不同压缩级别下测试，输入数据来自常见的基准测试集：

平台: x86-64, GCC 13.2, -O2
CPU:  AMD Ryzen 7 5800X @ 3.8 GHz
内存: DDR4-3600 32GB

9.2 Canterbury Corpus 基准测试

9.3 不同数据类型的压缩表现

9.4 压缩级别与吞吐量

级别    压缩率(Canterbury avg)    编码速度(MB/s)    解码速度(MB/s)
 1      35.1%                    285               480
 2      34.2%                    240               480
 3      33.5%                    195               480
 4      32.6%                    155               480
 5      32.0%                    120               480
 6      31.6%                    95                480
 7      31.4%                    78                480
 8      31.2%                    55                480
 9      31.1%                    42                480

关键观察：

• 压缩率的提升幅度随级别递减：从级别 1 到 6 改善约 3.5%，从 6 到 9 仅改善 0.5%。
• 解码速度与压缩级别无关——DEFLATE 的不对称设计使得”压缩一次、解压多次”成为理想选择。
• 默认级别 6 是一个经过深思熟虑的工程折中。

十、工程实践中的陷阱

在实际项目中使用 DEFLATE 相关技术时，有许多容易踩到的坑。以下是一份总结：

十一、与其他压缩算法的对比

11.1 压缩算法全景

              压缩率
              ^
              |
  LZMA/xz    |  *
              |
  bzip2       |     *
              |
  zstd        |        *          <-- 相同压缩率下速度快 5-10 倍
              |
  gzip/DEFLATE|           *
              |
  LZ4         |                *
              |
  Snappy      |                  *
              |
              +-----------------------> 解压速度

11.2 横向对比

11.3 DEFLATE 仍然重要的原因

尽管 zstd 在几乎所有维度上都优于 DEFLATE，后者仍然无处不在：

1. 标准化和兼容性：ZIP、gzip、PNG、HTTP 等标准已经深度绑定 DEFLATE。
2. 普遍的硬件支持：Intel QAT、IBM z15 等硬件加速器原生支持 DEFLATE。
3. 足够好：对于大多数 Web 传输场景，gzip 的压缩率已经足够，且 CPU 开销可控。
4. 简单可审计：相比 zstd 的复杂实现，DEFLATE 的规范只有几页纸，更容易进行安全审计。

十二、个人思考

12.1 算法之美

Huffman 编码是贪心算法的经典范例——每一步都做出局部最优选择，最终得到全局最优解。其证明之优雅、实现之简洁，堪称算法设计的教科书。而 DEFLATE 则展示了工程师的智慧：将两种互补的技术（LZ77 处理重复模式，Huffman 消除统计冗余）组合在一起，达到了 1+1>2 的效果。

12.2 压缩与信息论的哲学

从信息论的视角看，压缩的本质是去除冗余——找到数据的更紧凑表示。Shannon 熵定义了这个过程的理论极限。有趣的是，这个极限并不是由算法决定的，而是由数据本身的统计特性决定的。换言之，数据中”蕴含”了多少信息，是一个客观的量。

这引出了一个更深层的问题：Kolmogorov 复杂度——一个字符串的最短描述长度。与 Shannon 熵不同，Kolmogorov 复杂度不假设概率模型，而是基于通用图灵机。遗憾的是，它是不可计算的。但它提供了一个优美的理论框架：压缩就是理解，理解就是压缩。一个好的压缩算法，本质上是在”理解”数据的结构。

12.3 DEFLATE 的遗产

DEFLATE 诞生于一个特殊的时代：内存以 KB 计量，CPU 主频不到 100 MHz，而互联网刚刚起步。Phil Katz（PKZIP 的作者）设计 DEFLATE 时做出的许多决策——32KB 窗口、15 位最大码长、固定的长度/距离表——都带有那个时代的烙印。

三十年过去了，这些参数在今天看来当然不够理想。但 DEFLATE 的整体架构——LZ77 前端+Huffman 后端+分块独立压缩——至今仍是压缩算法的主流范式。zstd 本质上也是这个架构，只是在每个环节都做了现代化的升级：有限状态熵编码（FSE）替代 Huffman，更大的窗口，更高效的匹配查找。

12.4 写给实践者

对于日常工程实践，我的建议是：

1. 新项目优先考虑 zstd。它在压缩率和速度两个维度上都显著优于 gzip，且 API 设计更现代。
2. 需要兼容性时用 gzip。与旧系统交互、HTTP Content-Encoding、生成 ZIP 文件等场景，gzip 仍然是最安全的选择。
3. 理解原理比使用库更重要。当你遇到压缩相关的 bug 时（比如流式传输中的 flush 问题、多成员 gzip 文件、PNG 解码异常），理解 DEFLATE 的内部机制会让你事半功倍。
4. 永远不要信任压缩数据的大小声明。解压时限制输出大小是防止压缩炸弹的基本措施。

12.5 进一步阅读

• RFC 1951: DEFLATE Compressed Data Format Specification
• RFC 1950: ZLIB Compressed Data Format Specification
• RFC 1952: GZIP file format specification
• D.A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, 1952
• C.E. Shannon, “A Mathematical Theory of Communication”, 1948
• Zstandard (RFC 8478): 现代替代方案
• Mark Adler 的 zlib 源码——堪称 C 语言工程的典范

附录：DEFLATE 比特流解析示例

为了加深理解，我们手动解析一段 DEFLATE 比特流。考虑用 gzip 压缩字符串 "AABCAAB"：

原始数据 (hex): 41 41 42 43 41 41 42
长度: 7 bytes

gzip 输出 (hex):
1f 8b 08 00 00 00 00 00 00 03    -- gzip 头 (10 bytes)
73 74 74 72 76 04 51 00          -- DEFLATE 压缩数据
a4 0e 2f ab 07 00 00 00          -- CRC32 + ISIZE

解析 DEFLATE 部分（比特级）：

字节 73: 0111 0011
  BFINAL = 1        (最后一个块)
  BTYPE  = 01       (静态 Huffman)

使用静态 Huffman 编码表:
  'A' (0x41) -> 8-bit: 00110001  (literal 值 65, 对应 8-bit 编码)
  'A' (0x41) -> 00110001
  'B' (0x42) -> 00110010
  'C' (0x43) -> 00110011
  然后编码器发现 "AAB" 在前面出现过:
    length=3, distance=4
    length code 258 -> 7-bit: 0000010
    distance code 4 -> 5-bit + 1 extra bit
  end-of-block (256) -> 7-bit: 0000000

这个例子展示了 DEFLATE 如何在一个块内混合使用字面量和 LZ77 回引。对于这么短的输入，LZ77 的收益有限（因为回引本身也需要编码开销），但对于更大的输入，重复模式的匹配会带来显著的压缩收益。

附录：关键数据结构速查

DEFLATE 长度码表 (完整):
Code  Extra  Length     Code  Extra  Length     Code  Extra  Length
257    0       3        267    1     15-16      277    4     67-82
258    0       4        268    1     17-18      278    4     83-98
259    0       5        269    2     19-22      279    4     99-114
260    0       6        270    2     23-26      280    4     115-130
261    0       7        271    2     27-30      281    5     131-162
262    0       8        272    2     31-34      282    5     163-194
263    0       9        273    3     35-42      283    5     195-226
264    0      10        274    3     43-50      284    5     227-257
265    1     11-12      275    3     51-58      285    0     258
266    1     13-14      276    3     59-66

DEFLATE 距离码表 (完整):
Code  Extra  Distance       Code  Extra  Distance
  0    0       1              15    7     193-256
  1    0       2              16    8     257-384
  2    0       3              17    8     385-512
  3    0       4              18    9     513-768
  4    1       5-6            19    9     769-1024
  5    1       7-8            20   10     1025-1536
  6    2       9-12           21   10     1537-2048
  7    2      13-16           22   11     2049-3072
  8    3      17-24           23   11     3073-4096
  9    3      25-32           24   12     4097-6144
 10    4      33-48           25   12     6145-8192
 11    4      49-64           26   13     8193-12288
 12    5      65-96           27   13     12289-16384
 13    5      97-128          28   14     16385-24576
 14    6     129-192          29   14     24577-32768

上一篇: MPMC Channel 下一篇: LZ 字典压缩 相关阅读: - 算术编码与 ANS - zstd 深度解剖