Huffman 编码

若字符出现频率不同，给高频字符更短编码、低频字符更长编码，可以降低平均码长。Huffman 编码在所有二进制前缀码中达到最小加权路径长度。

1. 为什么需要前缀码

前缀码要求任何字符的编码都不是另一个字符编码的前缀。这样读比特流时，一旦到达叶子就能唯一解码，无需分隔符。

例如 0、10、110、111 是前缀码；0 与 01 不能同时出现，因为读到 0 时无法判断是否应该继续。

2. 编码树与目标函数

每个字符对应二叉树叶子，根到叶子的左右边可记为 0 和 1。字符 $c$ 的码长就是叶子深度 $d(c)$。

若频率为 $f(c)$，总编码长度为

$$B(T)=\sum_c f(c)d(c).$$

目标是让 $B(T)$ 最小。

3. Huffman 算法

每次取频率最小的两个结点 $x,y$，合并为父结点 $z$，令

$$f(z)=f(x)+f(y),$$

再把 $z$ 放回候选集合，直到只剩根。

put all leaves into a min-priority queue
while queue size > 1:
    x = extractMin()
    y = extractMin()
    z = new node(weight = x.weight + y.weight)
    z.left = x; z.right = y
    insert(z)

用最小堆实现，复杂度为 $O(n\log n)$。

4. 为什么合并最小的两个

在某棵最优前缀码树中，频率最小的两个字符可以被安排成最深层的一对兄弟：若深处放着更高频字符，交换位置不会增加、通常会降低总代价。

把这对兄弟合成一个频率为二者之和的伪字符，原问题便缩成更小的同类问题。小问题的最优树展开这个伪字符，就得到原问题的最优树。这同时给出贪心选择性质和最优子结构。

5. 一个例子

频率为

$$a:45,\ b:13,\ c:12,\ d:16,\ e:9,\ f:5.$$

依次合并 $5+9=14$、$12+13=25$、$14+16=30$、$25+30=55$、$45+55=100$。一种编码可能是：

a: 0
c: 100
b: 101
f: 1100
e: 1101
d: 111

左右子树互换会改变具体比特串，但不会改变码长和最优性，因此 Huffman 编码通常不唯一。

6. 解码

从树根开始读比特：0 走左、1 走右；到叶子就输出字符并回到根。前缀性质保证每一步都无歧义。

只有一个字符时要特别处理：不能给它空编码，工程中通常给 0，并额外记录原始字符数量。

7. 真正做压缩还缺什么

算法课常只计算编码树，文件压缩还必须保存：

• 频率表、树结构或规范 Huffman 码，以便解码端重建码表；
• 原始字节数或末字节有效位数，区分末尾补零；
• 明确按字节、Unicode 码点还是其他符号统计；
• 处理空文件、单符号文件和损坏输入。

小文件可能因为码表头部开销反而变大。评价压缩率时，应把头部一起计入，而不能只比较正文比特数。

8. 与定长编码比较

$n$ 种符号的定长编码需要 $\lceil\log_2n\rceil$ 位。Huffman 利用概率不均匀降低平均长度；概率几乎相同时，收益会很小。它保证前缀码中的最优性，并不保证比所有可能的压缩方法都好。