36. 信息论与数据压缩

1. 信息量与熵

1.1 信息量

一个事件「越不可能发生」，它一旦发生带来的信息量就越大。香农把这件事写成了公式：

I(x) = -log₂ P(x)     单位：比特（bit）

直觉校验：抛一枚公平硬币，P = 1/2，I = -log₂(1/2) = 1 比特，正好是「一个是非问题的答案」。必然事件 P = 1，I = 0——必然发生的事没有信息量。

1.2 熵的定义

熵是信息量的期望，即一个随机变量平均携带多少比特：

H(X) = -Σ p(x) log₂ p(x)

核心性质：

• 0 ≤ H(X) ≤ log₂|X|，等号右侧当且仅当均匀分布时取得。
• 熵只由分布决定，与具体编码方式无关——它是数据的固有属性。

1.3 熵就是压缩极限

如果一段数据每个符号的熵是 H 比特，那么任何无损编码平均每个符号至少需要 H 比特。这是数据压缩的物理下界，任何号称「压缩到低于熵」的方案要么在骗人，要么利用了数据本身不是该分布（建模错误）。

import math
from collections import Counter

def entropy(data: bytes) -> float:
    n = len(data)
    freq = Counter(data)                          # 统计字节频率
    return -sum((c / n) * math.log2(c / n) for c in freq.values())

raw = b"abracadabra abracadabra abracadabra"
print(f"字节数={len(raw)} 经验熵={entropy(raw):.3f} bit/byte")
print(f"理论最小={len(raw) * entropy(raw) / 8:.1f} 字节")

2. 联合熵、条件熵与互信息

2.1 三个量

给定两个随机变量 X、Y：

联合熵   H(X,Y) = -ΣΣ p(x,y) log₂ p(x,y)
条件熵   H(Y|X) = -ΣΣ p(x,y) log₂ p(y|x)
互信息   I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)

2.2 链式法则与关系

H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)

几条必须记住的关系：

• 条件降低熵：H(Y|X) ≤ H(Y)，知道 X 只会减少（不会增加）对 Y 的不确定性。
• 互信息对称：I(X;Y) = I(Y;X) ≥ 0，等号当且仅当 X 与 Y 独立。
• 互信息 = 压缩收益：I(X;Y) 衡量知道 X 后 Y 能省下多少比特，这正是「用上下文预测下一个符号」类压缩器（PPM、上下文混合、LLM 式建模）的理论依据。

2.3 相对熵与交叉熵

KL 散度   D(p‖q) = Σ p(x) log₂ (p(x)/q(x))     ≥ 0，不对称
交叉熵    H(p,q) = H(p) + D(p‖q)

工程含义：若编码模型 q 与真实分布 p 不一致，代价就是多付出 D(p‖q) 比特/符号。压缩器的建模越准，KL 越小，输出越短——这也是机器学习中交叉熵损失的信息论解释。

3. 信源编码定理

3.1 无失真信源编码定理

香农第一定理：对离散无记忆信源的 N 次扩展，存在唯一可译变长编码，其平均码长 L̄ 满足：

H(X) ≤ L̄ < H(X) + 1/N

含义有两层：

1. 下界不可突破：平均码长不可能低于熵。
2. 上界可以逼近：通过块编码（把 N 个符号一起编码），每符号的冗余可以压到任意小。

3.2 前缀码与 Kraft 不等式

唯一可译要求编码不含歧义。最实用的充分条件是前缀码（任何码字都不是另一个码字的前缀），它能即时译码、无需回看。

Kraft 不等式给出前缀码存在的充要条件（码字长度 l₁…lₘ，字母表大小 D）：

Σ D^(-lᵢ) ≤ 1

3.3 定长与变长

定长编码平均码长恒为 log₂ n，适合均匀分布（ASCII、UTF-32）；变长前缀码（Huffman、Shannon-Fano）平均码长 ≥ H(X)，适合偏斜分布；算术编码平均码长 ≈ H(X)，适用面最广（JPEG、H.264 的 CABAC）；字典编码（LZ77、LZW）的码长取决于数据重复度。

结论：分布越偏斜，变长编码相对定长编码收益越大。全 0 的数据熵为 0，可以压到几乎无长度。

4. Huffman 编码

4.1 构造算法

Huffman 编码是最优前缀码，贪心构造：

