题目描述
有一篇文章,文章包含$n$ 种单词,单词的编号从$1$至 $n$,第$i$种单词的出现次数为$w_{i}$。
现在,我们要用一个2进制串$s_{i}$来替换第 i 种单词,使其满足如下要求:对于任意的$1≤i,j≤n(i≤j)$,都有$s_{i}$不是$s_{j}$的前缀。
你的任务是对每个单词选择合适的$s_{i}$,使得替换后的文章总长度(定义为所有单词出现次数与替换它的二进制串的长度乘积的总和)最小。
思路
其实也就是一个Huffman树最小带权路径长度(WPL)的问题。
至于什么是Huffman树(编码)可以参考:https://zh.wikipedia.org/zh/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
如图,是一棵已经构造好的Huffman树:
我们注意到每个节点下面都有一个权值,代表的就是词频。词频越高,节点深度越低(必要不充分),也就越能压缩内容。抽象到WPL问题里,就是越能减小WPL长度。
代码实现
先给出一个参考程序:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,ans;
priority_queue<ll,vector<ll>,greater<ll> > q;
int main() {
ios::sync_with_stdio(false);
cin >> n;
ll temp;
for(int i = 1; i <= n; ++i) {
cin >> temp;
q.push(temp);
}
//输入词数及词频
while(q.size() > 1) {
ll sum = 0;
for(int i = 1; i <= 2; ++i) {
sum += q.top();
q.pop();
}
q.push(sum);
ans += sum;
}
cout << ans << endl;
//输出二进制下最小编码长度
return 0;
}
这里我们使用堆(优先队列)来实现我们的算法。每次将堆顶两个元素取出相加再压入堆,重复操作直到堆中只剩下一个元素,这个过程的累加值即WPL的最小长度。
那么问题来了,为什么呢?
这就要回到刚才我们所说的「词频越高,节点深度越低(必要不充分)」上来了。
我们构造一个小根堆,就相当于把这里的部分WPL值计算了出来
此时$ans=5*1+5*1$,再将累加结果压入堆中,我们又可以计算出上一层的部分WPL值。(图中E的编码应为10,小错误)
此时$ans =10+10*1+7*1$,把该节点右子树的部分WPL值累加了进去。
重复以上步骤,由二叉堆的性质,当堆中只剩下一个节点的时候,得到的就是最小WPL了。
(强行解释清楚了)
实在不能理解这个通过堆计算WPL的过程的话,可以尝试构造一组小数据手动模拟。