哈夫曼编码例题与答案_哈夫曼编码例题与答案

2024年 9月 4日下午12:42 • 激活谷笔记

[0x17-148&149][NOIP2004 提高组&NOI2015] 合并果子&荷马史诗【哈夫曼树】　　最近过完年了，眼瞅着马上就要开学了，再学此寒假最后一个数据结构好了。　　我挑的这个哈夫曼树学其实有点波折，一开始我想着直接接着树状数组下去学线段树，但考虑不能囫囵吞枣，仔细一想真咽不下去。然后想着写树状数组关于逆序对的应用，但又感觉没必要花这时间去精心写一个分支的文章。　　接着我去翻了翻ccf的大纲，发现【4】哈夫曼树的定义、构造及其遍历[1] 还不认识。就有了这篇文章。（废话有点多）　　哈夫曼树　　定义　　我们可以通过一个问题作为引子：　　假设构造一棵有
个叶节点权值和到根节点的距离分别为
w_i 和
l_i 的
叉树。　　我们定义树的所有叶节点的带权路径长度之和为树的带权路径长度（Weighted Path Length of Tree，WPL），假设给定一棵如下的二叉树：

　　则这棵树的带权路径长度为：
$1\times2+2\times3+3\times3+4\times1=21$ . 　　形式化地，即：
$wpl=\sum\limits^n_{i=1}w_i\cdot l_i\\$ 而当经过调换节点后：

　　此时
wpl 值最小时，这棵树被称为 (二叉)哈夫曼树（Huffman Tree，最优树）. 　　构造&遍历　　根据前文我们可以得到哈夫曼树的特性，叶子节点的权值越小，深度越要大。　　则我们容易想到用贪心思想来实现构造哈夫曼树的哈夫曼算法。当
k=2 时　　假设我们有叶子节点集
$T=\{1,2,3,3,4,5\}$ ，显然我们每次要取权值最小的两个节点，把它俩权值相加，作为父节点并加入节点集，不断进行这个过程，直到集合内只有一个节点，即这棵哈夫曼树的根节点。　　内部节点权值之和就是它
wpl 的最小值。

（有些文章中要求左小又大，但我画的时候懒得改了，反正也不是明确要求，并不会改变它的合法性）　　在代码实现上，我们不可能每次对它进行排序。在这里，我们可以用「小根堆」维护，使程序达到一个较优的复杂度
$O(n\log n)$ ，平常的题够用了。当
2″ eeimg=”1″> 时（这里取
k=3 为例）　　可能大家觉得不就是直接在刚刚的思路中改成每次取最小的
个值不就好了。　　但是，如果这样取到最后一层时，集合的大小不足
个，即
$2\thicksim k-1$ 之间，那么根节点就不满
个子树，显然这不是最优解，我随便从下面拿一个叶子节点上来都会比它的
wpl 值小。　　那当集合大小
和叉数
存在什么关系时，不会出现这个情况呢？　　对于每次循环，我们在集合中将
个节点合并成
个，假设会进行
次，易得：
$\begin{aligned} n-m(k-1)&=1\\ (n-1)\%(k-1)&=0 \end{aligned}\\$ 　　∴ 只要不满足这个等式，上述贪心就无法得到最优解，即
$(n-1)\%(k-1)=x(x\in\mathbb{N^*})$ . 　　那么我们可以考虑两个等价的处理方法：1.在最底层添加
个空节点，2.在最底层只取
个节点数量。　　这样就能使不足的情况发生在最底层，此时显然是最优的，而往上就满足等式，用既有贪心即可。

　　应用：哈夫曼编码　　哈夫曼编码就是一种比普通编码效率更高的编码方式，而编码就是给每个字符标记单独的代码来表示一串字符，常用于压缩。　　现在假设给定一个字符串
，要求把它转换成二进制信息并保证解码的唯一性。　　如果用二进制编码，显然要求每个编码是等长的以保证解码的唯一性，则可以有：
　　那么字符串转化为：
，共16位。　　如果用哈夫曼编码，提高空间效率的方法是采用不等长编码，将频率高的字符用尽可能短的编码。而为了保证解码的唯一性，就要保证任一编码都不是其他编码的前缀，即前缀编码。则有：
　　那么字符串转化为：
，共14位，减少了2位。　　哈夫曼树就可以构造最短的前缀编码，也就是哈夫曼编码。字符abcd频率50%25%12.5%12.5%编码0 　　思路就是将每个字符的频率看作权值构造即可。

（大小和深度以及01左右顺序不会改变性质，不过习惯上大小和深度左小右大，左0右1）　　T1-合并果子　　题意　　link（more：LuoguP1090）简化题意：给定
堆数目分别为
a_i 的果子，每次可以合并任意两堆，消耗的体力为两堆果子数目之和，求当全部合并为一堆后，消耗的总体力的最小值。
$(n\leqslant 10^4,a_i\leqslant2\times10^4)$ 　　思路　　易得最终消耗的体力为每堆果子的数目与它参与合并的次数的乘积之和，az…模板到不能再模板的哈夫曼树问题，我们只要维护一棵二叉哈夫曼树即可。　　code 　　T2-荷马史诗　　题意　　link（more：LuoguP2168）简化题意：假设有
种不同的单词，给定每种单词出现的频率
w_i 。现要求用
进制串
s_i 代替第
种单词，使其满足：
$\forall i,j(1\leqslant i,j\leqslant n ~,~i\not= j)$ ，有
s_i 不是
s_j 的前缀。要求使转换后的串总长最小并输出，同时输出最长
s_i 的最短长度。（一个字符串被称为
进制字符串，当且仅当它的每个字符是
[0,k-1] 之间的整数。）
$(n\leqslant10^5$ ，
$2\leqslant k\leqslant9$ ，
$w_i\leqslant 10^{11})$ 　　思路　　显然本题所构造的编码就是哈夫曼编码，利用
叉哈夫曼树实现。　　但需要注意的是，题目要求最长的
s_i 长度要最小，那么在构造哈夫曼树时，当遇到权值相同的节点时，肯定要优先考虑当前深度最小的节点进行合并。　　也就是说，我们还要对每个节点保存深度，这里我用 pair 实现。　　code 　　ps：　　这篇完成度不是很好，贪心也没有给出严谨的证明，大家见谅。ZhangWenjie：目录-数据结构

哈夫曼编码例题与答案_哈夫曼编码例题与答案

相关推荐