数据压缩

数据压缩看起来像一个工程问题：给文本、图像、语音找一种更短的表示方式，节省存储和传输成本。但信息论把它变成了一个更尖锐的问题：

给定信源分布 $p(x)$，在完全无损恢复的前提下，平均至少要用多少个符号来表示一个信源符号？

这个问题分两层回答：

1. 理论层：熵 $H(X)$ 决定了任何无损压缩都绕不过去的下界。
2. 构造层：Shannon 码、Huffman 码、Shannon-Fano-Elias 编码、算术编码分别提供了不同程度逼近这个下界的办法。

第5章解决"极限在哪里"，第6章解决"怎么逼近这个极限"。读这两章时，最重要的主线不是背算法，而是始终围绕下面这条链条：

信源分布 $\to$ 可译码约束 $\to$ 码长分配 $\to$ 平均码长 $\to$ 熵下界 $\to$ 具体构造

设离散信源随机变量为 $X$，取值集合为 $\mathcal{X}=\{x_1,\dots,x_m\}$，概率分布为 $p(x)$。一个 $D$ 元信源编码 $C$ 把每个符号映射成一个由 $D$ 个码元组成的有限长字符串：

其中：

• $\mathcal{D}$ 是大小为 $D$ 的码字字母表，例如二进制时 $\mathcal{D}=\{0,1\}$
• $\mathcal{D}^*$ 表示所有有限长字符串的集合
• $l(x)$ 表示符号 $x$ 的码字长度

若按概率 $p(x)$ 发送符号，则编码的期望长度定义为：

这就是压缩问题的目标函数。我们希望 $L(C)$ 越小越好。

但并不是随便给高概率符号分短码、低概率符号分长码就行。编码还必须满足可译码性，否则接收端无法唯一恢复原消息。

几种重要的编码类型

• 非奇异码：不同源符号对应不同码字。
• 唯一可译码：任意有限长源符号序列的编码结果都能唯一反解。
• 前缀码 / 即时码：没有任何一个码字是另一个码字的前缀，从左到右读码时不必等后续符号即可立刻判定边界。

