哈夫曼树

· · 个人记录

来补一下以前漏学的普及组知识点

Part1 引入

以最经典的二叉哈夫曼树为例。

二叉哈夫曼树，是由对最短二进制编码的研究拓展而来的。

所谓最短二进制编码，描述大致如下：

一部资料中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的频率为 w_i。现在要用二进制串 s_i 来替换第 i 种单词，使得其满足如下要求：

对于任意的 1\leq i, j\leq n ，i\ne j ，都有：s_i 不是 s_j 的前缀。

问题即为，如何选择 s_i，才能使压缩以后得到的新的资料长度最小。

改编自P2168 [NOI2015] 荷马史诗

对于这个问题，我们就可以通过构造一棵二叉的 Huffman 树来解决。

part2 构造方法

转化后的问题：对于给定的集合元素个数为 n 的权值集合 \{W\}，找到一个与之对应的（深度）集合 \{L\}，使得 \sum_{i=1}^{n} W_i\times L_i 最小。

Huffman 算法：

把每一个单词看作一个单结点子树放在一个树的集合中，每棵子树的权值等于相应单词的频率。每次取权值最小的两棵子树合并成为一棵新树，并重新放到集合中。新树的权值即等于两棵子树权值之和。

摘编自刘汝佳的入门紫书。

这也就是转化后的问题的求解方案。

part3 求解方法

主要有两种。

一种是用一个优先队列，直接存取，代码容易实现，时间复杂度 O(nlogn)。

例题：P1090 合并果子

另一种方法是用两个普通队列，一个存的是权值有序的子树，另一个存的是合并后的子树。这种方法中，为了保证 O(n) 的时间复杂度，一开始的排序需要用桶排或是基数排序，每次从两个队列分别的前两个元素中，取出较小的两个，合并后插入二号队列，这样同时又可以保证二号队列中的子树权值有序，保证了实现的正确性以及代码效率。

例题：P6033 合并果子加强版

part4 算法正确性证明

这个证明我个人感觉入门紫书的证明不太直观，于是用了另一种更简洁的证明方式。

对于一棵二叉哈夫曼树，初始元素也就是其中的叶子节点，转化后的问题的答案的另一种计算方式，就是该树中非叶子节点的权值之和。

原因的话，因为每一个叶子节点的祖先都是非叶子节点，而每一个非叶子节点的权值就是它的两个子节点的权值之和，于是最底层的答案经过它的所有祖先结点的累加，最终得到的就是其权值乘以深度。

然后，我们根据哈夫曼树的构建过程，可以知道这棵树的总结点个数是 2n-1个，其中叶子结点的个数为 n 个，因此非叶子节点的个数就为 n-1个。这也就是说，最多会有 n-1 次的合并操作，那么每次合并时贪心选择最小的两个结点，这样就可以保证它的最优性了。

part5 扩展

之前讨论的都是二叉哈夫曼树，显然如果用 k 进制编码来压缩单词，就可以得到 k 叉哈夫曼树了。求解思路完全相同，但是要注意，因为每次是合并 k 个子树，也就是集合中少掉 k-1 个子树，就需要满足 (n-1) \mod (k-1)=0，其中 n 是初始子树个数。所以在一开始向集合中加入一些权值为 0 的子树来补以满足其正确性。

例题：P2168 荷马史诗