源编码与压缩

前两篇把不确定性变成了信息量。这一篇继续追问：⁠这些可能带小数的 bit，怎样变成能够完整解码的二进制文件？

我们依次看码字如何分配空间、熵为什么限制平均码长、怎样编码整条消息，以及长序列为什么能接近这个界。全文使用以 2 为底的对数；除特别说明外，符号表有限、概率模型已知，并忽略单独传输模型的成本。

前缀码：每个码字占据多少空间？

给符号分配二进制码字，还必须说明连续拼接后如何切分。⁠前缀码要求任何码字都不是另一个码字的前缀。例如 $A=0$、$B=10$、$C=110$、$D=111$，读到一个完整码字就可以输出一个符号，不需要分隔符。

把所有无限二进制串想成一棵不断分叉的树。前缀 0 占其中一半；10 占四分之一；每多确定一位，所占空间再减半。因此长度 $l_i$ 的码字占据比例 $2^{-l_i}$。前缀码的这些区域互不重叠，总占用不能超过 1：

$$K=\sum _i{2}^{-l_i}\le 1$$

这就是 Kraft 不等式⁠。对给定的整数码长，这个条件也足以保证存在一个对应的二进制前缀码。注意，它保证的是“能构造出来”，不是“随便挑一组同样长度的码字都不会冲突”。

图中先按码长从短到长摆放。长度为 $l$ 的码字也可对应区间 $[k/2^l,(k+1)/2^l)$；对齐二进制网格并保持不重叠，就能读出码字。总占用小于 1 时还有余量，所以码长不是无条件的零和关系⁠。只要剩余容量足够，缩短某个码字就不必改动其他码字；余量不足时才需要腾出空间。

熵为什么是平均码长的下界？

对一个二进制唯一可解码的符号码，令 $L={\sum }_{x}p(x)l_x$。Kraft–McMillan 不等式仍给出 $K\le 1$。我们可以把每个码字的空间占用归一化，得到一个分布：

$$q(x)=\frac{2^{-l_x}}{K}$$

于是 $-{\log }_{2}q(x)=l_x+{\log }_{2}K$。用上一章的交叉熵与 KL 分解，可把原来抽象的下界拆成两个明确的非负项：

$$L-H(p)=D_{KL}(p\parallel q)-{\log }_{2}K\ge 0$$

第一项是概率 $p$ 与码空间分配 $q$ 的失配，第二项来自未用满的码空间，因为 $K\le 1$，所以 $-{\log }_{2}K\ge 0$。这就解释了为什么不能在平均意义上压到熵以下。这里的码必须满足唯一可解码条件；不能忽略外部提供的长度、边界等信息，把任意一对一文件映射都直接套进这个结论。

对正概率符号取 $l_x=\lceil -{\log }_{2}p(x)\rceil$ 可以构造 Shannon 前缀码，得到：

$$H(X)\le L<H(X)+1$$

对独立同分布的 $n$ 个符号一起编码，由 $H(X^n)=nH(X)$ 得到：

$$H(X)\le \frac{L_n}{n}<H(X)+\frac{1}{n}$$

每一块的码长仍是整数，变小的是摊到每个符号上的取整开销。 这个平均长度结论直接由块编码得到，不需要先借助典型集。

公平骰子：2.585 bit，为什么平均要问 2.667 次？

任意是非提问策略都可表示为二叉决策树，根到叶的路径就是前缀码。公平骰子的熵为 ${\log }_{2}6\approx 2.585$ bit。一个最优树有两个深度为 2 的叶子、四个深度为 3 的叶子，因此：

$$L^{\ast }=\frac{2\times 2+4\times 3}{6}=\frac{8}{3}\approx \mathrm{2.667.}$$

最坏情况仍要 3 次。熵、平均提问次数与最坏次数各有不同含义；把多个独立结果分块编码，才可以摊薄整数码长的开销。

Huffman：保留树，就能看清码字如何产生

Huffman 编码反复合并当前概率最小的两个节点，直到形成根。两条分支分别标 0、1，从根到叶的路径就是码字。它在给定符号概率下，得到平均长度最优的二进制前缀码；概率相同的节点可能有不同但同样最优的排列。

沿分支读取即可得到码字：$A=0$、$B=10$、$C=110$、$D=111$。叶子越浅，码字越短。

