Huffman 编码

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

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

最优性的证明机制 ​

正概率最优树不需要只含一个孩子的内部节点：收缩该边会缩短其全部后代的码字并严格降低平均长度。因此可取满二叉前缀树，其中最深叶成对出现。把两个最小概率符号与一对最深同胞交换，只会把小权重移到不短的位置，因此平均长度不增；故存在一棵最优树让最小的两个概率 $p_a,p_b$ 成为最深同胞。

归纳从 $m=2$ 开始：两个正码长都至少为一，取 0,1 即得最小平均长度 $1$。仅在 $m\ge 3$ 时，才把上述同胞收缩为权重 $q=p_a+p_b$ 的叶；这时剩下的 $m-1\ge 2$ 个符号仍属于同一合法问题类。任意收缩树的平均长度 $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 算法出错，而是让“只优化单符号码”成为错误模型。

单符号源须先声明消息数：外部已约定一个块时可用空码字；若须从无分隔符码流恢复未知重复次数，最短合法码字仍需一 bit。零概率符号、码长上限、不等码字符成本以及 $D$ 元输出也需要额外约定或算法变体。基本 Huffman 最优性定理本身也不包含码表传输成本或有限精度建模。

若用二叉堆实现最小优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。，每次合并执行两次取最小和一次插入。共有 $m-1$ 次合并，队列大小不超过 $m$；在权重比较、加法和节点操作按单位成本计的模型下，建树总时间为 $O(m\log m)$，存储树和队列需要 $O(m)$ 个记录。若要求把所有码字逐 bit 写出，还须另计 $\mathrm{\Theta }(\sum _i{\ell }_i)$ 的输出时间与空间；极不平衡的合法 Huffman 树可使这个总量达到 $\mathrm{\Theta }(m^2)$。因此“建树近线性”不意味着显式码表的总 bit 长度也近线性。

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

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

长度选好后，规范Huffman码理路规范Huffman码与码长表Canonical Huffman code · 规范赫夫曼码从带符号的码长表唯一重建码字，以整数空槽检查拒绝过订长度，并逐位解出含EOF的短流。用符号顺序和码长表重建唯一的bit映射，并以整数空槽检查拒绝过订长度。这是码表表示与传输的接口，不重新证明或扩大本页的最优性范围。完整压缩流理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。再规定EOF、位序和填充；ABABA的正文7位、含EOF有效码9位与整份文件200位分别属于不同账本。

若每符号码长还必须不超过给定上限，package-merge限长优化理路最大码长约束下的package-mergeLength-limited prefix code · Length-limited Huffman coding · Package-merge · 限长前缀码将最大码长的最优前缀码归约为二进制硬币选择，以配对归并和nodeset闭合证明最优长度并保留符号身份。重新求解带约束的长度选择，而不是截短本算法的输出。权重1、1、2、3、5、8的无上限成本45需最深5层；上限3时最优成本47。原来的无上限交换证明与规范码映射接口继续保留。