1. 统计每个符号的频率，每个符号建一个叶子节点。
2. 取频率最小的两个节点，合并为一个新节点，权值为两者之和。
3. 把新节点放回集合，重复直到只剩一个根节点。
4. 从根到叶的路径（左 0 右 1）即码字。

4.2 一个完整例子

符号频率：a:45, b:13, c:12, d:16, e:9, f:5

合并 f(5)+e(9)=14 ；合并 c(12)+b(13)=25 ；合并 14+d(16)=30
合并 25+30=55 ；合并 45+55=100（根）
结果码字（一种可能）: a=0  c=100  b=101  f=1100  e=1101  d=111
平均码长 = (45*1 + 12*3 + 13*3 + 5*4 + 9*4 + 16*3)/100 = 2.24 bit
熵 = 2.236 bit    ← 平均码长紧贴熵

4.3 代码实现

import heapq
from collections import Counter

def huffman(data: bytes):
    freq = Counter(data)
    heap = [[w, [sym, ""]] for sym, w in freq.items()]    # 叶子节点
    heapq.heapify(heap)
    while len(heap) > 1:
        lo, hi = heapq.heappop(heap), heapq.heappop(heap) # 最小 + 次小
        for pair in lo[1:]: pair[1] = '0' + pair[1]       # 左分支补 0
        for pair in hi[1:]: pair[1] = '1' + pair[1]       # 右分支补 1
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[1]), p))

4.4 最优性与局限

最优性：Huffman 编码在所有前缀码中平均码长最小（可用交换论证证明）。但它有三个限制：

• 需要先统计频率：必须两遍扫描，或把码表随数据一起传输。
• 每符号至少 1 比特：某符号概率 p > 0.5 时，熵可以小于 1 比特，但 Huffman 给不了（码字长度是整数）。
• 只利用符号频率，不利用上下文：ab 与 ba 频率相同但出现顺序不同，Huffman 看不出差别。

改进方向：块 Huffman（多个符号一起编码）、算术编码（突破整数码长）、上下文建模（利用互信息）。

5. 算术编码与区间编码

5.1 核心思想

算术编码不把每个符号映射为码字，而是把整个消息映射为 [0,1) 区间里的一个实数：

初始区间 [0.0, 1.0)
每读一个符号 s：
    新区间长度 = 旧区间长度 × p(s)
    新区间起点 = 旧起点 + 旧长度 × (所有比 s 小的符号概率之和)
最后在剩余区间里任取一个足够短的小数作为码字

5.2 例子

字母表 {a:0.5, b:0.25, c:0.25}，编码消息 "ab"：

初始 [0.000, 1.000)
读 a（p=0.5, cum=0.0）:  [0.000, 0.500)
读 b（p=0.25, cum=0.5）: [0.250, 0.375)  ← 长度 0.125 = 0.5*0.25
取区间内小数 0.3125 = 0.0101₂，用 4 比特表示

"ab" 的熵是 -log₂(0.5) - log₂(0.25) = 3 比特，算术编码给出 4 比特，差距仅来自有限精度。

5.3 与 Huffman 的对比

**区间编码（range coding）**是算术编码的整数实现，用 32 位整数做区间收缩，避免浮点，速度更快且无专利问题，被 LZMA、bzip2、zstd 的熵编码阶段采用。

6. LZ77、LZ78 与 LZW

6.1 LZ77：滑动窗口 + 反向引用

LZ77 用「指向已出现内容的引用」代替重复串。每个 token 是三元组：

(距离 offset, 长度 length, 下一字符 next)

例：abcabcabc 编码为 (0,0,a) (0,0,b) (0,0,c) (3,6,EOF)——「回退 3 个字节，复制 6 个」即还原出后两段 abc。

• 滑动窗口：只在最近 W 字节里找匹配（DEFLATE 用 32 KB），限制内存与搜索成本。
• 懒惰匹配：发现更长匹配时放弃当前较短匹配，能略微提升压缩率。
• 代表：DEFLATE（gzip/zip/png）、LZMA（7z）、Snappy、LZ4。

/* LZ77 匹配的简化示意：暴力在窗口内找最长匹配 */
typedef struct { int offset, length; unsigned char next; } Token;