这张树使用 $p=(0.5,0.25,0.125,0.125)$，所以：

$$L=0.5\times 1+0.25\times 2+0.125\times 3+0.125\times 3=1.75\text{bit}$$

所有正概率恰好都是 $2^{-l}$ 的形式，码长等于自信息，因此 $L=H=1.75$ bit。

一般情况下，Huffman 满足的是平均冗余 $0\le L-H<1$ bit/符号；这不是每个符号的码长与自信息之差都小于 1 的逐项保证。若只有两种结果、概率为 $(0.9,0.1)$，逐符号 Huffman 仍给两者各 1 bit，平均长度为 1；而熵只有约 0.469 bit。

把多个符号作为一个新符号做 Huffman 可以缩小差距，但码表会随块长快速增大。算术编码用另一种表示方法处理整条消息。

算术编码：概率连乘，信息量相加

从区间 $[0,1)$ 开始，按模型给出的概率分成若干子区间。每读一个符号，就保留它对应的一段，然后在这一段内部继续划分。若当前区间是 $[a,b)$，符号的累积概率范围是 $[F,F+q)$，更新为：

$$[a+(b-a)F,a+(b-a)(F+q))$$

关键是宽度每次乘上该符号的模型概率⁠。用条件概率模型编码一条消息时：

$$W_n=\prod _{i=1}^{n}q(x_i\mid x_{<i})$$

$$-{\log }_2{W}_n=\sum _{i=1}^n-{\log }_{2}q(x_i\mid x_{<i})$$

下面固定消息为 ABA，只改变模型 $q(A)=p$，其中 $q(B)=1-p$，各位置使用同一分布。三个阶段同时保留，并共用 $[0,1)$ 标尺，便于直接看见宽度的乘法。

在 $p=0.6$ 时，三个区间依次为 $[0,0.6)$、$[0.36,0.6)$、$[0.36,0.504)$。最终宽度为 $0.6\times 0.4\times 0.6=0.144$，理想信息长度约为 $2.796$ bit。

怎样输出实际比特？一种清楚的收尾方式是在最终区间内选一个完整的二进制网格单元 $[k/2^m,(k+1)/2^m)$，发送其 $m$ 位前缀。例如 011 对应 $[0.375,0.5)$，完全落在 ABA 的区间内。解码器使用相同概率划分，就能确定消息；这里还约定消息长度为 3，实际系统需要共享长度或终止规则。

所以算术编码仍然输出整数个 bit。它允许信息成本跨符号累积，最后统一付出有限的收尾开销。对理想精度、已知块长的这种构造，整块可做到 $-{\log }_{2}q(x^n)\le l(x^n)<-{\log }_{2}q(x^n)+2$；有限精度实现还要考虑重归一化、概率量化和文件头等成本。算法与区间构造可参阅 Stanford 算术编码讲义。

熵率：有上下文后，每个符号还剩多少不确定性？

独立假设下，联合熵等于单符号熵的 $n$ 倍。有依赖时，应该先使用链式法则：

$$H(X_1,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1})$$

若极限存在，⁠熵率定义为：

$$\bar{H}=\underset{n\to \infty }{\lim }\frac{1}{n}H(X_1,\dots ,X_n)$$

对有限字母表的平稳信源，这个极限存在，并等于逐渐加长历史后的条件熵极限。若还要使用下面的样本路径 AEP，通常进一步要求遍历性。

一个具体例子：令 $X_1$ 为公平比特，之后以概率 $r$ 翻转上一位、以概率 $1-r$ 保持，翻转选择彼此独立。每个位置单看仍是公平比特，熵为 1，但已知上一位后的不确定性只有 $h_2(r)$。因此：

$$H(X^n)=1+(n-1)h_2(r),\bar{H}=h_2(r)$$

当 $r=0.1$，熵率约为 0.469 bit/符号。压缩器利用的正是这种上下文冗余，不能只看单个符号的边缘频率。

把同一条序列交给两种预测器

下面两个固定样本的 0/1 总频率相同。独立模型始终给下一位概率 $1/2$；上下文模型知道上一位后，给“保持”概率 $1-r$、给“翻转”概率 $r$。改变 $r$，再逐位揭示，观察两份累计理想码长如何分开。

若前 $n$ 位中有 $k$ 次翻转，上下文模型的样本码长为

