3. 香农编码：从第一定理到手算趣事

香农编码，说白了就是信息论里最早的那套编码方法。它不像哈夫曼编码那么流行，但它的思想——用更少的比特表示更常见的东西——是所有压缩技术的根基。我个人觉得，搞懂香农编码，才算真正摸到了压缩的门槛。

3.1 香农第一定理：无失真编码的极限

香农第一定理，也叫无失真信源编码定理。它告诉我们一件事：任何无损压缩，平均码长都不可能小于信源的熵。

嗯，这里要注意。这个定理不是告诉你具体怎么编，而是给你画了一条红线。你编得再好，也跨不过去。

我在项目中遇到过不少刚入行的同学，上来就问「这个压缩率能到多少？」。其实你先算算信源的熵，心里就有底了。如果熵是 4.5 bit，那平均码长至少 4.5 bit，低于这个数就是骗人的。

3.2 香农编码算法：一步一步来

香农编码的算法其实很直白。你想想看，它就是把概率大的符号分到短的码字，概率小的分到长的码字。具体怎么做？

1. 排序：把所有符号按概率从大到小排好。
2. 算累积概率：从第一个符号开始，累加前面的概率。
3. 定码长：每个符号的码长 l(i) = ⌈-log₂ p(i)⌉。
4. 取二进制小数：把累积概率转成二进制，取前 l(i) 位。

举个例子，假设有 4 个符号：

符号	概率	累积概率	码长	二进制小数	码字
A	0.5	0.0	1	0.0	0
B	0.25	0.5	2	0.10	10
C	0.125	0.75	3	0.110	110
D	0.125	0.875	3	0.111	111

你看，概率大的 A 只用了 1 位，概率小的 C 和 D 用了 3 位。这就是香农编码的直觉。

3.3 编码效率计算

编码效率 η 的定义很简单：

η = H(S) / L̄ × 100%

拿上面的例子算一下：

• 熵 H = -0.5·log₂0.5 - 0.25·log₂0.25 - 0.125·log₂0.125 - 0.125·log₂0.125 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bit
• 平均码长 L̄ = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bit
• 效率 η = 1.75 / 1.75 × 100% = 100%

这个例子刚好达到了极限。但现实中很少这么完美。香农编码的效率通常比哈夫曼编码低一点，因为它的码长是向上取整的，会浪费一些比特。

3.4 我当年手算香农编码的趣事

说到手算，我想起大学时的一件糗事。

那时候刚学香农编码，老师布置了一道题：给 8 个符号，概率分别是 0.4、0.2、0.1、0.1、0.05、0.05、0.05、0.05。要求手算码字并验证唯一可译性。

我算到第三个符号就卡住了。累积概率 0.6 的二进制是 0.100110011...，无限循环。码长是 3 位，取前三位是 100。但下一个符号的累积概率 0.7，二进制是 0.101100110...，取前三位也是 100。两个符号码字冲突了！

我当时急得满头汗，翻书查资料，最后发现香农编码的原始论文里提到：如果冲突，就把后一个符号的码长加 1 位。于是我把第二个符号的码长从 3 改成 4，码字变成 1011，这才解了围。

那次之后我养成了一个习惯：手算完一定要检查前缀条件。后来做嵌入式系统时，有个同事用香农编码压缩传感器数据，没检查前缀，结果解压出来的数据全是乱码。我帮他排查了一下午，最后发现是码字冲突。嗯，从那以后我再也不敢跳过这步了。

3.5 香农编码的完整流程

下面这张图总结了香农编码的完整流程，从输入符号概率到输出码字：

3.6 香农编码 vs 其他编码

香农编码虽然理论意义重大，但实际应用中用得不多。我整理了一个对比表：

特性	香农编码	哈夫曼编码	算术编码
编码方式	基于累积概率	基于二叉树	基于区间划分
码长	整数，向上取整	整数，最优	分数，接近熵
效率	中等	高	极高
实现复杂度	低	中	高
前缀条件	需手动检查	自动满足	不适用

你看，香农编码的优势在于实现简单，适合教学和理解。但真要上生产环境，我建议用哈夫曼或算术编码。不过话说回来，没有香农编码打底，你很难理解后面那些更复杂的算法。