Huffman 编码

深度每增加一，符号每次出现就多花一 bit，所以最小概率符号最适合占据最深叶。Huffman 算法先把两个最轻符号绑成同胞，相当于先决定它们共享最长前缀，再把这个合并节点当成一个概率为两者之和的新符号继续处理。

这是一个有证明义务的贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。：局部选择之所以安全，不是因为“概率小看起来该放深”，而是任何最优树都能通过交换改造成同意这个选择。

最优性的证明机制 ​

满二叉前缀树中，最深叶成对出现。把两个最小概率符号与一对最深同胞交换，只会把小权重移到不短的位置，因此平均长度不增；故存在一棵最优树让最小的两个概率 $p_a,p_b$ 成为最深同胞。

收缩这对同胞为权重 $q=p_a+p_b$ 的叶。任意收缩树的平均长度 $L^{\prime }$ 与展开后的长度满足

因为 $a,b$ 的码长各增加一。于是原问题的最优解等价于更小实例的最优解加固定成本 $q$；对符号数归纳即证明反复合并最小两项全局最优。

可复算例：$(0.4,0.3,0.2,0.1)$ ​

合并轨迹为

一种输出是

码长 $(1,2,3,3)$ 的 Kraft 和为 $1$，平均长度为

源熵为 $H(X)\approx 1.8464$ bit，所以冗余约为 $0.0536$ bit，并满足经典界

并列权重可能产生不同码树，但平均长度同样最优。

超出精确范围的失败情形 ​

若源以相等概率产生块 00 或 11，单字母边缘是公平比特，逐符号 Huffman 仍需 $1$ bit/符号；把两个符号作为一块编码只需 0 或 1，即 $1/2$ bit/符号。源的记忆并未让 Huffman 算法出错，而是让“只优化单符号码”成为错误模型。

单符号源、零概率符号、码长上限、不等码字符成本以及 $D$ 元输出都需要额外约定或算法变体。基本 Huffman 定理也不包含码表传输成本、有限精度建模或运行时复杂度保证。

Kraft–McMillan 不等式公理库Kraft–McMillan 不等式Kraft–McMillan inequality刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。提供可行长度约束，Huffman 在其中解决有限分布的整数优化。对长源块再运行 Huffman 可以把每符号开销降到 $1/n$ 以下；无噪声编码定理公理库无噪声编码定理Source coding theorem · Noiseless coding theorem独立同分布信源的无损压缩平均码率可以逼近但不能低于其熵。把这一点概括为熵极限。

实际压缩器常把 Huffman 与上下文模型、游程变换或字典方法组合。此时 Huffman 只负责把模型给出的有限符号概率变成前缀码，整体性能还取决于模型是否捕捉相关性。