题目描述

有一篇文章,文章包含$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树:

huffman-tree-1.jpg

我们注意到每个节点下面都有一个权值,代表的就是词频。词频越高,节点深度越低(必要不充分),也就越能压缩内容。抽象到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值计算了出来

huffman-tree-2.jpg

此时$ans=5*1+5*1$,再将累加结果压入堆中,我们又可以计算出上一层的部分WPL值。(图中E的编码应为10,小错误)

huffman-tree-3.jpg

此时$ans =10+10*1+7*1$,把该节点右子树的部分WPL值累加了进去。

重复以上步骤,由二叉堆的性质,当堆中只剩下一个节点的时候,得到的就是最小WPL了。

(强行解释清楚了)

实在不能理解这个通过堆计算WPL的过程的话,可以尝试构造一组小数据手动模拟。

Last modification:July 25, 2021
博客维护不易,如果你觉得我的文章有用,请随意赞赏