哈夫曼树

samaofCaCa · 2020-09-08 21:31:29 · 个人记录

Huffman树

构造一棵包含n个叶子节点的k叉树，其中第i棵叶子节点带有权值w_i，要求最小化\sum w_i*l_i。其中l_i表示叶子节点到根的距离。

分析：为了使权值*距离最小，那么权值大的叶子节点应该尽量小。

当k=2时，每次取权值最小的两个点合成一个新的点p，p再树中为这两点的父亲，此次合并答案贡献为两点权值和。合并至只剩下一个点。所构成的树即为哈夫曼树。答案即为\sum w_i*l_i的最小值。

当k>2，猜想每次直接取最小k个权值。但可以发现，如果最后一次合并时，只有不足k个节点，此时显然不是最优解。但我们可以补一些权值为0的使得子节点不足k的情况发生在最底层，而不是在根处。一共需要缩n-1个点，每次缩k-1个点。所以当n \bmod k \not= 0时需要补若干个权值为0的点，使得n \bmod k = 0。此时按照上述贪心即可。

Huffman编码

若一篇文章有n种单词，每个单词有w_i个，如果用k进制数代替这n种单词。且一个数不能是另一个数的前缀。那么怎样编码才能使这篇文章尽可能短。并求文章最短的前提下，使最长的单词最短的编码方法。

假设单词的编码长度为l_i，那么问题要使\sum w_i*l_i最小。即哈夫曼树的问题。将哈夫曼树构造出来后，把这棵哈夫曼树看成字典树。且所有单词编码的末尾都在叶子节点上，而不在内部节点上，此时任何一个编码都不是另一个编码的前缀。按照这种编码方式即满足第一个要求。而满足第二个要求只需要合并时，对于权值相同的点优先合并深度最小的点即可。