霍夫曼如何构建最优代码
Hamming 提出霍夫曼编码是一种贪心算法，它构建最小平均长度的前缀无关码。关键思想：从下向上构建树，总是合并两个概率最低的符号。
前向传递（构建）
1. 按概率从高到低排序所有符号。
2. 取两个概率最低的符号。将它们组合成一个新的元符号，其概率 = 两个符号的概率之和。
3. 在其排序位置插入元符号。
4. 重复，直到只剩两个符号。
5. 将0和1分配给剩余的两个符号。
后向传递（分配代码）
按相反顺序撤销合并：在每次分割时，被合并的两个符号接收与其组合父节点相同的前缀位，加上一个额外的0（一个子节点）或1（另一个子节点）。0/1的分配是任意的——要么有效。
为什么这是最优的：如果任何其他代码有较小的平均长度 L'，应用相同的前向约简最终会产生两个符号，其平均长度小于1比特——对2符号代码不可能。矛盾。
追踪算法
Hamming的例子：四个符号 A, B, C, D，其中 p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125。
前向传递：
步骤1：排序：A(0.5), B(0.25), C(0.125), D(0.125)。最低两个：C, D。
步骤2：合并CD，p=0.25。新列表：A(0.5), B(0.25), CD(0.25)。
步骤3：最低两个：B(0.25), CD(0.25)。合并BCD，p=0.5。
步骤4：两个符号剩余：A(0.5), BCD(0.5)。分配 A=0, BCD=1。
后向传递：
BCD → B 得 10, CD 得 11。CD → C 得 110, D 得 111。
最终代码：A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3)。
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 比特。
多个有效的霍夫曼代码
Hamming 指出了非唯一性的两个来源：
1. 任意的0/1分配。 在每次分割时，你可以给任一子节点0。在整个过程中交换0和1给出一个具有相同 L 的不同代码。
2. 并列打破。 当两个节点具有相等的概率时，任一个都可以被放置得'更高'（先合并）。不同的并列打破选择可以产生结构不同的树——'长'vs'茂密'——具有相同的 L 但不同的代码长度分布。
长树与茂密树
长树（偏斜）： 每个深度级别一个符号（Fibonacci类似结构）。代码长度差异很大：一个符号得到短代码，其他的级联到更长的代码。
茂密树（平衡）： 符号在深度级别上均匀分布。代码长度聚集在平均值附近。较低的方差。
Hamming 的建议：当有选择时，优先选择茂密树。相同的 L，但代码长度的方差更小 → 更统一的解码时间 → 实时应用中更小的缓冲要求。
计算代码长度方差
代码长度的方差：Var = E[l²] − (E[l])²
对于代码 {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3}，其中 p=[0.5, 0.25, 0.125, 0.125]：
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
等概率符号的替代茂密代码使用所有长度2的代码：L=2, Var=0。
压缩收益与符号分布
Hamming 的规则：霍夫曼编码只在符号概率差异很大时才值得。
等概率。 如果所有2^k个符号都有相等的概率1/2^k，霍夫曼生成块码：每个符号得到长度k。L = H = k。没有优于简单块码的收益。
偏斜概率。 如果一个符号占主导（p >> 1/2^k对其他），霍夫曼给它分配一个非常短的代码（长度1或2），戏剧性地降低 L。
逗号码 (Hamming的术语)。当每个概率超过剩余总数的2/3时，霍夫曼自然产生：p(s1)→0, p(s2)→10, p(s3)→110, ...，直到最后两个等长代码。这是'逗号码'：1后的尾0像逗号一样。
Hamming 注意到：现实数据压缩（备份、文件归档）当源具有偏斜概率时可以减少超过一半的存储——英文文本是主要例子。
霍夫曼与块代码：数值比较
Hamming 的第二个例子：p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30。
块码：8个符号 → 每个3比特 → L_block = 3。
Hamming 计算霍夫曼代码并报告 L_Huffman ≈ 2.58 比特。
节省：(3 − 2.58)/3 ≈ 14% 相对块编码的压缩。
当符号概率差异很大时（此处1/3对1/30，10:1比率），变长编码有很大的收益。
自编译程序
Hamming 以一个惊人的想法结束第11章：霍夫曼编码器可以编码自己。解码树（告诉解码器如何读取压缩消息）与压缩数据一起传输。接收方不需要事先知道代码。
编码器：对数据采样，估计概率，构建霍夫曼代码，将解码树编码为头部，然后对数据编码。
解码器：读取头部以重建树，然后使用它解码数据。
Hamming 的观点：这整个管道可以作为库函数运行，不需要人类参与。你调用它，它自动压缩和解压。现代归档格式（ZIP, gzip, bzip2）实现完全相同的模式。
更深层的原则：智能在于算法，而非固定的码表。算法适应它接收到的任何数据。这是 Hamming 在所有伟大工程系统中看到的模式：内置适应性，而非后来加上的。