形式陈述

Huffman 算法对有限符号概率反复选取两个最小权节点合并为权重之和的新节点，最终得到二叉树；左右边标 0、1，叶路径给出前缀码。交换论证说明存在最优树使两个最低概率符号为最深同胞，归纳后得到最小期望码长。标准结论针对逐符号二元前缀码。

直觉

最不常见的符号最适合放在最深位置，并且可以共享最长公共前缀，从而把问题缩成一个较小实例。

例子与边界

权重 $0.4,0.3,0.2,0.1$$0.4,0.3,0.2,0.1$ 先合并 $0.1$$0.1$ 与 $0.2$$0.2$，再继续合并。相同权重可能产生不同但同样最优的树。Huffman 码的期望长度满足 $H(X)\le L<H(X)+1$$H(X)\le L<H(X)+1$，但不必达到熵；对块编码或算术编码可更接近熵率。概率为零的符号和码字长度上限需另行约定。

推论与应用

Huffman 编码用于压缩格式、通信协议和教材级最优贪心证明。

参考资料

• David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE 40(9), 1952，pp. 1098–1101。
• Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006，Chs. 2–8。