graph LR
    A["信源符号
X ~ p(x)"] --> B["编码器
C(x)"]
    B --> C["码字序列
011001..."]
    C --> D["译码器
C⁻¹"]
    D --> E["恢复符号
X̂"]
    style A fill:#dbeafe,stroke:#2563eb
    style E fill:#dcfce7,stroke:#16a34a
    style B fill:#fef3c7,stroke:#d97706
    style D fill:#fef3c7,stroke:#d97706

前缀码最容易实现，也最重要。很多定理先对前缀码证明，再推广到唯一可译码。

一旦进入可变长编码，最核心的问题就变成：哪些码长分配是可实现的？ Kraft 不等式给出精确答案。

码树几何直观：为什么是 $D^{-l_i}$

把所有可能码字想成一棵 $D$ 叉树：

• 树根是空串，第 1 层有 $D$ 个长度为 1 的串，第 $l$ 层一共有 $D^l$ 个长度为 $l$ 的字符串。
• 一个长度为 $l_i$ 的码字，相当于在第 $l_i$ 层占据了一个叶子节点。
• 由于前缀码要求码字之间不能互为前缀，一个叶子一旦被占，它下面整棵子树都不能再放别的码字。

如果把第 $l_i$ 层的一个叶子折算成"整棵树容量"的比例：

所有码字占用总量不能超过整棵树容量 1，于是得到 $\sum D^{-l_i} \le 1$。

充分性证明思路（构造性）

给定一组满足 $\sum D^{-l_i}\le 1$ 的正整数 $l_i$，如何构造前缀码？

1. 把所有符号按码长从小到大排序：$l_{(1)}\le l_{(2)}\le\cdots\le l_{(m)}$
2. 按顺序逐一分配码字：维护当前可用节点集合（初始为根）
3. 每次取当前队列中第一个可用节点，从它往下走 $l_i$ 步得到的叶子即作为码字
4. 该叶子被占后，其所有祖先保持可用（以支持同层其他码字），但该叶子以下子树标记为不可用

不等式保证整个过程中队列永远不会为空——容量始终够用。

一个直观例子

设二进制码长为 $(1,2,3,3)$，则

这说明这组码长刚好把整棵二叉树"装满"，对应码字：

如果某组码长使求和大于 1，例如 $(1,1,1)$，则

这说明二叉树容量不够，根本不可能构造出前缀码。

现在我们已经知道哪些码长可行，接下来要问：最优码长大概应该长成什么样？

先暂时忽略"码长必须是整数"这个离散限制，把优化问题放松成实数变量：

为什么把不等式改成等式？因为如果严格小于 1，说明码树还有空余，还能继续缩短某些码字，期望长度就还能下降，所以最优点一定会把容量用满。

用拉格朗日乘子法，设

对 $l_i$ 求偏导并令其为 0：

于是得到

这就是最理想的码长分配。把它代回平均长度：

其中 $H_D(X)= -\sum_i p_i\log_D p_i = \frac{H(X)}{\log_2 D}$ 表示以 $D$ 为底度量的熵。

为什么现实里通常达不到精确等号

真实编码里每个码字长度必须是整数，所以理想值 $-\log_D p_i$ 往往无法直接实现。例如 $p_i=0.3$ 时，$-\log_2 0.3 \approx 1.737$ 比特，不可能真的分配 1.737 个比特。于是熵变成了一个理论下界。

压缩效率对比：三种码长的差距

用同一个概率分布来比较 Shannon 码、Huffman 码与熵的差距：

以概率分布 $(0.4, 0.3, 0.2, 0.1)$ 为例：Huffman 码长 $1.9$ bit，仅比熵 $1.846$ bit 高 $0.054$ bit；Shannon 码取上取整后为 $2.0$ bit，略逊一筹。

下界为什么成立

对任意唯一可译码，MacMillan 不等式说明 Kraft 约束仍然成立。令

则 $q_i$ 是一个合法分布。将平均码长写成

再利用相对熵非负性 $D(p\|q)=\sum_i p_i\log_D\frac{p_i}{q_i}\ge 0$，推出 $L\ge H_D(X)$。

上界为什么成立

构造 Shannon 码，令 $l_i=\left\lceil \log_D \frac{1}{p_i} \right\rceil$。因为 $l_i \ge \log_D \frac1{p_i}$，所以 $D^{-l_i}\le p_i$，求和得 $\sum_i D^{-l_i}\le 1$，于是由 Kraft 不等式可构造出前缀码。另一方面，利用上取整不超过多加 1：

乘上 $p_i$ 并求和得 $H_D(X) \le L < H_D(X)+1$。

为什么分组编码能把"+1"磨掉

如果把 $n$ 个源符号打包成一个超级符号来编码，那么块熵变成 $H_D(X^n)=nH_D(X)$，而 Shannon 码给出的总块长只比它多不到 1。于是平均到每个原始符号：

当 $n\to\infty$ 时，额外损失 $1/n$ 消失。这就是"熵是可逼近的极限"的精确含义。

Shannon 码的思想非常朴素：既然理想码长是 $-\log_D p_i$，那就直接把它向上取整。

它的优点是：构造简单、理论分析干净、自动满足 $H_D(X) \le L < H_D(X)+1$。缺点是它只根据单个概率算码长，没有进一步优化码树结构，因此在逐符号编码里通常不如 Huffman 码短。

例：Shannon 码长怎么来

若概率分布为 $(0.4,0.3,0.2,0.1)$，则理想码长分别为

$(-\log_2 0.4, -\log_2 0.3, -\log_2 0.2, -\log_2 0.1) \approx (1.322, 1.737, 2.322, 3.322)$

向上取整后得到码长 $(2,2,3,4)$。它肯定可实现，但未必最优，因为高概率的第一个符号其实有机会只用 1 比特表示。

如果目标限定为逐符号、前缀、无损编码，那么 Huffman 编码给出了最优构造。它真正解决了这样一个问题：

在所有前缀码中，怎样让平均码长 $L$ 最小？

为什么"合并最小概率的两个符号"是对的

Huffman 算法背后有两个关键结构事实：

1. 最优前缀码中，概率最小的两个符号一定可以放在最深层，且码长相同。
2. 这两个最小概率符号的码字只在最后一位不同，因此可以先把它们视作一个"合并符号"，概率是两者之和。

这样，原问题就递归地缩小成一个更小规模的最优编码问题。这正是 Huffman 贪心策略成立的根源。

算法步骤

1. 把所有符号按概率放入最小堆
2. 每次取出概率最小的两个节点，合并成一个新节点，概率为二者之和
3. 重复直到只剩一个根节点
4. 从根向叶回溯，左支赋 0，右支赋 1，即得码字

flowchart TD
    subgraph Step1["第1步：合并最小概率两个符号"]
        A1["d: 0.1"] & B1["c: 0.2"] --> C1["n₁: 0.3"]
    end
    subgraph Step2["第2步：再次合并最小概率两个节点"]
        A2["a: 0.4"] & B2["b: 0.3"] & C2["n₁: 0.3"] --> D2["n₁+b: 0.6"]
    end
    subgraph Step3["第3步：合并最后两个节点"]
        A3["a: 0.4"] & D3["n₂: 0.6"] --> ROOT["根节点 1.0"]
    end
    style A1 fill:#dbeafe,stroke:#2563eb
    style B1 fill:#dbeafe,stroke:#2563eb
    style C1 fill:#fef3c7,stroke:#d97706
    style D3 fill:#fef3c7,stroke:#d97706
    style ROOT fill:#dcfce7,stroke:#16a34a

Huffman 码满足 $H(X) \le L_{\text{Huffman}} < H(X)+1$，而且在所有二元逐符号前缀码中，它的期望长度最短。

Huffman 码按符号一个个赋离散码字。Shannon-Fano-Elias 编码则开始把注意力转向概率区间。它是理解算术编码的关键过渡。

核心思想：区间中点

先把符号按某个顺序排列，定义累计分布

再定义修正后的中点累计量

直觉上，$\bar F(x_i)$ 就是符号 $x_i$ 对应概率区间的中点。然后取码长

并把 $\bar F(x_i)$ 的二进制展开前 $l(x_i)$ 位作为码字。

为什么区间中点能保证唯一译码

设符号 $x_i$ 的概率区间为 $[F(x_i),\ F(x_i)+p(x_i))$，其中点为 $\bar F(x_i)$。取前 $l(x_i)$ 位相当于在 $[0,1)$ 中选了一个长度为 $2^{-l(x_i)}$ 的小区间。由于 $l(x_i)$ 比 $\log_2 \frac1{p(x_i)}$ 多取了 1 位，所以这个小区间的宽度严格小于 $p(x_i)$，因此它完全落在符号 $x_i$ 自己的概率区间内部，不会碰到邻居区间。

所以不同符号的码字前缀区间互不相交，构成前缀码。

为什么额外多取 1 位

如果只取 $\lceil\log_2 \frac1{p_i}\rceil$ 位，截断误差可能导致二进制前缀恰好落在区间边界上，与邻居冲突。额外多取 1 位，相当于用宽度为 $2^{-l}$ 的小区间"盖住"区间中点，确保无论舍入规则如何，截断结果都落在该符号的概率区间内部。

Huffman 的瓶颈来自整数码长。即使某个符号理想码长是 1.37 bit，也只能给 1 bit 或 2 bit。算术编码绕开的办法是：

不再给每个符号单独分配一个码字，而是把整条消息映射成区间 $[0,1)$ 中的一个实数。消息越长，区间越窄，需要写出的二进制位数越精确，但平均到每个符号上就越接近熵。

基本过程

1. 先按符号概率把 $[0,1)$ 划分成若干子区间
2. 读入第一个符号后，保留其对应子区间
3. 再在这个子区间内按同样比例继续细分，对第二个符号选区间
4. 不断递归，最终整条消息对应一个极小区间
5. 输出该区间内任意一个二进制小数即可唯一表示整条消息

算术编码区间递归细分

设 $p(A)=0.6,\ p(B)=0.4$，初始区间 $[0,1)$。消息 BA 的编码过程：

每读入一个符号，就在当前区间内部按概率比例再次切分。最终消息 BA 对应区间 $[0.6,0.84)$，输出该区间内任一数（如 $0.75$）即可代表整条消息。

关键性质

• 消息越长，平均码率越接近熵 $H(X)$，因为额外开销（起始区间固定长度）被分摊到更多符号上。
• 能突破逐符号整数码长带来的浪费，在 JPEG、JPEG2000、H.264/AVC 等压缩系统中广泛使用。
• 实现复杂度比 Huffman 高，需要数值稳定处理以防止区间溢出。

课件中的 Python 实现

import collections

class ArithmeticCoder:
    def encode(self, data):
        freq = collections.Counter(data)
        total = len(data)

        prob_table = {}
        cum = 0.0
        for s in sorted(freq):
            p = freq[s] / total
            prob_table[s] = (cum, cum + p)
            cum += p

        low, high = 0.0, 1.0
        for s in data:
            rng = high - low
            lo, hi = prob_table[s]
            low, high = low + rng * lo, low + rng * hi

        return (low + high) / 2, prob_table, len(data)

每读取一个符号，就在当前区间内部按概率再次切分，最后返回区间中点作为编码结果。

从理论上讲，Huffman 码在期望意义上优于 Shannon 码，但两者差距不超过 1 比特。然而对于某些特定符号，Shannon 码反而可能给出更短的码字。