数据压缩原理：Huffman、LZ 家族与通用压缩算法

引言

文件、网络、数据库里到处是压缩——.zip、.tar.gz、HTTP 的 gzip/brotli、日志的 zstd。但大多数人都把压缩当"黑盒命令"，不知道它到底在压什么。本文拆开这个黑盒：先讲熵——压缩的下限来自信息量本身（为什么压缩不了随机数据）；再讲两大基石——Huffman（频率驱动）与 LZ 家族（重复驱动），以及把两者结合的 Deflate（gzip 的内核）；接着对比现代算法 zstd/brotli/LZMA，最后给工程决策：级别怎么选、分块与字典怎么用、什么时候压缩不值得。

前置：/others-big-o-complexity-guide/（复杂度视角看压缩算法）、/others-binary-encoding-tools/（字节与位层面的工具）。存储与网络底层的压缩见 [[database]]、[[network]]。

目录

• 1. 熵：压缩的下限来自信息量
• 2. Huffman 编码：用频率换短码
• 3. Huffman 实战：编解码与注意点
• 4. LZ77：滑动窗口的重复检测
• 5. LZ78 与 LZW：字典的另一种建法
• 6. Deflate：LZ + Huffman 的黄金组合
• 7. 现代算法：zstd、brotli 与 LZMA
• 8. 工程决策：级别、分块、字典与格式选型
• 9. 什么时候压缩不值得
• 10. 速查表与一句话记忆
• 延伸阅读

1. 熵：压缩的下限来自信息量

信息论基本事实：一串数据能压到多小，取决于它的熵（entropy）——每个符号平均携带多少比特信息。

熵 = -Σ p(x) · log2 p(x)   （p(x) 是符号 x 的出现概率）

均匀分布的 8 种符号 → 熵 = 3 比特/符号（无可压缩）
一个符号占 90% 的其他均匀   → 熵 ≈ 0.9 · 0.15 + ... ≈ 远小于 3 比特

直觉：越"意外"的信息越多。aaaaaa... 几乎不意外 → 熵极低 → 能压得很小；随机字节 每个都很意外 → 熵=8 比特/字节 → 几乎压不动。

为什么随机数据压不动：没有可利用的模式（频率均匀 + 无重复）。任何声称能"无损压缩随机数据"的方案都违背香农第二定律。

import math

def entropy(data):
    from collections import Counter
    cnt = Counter(data)
    n = len(data)
    return -sum((c / n) * math.log2(c / n) for c in cnt.values())

print(entropy(b"aaaaabbbbb"))      # 约 1.0（可压）
print(entropy(bytes(range(256))))  # 8.0（不可压）

记忆：压缩的对手是"规律性"的稀缺——熵越低越能压，随机数据是熵的天花板。

2. Huffman 编码：用频率换短码

目标：给高频符号分配短码、低频符号分配长码，让平均码长最短。

前缀码（prefix code）：任何码字都不是另一个码字的前缀 → 解码无歧义、不需要分隔符。

构建算法：

1. 统计每个符号的出现频率
2. 反复取两个频率最小的节点合并成新节点（频率相加）
3. 左子支标 0、右子支标 1 → 从根到叶的路径就是码字

示例：AAABBC

A×3, B×2, C×1
合并 B+C(3) → 与 A(3) 合并成根(6)
  根(6)
  ├─0: A           → "A" = 0        (1 bit)
  └─1: 节点(3)
     ├─0: B        → "B" = 10       (2 bits)
     └─1: C        → "C" = 11       (2 bits)

编码结果：AAA BB C → 0 0 0 10 10 11 → 8 bits
定长 2 比特要 12 bits → 压缩比 2/3

解码：从根开始，按位走 0/1，到叶输出符号并回到根——单遍 O(长度)。

注意点：

• Huffman 是最优前缀码，但它不是唯一的——相同频率可能有多种树。
• 码表需要随数据一起存储/传输（deflate 用"规范 Huffman"简化码表）。
• 对二进制数据，频率可能很均匀 → 收益有限 → 需要 LZ 那类"重复检测"。

# Huffman 建树（示意）
import heapq
from collections import Counter