Token longest_match(const unsigned char *win, int win_len,
                    const unsigned char *cur, int cur_len) {
    Token best = {0, 0, cur[0]};
    for (int d = 1; d <= win_len && d <= 32768; ++d) {
        int len = 0;
        while (len < cur_len && win[win_len - d + len] == cur[len]) ++len;
        if (len > best.length) { best.offset = d; best.length = len; }
    }
    return best;      /* 实际实现用哈希链把 O(n*W) 降到近似 O(n) */
}

6.2 LZ78 与 LZW

LZ78 维护一个显式字典，每次输出 (字典索引, 新字符) 并把新串加入字典。LZW（Welch 改进）做了两个关键简化：

• 字典初始化为所有单字符，因此不再需要输出「新字符」。
• 输出只有索引，字典在编解码两端同步构建，无需传输字典。

输入 ABABABA，初始字典 A=1 B=2
读 AB → 输出 1(A)，加入 AB=3 ；读 AB → 命中 3，输出 3(AB)，加入 ABA=4
读 BA → 输出 2(B)，加入 BA=5  ... 输出序列: 1 3 2 5 ...

注意：LZW 早期专利（Unisys）导致 GIF 之后诞生了 PNG。LZW 至今仍用于 TIFF、PDF 的部分场景。

6.3 字典压缩的适用边界

选择依据是压缩率 × 吞吐 × 内存三者权衡，而非单看压缩比。

7. DEFLATE 与 zstd 的工程取舍

7.1 DEFLATE 的两级结构

DEFLATE（RFC 1951）是「LZ77 + Huffman」的经典组合：

原始数据 ──▶ LZ77 匹配（滑动窗口 32 KB）──▶ 长度/距离符号序列
          ──▶ Huffman 编码（每块动态码表，或固定码表）──▶ 比特流

关键细节：

• 匹配长度 3258，距离 132768，都用变长前缀码编码。
• 每块可选用动态 Huffman（自带码表，码表本身也 Huffman 压缩）或固定 Huffman。
• 存储模式（stored block）直接原样输出，用于不可压缩数据。

gzip -9 -c big.log > big.log.gz && ls -l big.log.gz     # 高压缩，慢
zstd -19 -T0 big.log -o big.log.zst                     # 多线程，高压缩

# 用 Python 观察 zlib 级别对压缩率的影响
python3 -c "
import zlib
data = b'the quick brown fox ' * 2000
for lvl in (1, 6, 9):
    c = zlib.compress(data, lvl)
    print(f'level={lvl} {len(data)} -> {len(c)} ratio={len(data)/len(c):.2f}')
"

7.2 zstd 的现代设计

zstd（Zstandard）在 DEFLATE 的基础上做了几处工程改进：

• 有限状态熵（FSE） 替代 Huffman 做熵编码，支持分数比特，压缩率更高。
• 可训练字典：小文件压缩率极差是 DEFLATE 的痛点，zstd 用 zstd --train 训练共享字典，小文件压缩率可提升数倍。
• 多线程与长距离匹配：-T0 启用全部核心，长距离匹配器可跨数百 MB 找重复。
• 速度等级：从 -1（> 500 MB/s）到 -19（高压缩），且解码速度与等级几乎无关，这对存储场景很关键。

7.3 选型决策

8. 有损压缩基础

8.1 为什么可以「有损」

无损压缩受熵限制，而有损压缩改变数据本身：只要人感知不到差异，就可以丢弃信息。关键前提是感知模型——人眼对亮度比对色度敏感、对低频比对高频敏感。

8.2 量化的核心地位

量化是有损压缩的心脏，把连续值映射到有限个离散级别：

q = round(x / Q)      量化
x̂ = q × Q            反量化，误差 ≤ Q/2

量化步长 Q 越大，压缩率越高、失真越大。所有有损编解码器（JPEG、MP3、H.264）的核心都是在感知不敏感的地方放大 Q。

8.3 DCT 与 JPEG 流程

JPEG 用 8×8 离散余弦变换把空间域转成频率域：

① 色彩空间转换 RGB → YCbCr，并对 Cb/Cr 下采样（4:2:0，色度分辨率减半）
② 分成 8×8 块
③ 每块做 DCT，得到 64 个频率系数（左上为直流 DC，其余为交流 AC）
④ 用量化表逐系数除以 Q 并取整（高频系数量化得更狠）
⑤ 之字形扫描（zigzag）把低频系数排前面
⑥ DC 差分 + AC 游程编码
⑦ Huffman 熵编码