$$L(x^n)=1-k{\log }_{2}r-(n-1-k){\log }_2(1-r).$$

第一位花 1 bit。后面的每一次保持或翻转，都按相应条件概率付费。$r=0.5$ 时每一步都是 1 bit；$r=0.1$ 时连续保持便宜，意外翻转昂贵。⁠利用上下文不保证每条消息都更短⁠：若样本经常翻转，而模型认为翻转罕见，累计码长可以超过独立模型。只有在该源模型下取平均，才得到 $1+(n-1)h_2(r)$。

AEP：典型集小，为什么概率质量却大？

对独立同分布信源，序列的平均自信息是独立同分布随机量的平均。大数定律给出渐近等分性质（AEP）：

$$-\frac{1}{n}{\log }_{2}P(X^n)=\frac{1}{n}\sum _{i=1}^n-{\log }_{2}P(X_i)\stackrel{P}{\to }H(X)$$

固定容差 $\epsilon >0$，把平均自信息落在 $H\pm \epsilon$ 内的序列叫作典型集 $T_{n,\epsilon }$。其总概率随 $n$ 增大趋于 1，而每条典型序列的概率满足：

$$2^{-n(H+\epsilon )}\le P(x^n)\le 2^{-n(H-\epsilon )}$$

这里容易混淆两种“多”：⁠序列的条数占比⁠，与按真实分布采样时命中的概率⁠。下面固定 $P(1)=0.2$、$\epsilon =0.12$，用精确二项分布计算，不依赖随机模拟。

含 $k$ 个 1 的每条序列，概率都是 $0.2^{k}0.8^{n-k}$；这样的序列有 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 条。因此图中每组的总概率是 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)0.2^{k}0.8^{n-k}$，而计算条数时只累加 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$。这就是两个比例相差很大的原因。

如果典型集总概率至少是 $1-\delta$，由上面的单条概率界可得：

$$(1-\delta )2^{n(H-\epsilon )}\le |T_{n,\epsilon }|\le 2^{n(H+\epsilon )}$$

“约有 $2^{nH}$ 条”说的是这种指数增长率意义上的近似⁠，不是固定 $n$ 下的精确条数。固定容差下也不保证命中率随每一次 $n$ 增加都单调上升。一般的均匀信源可以让所有序列都典型，所以“条数占比很小”是这里非均匀二元例子的现象，不是 AEP 对所有信源的要求。

给典型序列编号，可以解释渐近固定码率、允许小错误概率的编码。要做严格无损压缩，非典型序列也必须能恢复，可以增加逃逸标记和后备编码；不能直接丢掉它们。相关定义见 Stanford AEP 讲义。

语言模型提供概率，熵编码器输出比特

语言模型给出 $q(x_i\mid x_{<i})$，算术编码等熵编码器把这些概率变成可还原的比特流。对同一份数据，理想比特率是：

$$\frac{1}{n}\sum _i-{\log }_{2}q(x_i\mid x_{<i})$$

它是这份样本上的经验负对数似然；在真实分布下取期望，才得到相应的交叉熵。用自然对数训练时还要除以 $\ln 2$ 才换算为 bit。在一致的单位和数据表示下，预测损失降低通常意味着理想编码成本降低，但某一条消息的码长不受“必须大于总体平均熵”这种逐条限制。

真实压缩系统还要计入模型、词表、长度或结束标记、文件头和数值精度。解码端必须复现同一套概率；若模型成本可被大量数据摊销，预测质量与压缩率的关系才更接近理想情况。Language Modeling Is Compression 研究了这一联系及语言模型的压缩表现。

BPE 通过合并常见相邻符号缩短 token 序列，但词表、概率分布和模型能力也随之改变。比较不同分词器时，应使用 bit/字节等共同单位，不能直接把更少 token 或更低的每 token 损失当作更好的文本压缩。见 Token 与采样。

下一篇讨论加入噪声后，怎样在冗余与可靠性之间取舍：信道容量与编码。压缩视角在语言模型中的应用见信息论与 LLM。

参考

• Stanford EE274：Kraft 不等式、熵与平均码长。
• Cover & Thomas，Elements of Information Theory，第 5 章：数据压缩；第 3 章：AEP。
• Stanford EE274：算术编码、AEP。
• Delétang et al., Language Modeling Is Compression (2023)。