def build_tree(data):
    heap = [[w, [c, ""]] for c, w in Counter(data).items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap); hi = heapq.heappop(heap)
        for p in lo[1:]: p[1] = '0' + p[1]
        for p in hi[1:]: p[1] = '1' + p[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return dict(heap[0][1:])

记忆：Huffman 吃"频率不均"——高频短码、低频长码、前缀码免歧义；它管符号级，不管"重复的长串"。

3. Huffman 实战：编解码与注意点

编码（把源数据逐符号换成码字）：

def encode(data, table):
    return ''.join(table[b] for b in data)

解码（用前缀树逐位走）：

def decode(bits, tree):
    out, node = [], tree
    for bit in bits:
        node = node[int(bit)]
        if isinstance(node, int):          # 叶子
            out.append(node)
            node = tree
    return bytes(out)

文件里的真实做法：deflate 用规范 Huffman（canonical）——只存每个符号的码长，按特定顺序重建码表，省掉整棵树的存储。

三个工程注意点：

1. 码表开销：小文件光存码表就占不少 → 小文件常"不压还小"（见第 9 节）
2. 均匀数据的无力：二进制随机/已压缩数据，Huffman 几乎无收益
3. 顺序编码 vs 分组：分组（block）编码可让大文件按块独立解压、容错更好

与"重复"的关系："ababababab" 只有 2 个符号、频率各半 → Huffman 编码 1 bit/符号 ≈ 熵 1 bit，但真实压缩能远低于 1 bit——因为"ab"整串在重复，这需要 LZ 而不是 Huffman。

记忆：Huffman 是"按符号压"，对重复长串无能为力——那正是 LZ 家族的主场。

4. LZ77：滑动窗口的重复检测

LZ77 的核心洞察：数据里的重复是跨符号的长串（"the quick brown fox the quick"），而不是单个字符的频率。

思想：维护一个滑动窗口（已编码的历史缓冲区），当当前内容在窗口内出现过，就输出一个 （距离, 长度）引用 而不是重复的原文。

历史窗口 ←←←←← | ←← 待编码输入 →→
"A B C A B D ..."
         ↑ 在窗口内找到 "AB"，输出 (dist=2, len=2)，而不是重发 "AB"

压缩流程（示意）：

输入: "ABABAB"
窗口: 空 → 编码 "A" (字面量 A)
窗口: A → 编码 "B" (字面量 B)
窗口: AB → "AB" 匹配 → 输出 (dist=2, len=2)
窗口: ABAB → 匹配可延伸 → 输出 (dist=2, len=2)  ← "AB" 重叠匹配
结果: A B (2,2) (2,2)  vs 原 6 字节

关键实现点：

• 重叠匹配：(dist, len) 里 len 可大于 dist（如 "aaaa" 编码成 (1,3)）——这压的是"一个字节的重叠重复"。
• 哈希链：用哈希找窗口内候选位置，避免线性扫描整个窗口。
• 窗口大小：越大找重复越远，但查找成本越高（用哈希缓解）。

LZ77 的产物：(字面量 | (距离, 长度)) 的 token 流——这一步之后通常再交给熵编码（见第 6 节 Deflate）。

记忆：LZ77 是"滑动窗口 + 重叠匹配"——把重复长串变成 (距离,长度)，是 Deflate/zstd 的压缩骨架。

5. LZ78 与 LZW：字典的另一种建法

LZ78 不用固定窗口，而是增量构建字典（每个新串存入字典，下次引用字典下标）：

输入: "ABABABAB"
过程:
  "A"  不在字典 → 输出 (0,'A')，字典[1]="A"
  "AB" 不在字典 → 输出 (1,'B')，字典[2]="AB"
  "ABA" 不在字典 → 输出 (2,'A')，字典[3]="ABA"
  "AB" 已在字典(2) → 继续...

LZW（Lempel-Ziv-Welch）：LZ78 的著名变体，专利时代的 GIF 就用它——只输出字典下标，不输出字符（初始化字典含所有单字节）。

LZW 的著名案例：GIF、TIFF 使用；unix compress 用它。特点：解压时不需传字典（解码器同步重建），但遇到大字典会退化。

LZ77 vs LZ78 对比：

为什么要知道 LZW：很多"老格式为什么这么大/这么怪"的历史问题都源于 LZW 的专利与字典退化——现代压缩几乎都是 LZ77 系（Deflate/zstd/brotli）的天下。

记忆：LZW 是"字典下标化"的 LZ78，够经典但已退居历史；现代压缩全线走 LZ77 窗口路线。

6. Deflate：LZ + Huffman 的黄金组合

gzip 的内核就是 Deflate——它是两层压缩的教科书组合：

输入数据
  ↓ LZ77：滑动窗口去重 → (字面量 | 距离-长度) token 流
  ↓ Huffman：对 token 流做熵编码（两棵 Huffman 树：字面量树 + 距离树）
  → Deflate 位流

三个 key 细节：

1. 分层：LZ 抓重复、Huffman 抓频率——各自处理自己擅长的
2. 数据块：数据分成独立 block，每块可单独解压（流式、容错）
3. 压缩级别：级别越高 → 窗口越大 + 匹配更充分 → 比率高但更慢

级别在 gzip 里的体现：

gzip -1 file    # 最快、压缩率最低
gzip -6 file    # 默认平衡
gzip -9 file    # 最慢、压缩率最高（zlib 上限）

为什么 Deflate 仍是 HTTP 默认（HTTP 的 gzip）：解压极快、实现简单、兼容性 100%——对"传输为主、CPU 敏感"的场景，压缩率略低但解压速度与生态无可替代。

# 看 gzip 实际压出多少
echo "hello hello hello hello hello hello hello" | gzip | wc -c   # 很小

记忆：Deflate = LZ77 去重 + Huffman 熵编码——分层各自擅长；它赢在解压速度与兼容，而不是极限压缩率。

7. 现代算法：zstd、brotli 与 LZMA

三大现代算法都在 Deflate 思路上做工程优化：

zstd 的三件杀手锏：

1. 压缩/解压速度惊人：-3 级别接近 gzip 速度但比率更好
2. 可训练字典：对小样本（JSON 记录、日志行）自定义字典 → 大幅提升
3. 流式 API + 多线程：内存安全、可增量压缩

brotli 的 web 优势：内置约 120KB 的静态字典（常见 HTML/CSS/JS 单词与片段），对"短小文本网页"往往胜过 gzip 20%+。这就是为什么 HTTP 响应头常写 Content-Encoding: br。

LZMA 的极端比率：区间编码比 Huffman 更贴近熵下限，配合更大的匹配窗口——代价是压缩极慢、内存高。

# 命令级对比
zstd -3 file.txt > file.zst     # 快速、比率好
brotli -q 5 file.txt > file.br  # web 内容首选
xz -6 file.txt                  # LZMA，高比率慢压缩

记忆：zstd 是速度与比率的甜点、brotli 吃 web 文本、LZMA 冲极限比率——级别与算法一起选，别只认 gzip。

8. 工程决策：级别、分块、字典与格式选型

压缩级别不是越高越好——工程里选级别是"CPU 预算 × 比率"的权衡：

写路径（日志/缓存落盘）：
  高并发写 → 要低 CPU → zstd -1/-3 或 gzip -1
  低频写、读多    → 可高级别一次压到位
读路径（HTTP 响应）：
  浏览器解压很快 → 服务器端压缩级别可以放宽

分块（chunking）：把大文件/流切成独立块压缩——好处是随机访问（解一块不用解整个）与容错（一块坏了别的不受影响）。这就是 Parquet/ClickHouse 列存做块压缩的底层逻辑。

字典压缩（zstd）：对"每行结构相似"的数据（日志、JSON、数据库记录），用样本训练字典，压缩率可提升 30%+：

# 训练字典
zstd --train sampled.log -o dict     # 用代表性样本训字典
zstd -D dict -3 data.log             # 压缩时带字典
zstd -D dict -d data.log.zst -o out  # 解压也要同字典

格式选型速查：

记忆：选压缩 = 选"CPU 预算 × 比率 × 访问模式"——写路径求快、读多可压狠、分块换随机访问、字典喂给相似样本。

9. 什么时候压缩不值得

压缩不是免费的午餐，四个"不值得"：

1. 数据已压缩/随机：图片(jpg)、视频、已压缩归档 → 再压几乎无收益还耗 CPU
2. 小数据：几十字节的请求/日志行 → 头开销（格式头+码表）可能比原文还大
3. 写路径 CPU 紧张：每写一次都压缩，CPU 成为瓶颈
4. 无需传输的本地数据：只在本地读、不跨网络 → 压缩换不来传输收益

小数据示范：

import zlib
payload = b'{"ok": true, "n": 1}'   # 26 字节
compressed = zlib.compress(payload)
print(len(compressed))              # 可能 30+ 字节 → 比原文大！

收益公式：

净收益 = (压缩省下的传输/存储) - (压缩 CPU + 头开销 + 解压 CPU)
数据小 → 头开销吃掉收益；数据随机 → 省不下来

工程红线：压缩要加大小阈值——低于阈值（如 128B/1KB）直接原样传输，避免"压了个寂寞"。

记忆：压缩的账要算净收益——已压缩/随机/极小/本地数据，压了都是亏；设阈值，别做"无脑压缩"。

10. 速查表与一句话记忆

全篇速查：

一句话记忆：压缩的对手是熵——随机数据压不动；Huffman 吃频率、LZ77 吃重复，Deflate 把两者合二为一；现代选型 zstd 快而平衡、brotli 吃 web、LZMA 冲比率；写路径求低 CPU、读多可压狠、块压缩换随机访问、字典喂相似样本；数据已压缩/随机/极小就别压——压缩之前先算净收益。

延伸阅读

• /others-big-o-complexity-guide/ — 压缩算法的复杂度与工程权衡
• /others-binary-encoding-tools/ — 字节与位的底层工具
• /serialization-formats-compare/ — 序列化与压缩的关系
• [[database]] — 列存块压缩的工程实现
• [[network]] — HTTP 内容编码（gzip/brotli）