哈夫曼编码
哈夫曼编码（Huffman coding）是 David A. Huffman 于 1952 年提出的最优前缀码构造算法。给定符号概率分布，Huffman 算法通过自底向上的合并过程生成一棵最优二叉树，使得加权路径长度（即平均码长）最小。
算法的核心步骤如下：将每个符号视为一个叶节点，权值为其概率。重复合并两个概率最小的节点，生成一个父节点（权值为子节点概率之和），直至所有节点合并为一棵树。从根出发到每个叶子节点的路径（左分支为 0，右分支为 1）即为该符号的码字。对于 D 进制编码，每次合并 D 个节点，必要时补充虚拟节点。
Huffman 编码的最优性可以通过交换论证（exchange argument）或贪心选择性质来证明。其核心思想是：在最优编码中，概率最小的两个符号一定具有最长且相等的码长，且它们仅在最后一位不同。Huffman 算法的合并操作恰好保证了这一性质。由于 Huffman 编码能够达到 的最优性能，且构造简单，它被广泛应用于数据压缩领域，是 ZIP、JPEG 等压缩标准的重要组成部分。