import numpy as np
from scipy.fftpack import dct

block = np.full((8, 8), 128.0)                         # 纯灰块
D = dct(dct(block.T, norm='ortho').T, norm='ortho')    # 二维 DCT
Q = np.array([...])                                    # JPEG 标准量化表（略）
quant = np.round(D / Q)                                # 量化：大量系数归零
# 平坦块量化后只剩 DC 非零，AC 全为 0 -> 熵编码后极短

质量因子 QF 只是对标准量化表做整体缩放：QF=50 用原表，QF=90 把表缩小到 0.2 倍（保留更多细节）。

8.4 其他有损编码

音频 MP3/AAC 用心理声学模型（掩蔽效应）决定量化精度；视频 H.264/H.265 在 JPEG 流程之上加入运动补偿（帧间预测），只编码残差；神经网络量化 INT8/INT4 权重同样是量化，用精度换推理速度与显存。

9. 信道编码与纠错码入门

9.1 与信源编码的分工

信源编码去冗余、压缩数据（追求短）；信道编码加冗余、抵抗传输错误（追求可靠）。香农第二定理（有噪信道编码定理）指出：只要传输速率低于信道容量 C，就存在编码使错误率任意小——代价是引入冗余。

9.2 汉明码

汉明码用 k 个校验位覆盖 2^k - 1 个位置，能纠正 1 位错误。经典 (7,4) 码：4 位数据 + 3 位校验。

位置:      1   2   3   4   5   6   7
类型:     p1  p2  d1  p4  d2  d3  d4
校验覆盖: p1:1,3,5,7   p2:2,3,6,7   p4:4,5,6,7
接收后计算伴随式 (s4 s2 s1)，其二进制值即错误位置；
为 0 则无错，否则翻转该位即完成纠正。

汉明距离 d=3 意味着「可纠 1 位、可检 2 位」。一般地，纠 t 位错需要 d ≥ 2t+1。

9.3 里德-所罗门码

RS 码工作在符号（通常是字节）而非比特上，适合突发错误（如划痕、丢包）：

• 一个 RS(n, k) 码用 n-k = 2t 个校验符号，能纠正 t 个符号错误。
• 广泛用于 CD/DVD、QR 码、DSL、深空通信。
• **纠删码（erasure coding）**变体是分布式存储的核心：把数据切成 k 块，编码出 m 个校验块，任意丢失 ≤ m 块都能恢复。相比三副本（300% 开销），RS(10,4) 只需 140% 开销。

9.4 编码方案的取舍

奇偶校验只能检 1 位（内存 ECC 的一部分）；汉明码纠 1 位、开销中等（内存 ECC、早期存储）；CRC 只检错不纠错，用于网络帧与文件校验；RS 码纠多个符号，用于光盘、QR 与存储；LDPC 与 Turbo 码可逼近信道容量，用于 5G、SSD 与深空通信。

趋势：LDPC 与 Polar 码在 5G 与 SSD 主控中逐渐取代 RS，因为它们更接近香农极限，但编解码复杂度更高。

10. 常见陷阱

• 以为压缩可以无限进行：无损压缩的下界是熵，重复压缩已压缩数据通常只会变大。
• 对已压缩数据再压缩：JPEG、MP4、zip 内部已接近熵极限，外层 gzip 几乎无收益且浪费 CPU。
• 忽视压缩带来的 CPU 成本：高等级 zstd/xz 可能吃掉数倍 CPU 时间，高吞吐场景应选 LZ4。
• 小文件直接压缩：几百字节的文件用 DEFLATE 反而变大（码表开销），应使用预训练字典。
• 混淆有损与无损：JPEG 反复保存会累积失真，编辑流程中应保留原始无损素材。
• Huffman 用于概率 > 0.5 的符号：整数码长限制使其无法低于 1 比特，此时应改用算术编码。
• 把 CRC 当纠错码：CRC 只检错不纠错，检测到错误只能重传。
• 纠删码忽略重建带宽：EC 省存储，但重建时需读取 k 倍数据，网络与 IO 压力远高于副本。

参考文章

• 算法复杂度 — Huffman 贪心与 LZ 匹配的复杂度分析
• 贪心与回溯 — Huffman 编码的贪心最优性证明
• 文件系统与 IO — 压缩文件系统的透明压缩实现
• 分布式系统基础 — 副本与纠删码在存储层的取舍