L3-图论-第03课哈夫曼树

哈夫曼编码

❝
1951年，哈夫曼在麻省理工学院(MIT)攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺(Robert Fano)出的学期报告题目是：查找最有效的二进制编码。1952年，哈夫曼发表论文《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)中发表了这个编码方法。
❞

在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为 "Farris is not a Ferris wheel" ，这里用到的字符集为“f a r i s n o t e”，各字母出现的次数为{2，2，4，3，3，1, 1, 1, 1}。现要求为这些字母设计编码。要区分这些字母，如何编码才能让编码后长度最短吗?

字符	频率	编码
i	3	00
s	3	01
f	2	110
a	2	111
n	1	1000
o	1	1001
t	1	0110
e	1	1011

让出现频率越高, 编码越短, 就可以得出最短编码.

前缀编码

前缀编码是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，

例如：设有abcd需要编码表示(其中，a=0、b=10、c=110、d=11,则表示110的前缀可以是c或者da，不唯一).

二叉树：约定左分支表示字符‘0’，右分支表示字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。

用构造哈夫曼树的过程生成的二进制前缀编码。哈夫曼树是一类带权路径长度最短的树。

哈夫曼树

Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径. 例如从根结点 14 到字母 f 有条路径 14->8->4->f.

路径长度：在一条路径中，每经过一个结点，路径长度都要加 1. 从根结点到结点 f 长度为 3.

结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。结点 f 的权就是字符 f出现的频率

结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如从根结点 14 到字母 f 的带权路径长度为: 3 * 2 = 6.

树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。上图中的树的带权路径长度为：WPL = 2 * 3 + 2 * 3 + 1 * 4 + 1 * 4 + 1 * 4 + 1 * 4 + 3 * 2 + 3 * 2 = 40

构造

对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：

在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树.

构造示例:

初始状态, 都是单棵树
选权值最小的两个结点, 合并成 1 棵树, 新的结点代替原来的两个结点
继续选权值最小的两个结点, 合并成 1 棵树
继续, 权值相等时, 选高度小的.
...
...
...
终于完成了, 为了美观, 调整下.

K叉哈夫曼树

K叉哈夫曼树的做法与二叉哈夫曼树相类似，只不过每次弹出的数为K个。最关键的问题在于，当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个，可以增加(k - 1) - (n - 1) % (k - 1)个权值为0的叶子节点作虚拟点。

为什么必须要保证最后剩下的元素恰好是k个呢？假如最后的元素少于k个，那么我们完全可以前面已经加入的数随便拉一个过来补上，此时这个点的权值不变但距离变小，自然最后的结果会更小。

P2168 [NOI2015]荷马史诗

题目背景

追逐影子的人，自己就是影子 ——荷马

题目描述 Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 nn 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的总次数为。Allison 想要用 k 进制串来替换第 i 种单词，使得其满足如下要求：

对于任意的，，都有：不是的前缀。

现在 Allison 想要知道，如何选择，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的的最短长度是多少？

一个字符串被称为 k 进制字符串，当且仅当它的每个字符是 0 到 k-1 之间(包括 00 和 k-1 )的整数。

字符串 str1 被称为字符串 str2 的前缀，当且仅当：存在，使得 str1 = str2[1..t]。其中mm 是字符串 str2 的长度，str2[1..t]表示 str2 的前 t 个字符组成的字符串。

输入格式

输入的第 1 行包含 2 个正整数 n, k ，中间用单个空格隔开，表示共有 n 种单词，需要使用 k 进制字符串进行替换。

接下来 n 行，第 i+1 行包含 1 个非负整数，表示第 i 种单词的出现次数。

输出格式

输出包括 2 行。

第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。

第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串的最短长度。

输入输出样例

输入 #1复制

4 21122

输出 #1复制

输入 #2复制

6 3113399

输出 #2复制

分析

其实就是求k叉哈夫曼的带权路径长度.

除叶子节点外, 所结点权值之和就是整棵树的带权路径长度, 也就是文章编码的最短长度.

参考代码

#include using namespace std;const int MAXN = 100005;long long a[MAXN], sum;int n, k;struct Node{    long long w, h;    Node(long long myw, long long myh)    {        w = myw;        h = myh;    }    bool operator    {        if (w == b.w)            return h > b.h;        return w > b.w;    }};priority_queue pq;int main(){    ios::sync_with_stdio(false);    cin >> n >> k;    for (int i = 1; i <= n; i++)    {        cin >> a[i];        pq.push(Node(a[i], 1));    }    long long cnt = 0;    while ((n - 1 + cnt) % (k - 1) != 0)    {        pq.push(Node(0, 1));        cnt++;    }    while (pq.size() > 1)    {        long long tmp = 0, h = 0;        for (int i = 1; i <= k; i++)        {            Node t = pq.top();            tmp += pq.top().w;            h = max(t.h, h);            pq.pop();        }        pq.push(Node(tmp, h + 1));        sum += tmp;    }    cout << sum << endl;    cout << pq.top().h - 1 << endl;    return 0;}

云帆优培订阅号：

云帆优培服务号:

云帆优培老师联系方式：

云帆老师

微信：

云帆优培介绍

原文链接：https://blog.csdn.net/weixin_40002846/article/details/111687471

L3-图论-第03课 哈夫曼树