UVA240 可变基数霍夫曼编码
题目描述
哈夫曼编码是一种最优编码方法。根据已知源字母表中字符出现的频率,将源字母表中字符编码为目标字母表中字符,最优的意思是编码信息的平均长度最小。在该问题中,你需要将 N 个大写字母(源字母 S 1 …S N ,频率 f 1 …f N )转换成 R 进制数字(目标字母 T 1 …T R )。
当 R=2 时,编码过程分几个步骤,每个步骤中,有两个最低频率的源字符 S 1 、 S 2 ,合并成一个新的“组合字母”,频率为 S 1 、 S 2 的频率之和。如果最低频率和次低频率相等,则字母表中最早出现的字母被选中。经过一系列的步骤后,最后只剩两个字母合并,每次合并的字母分配一个目标字符,较低频率的分配 0,另一个分配 1。(如果一个合并中,每个字母有相同的频率,最早出现的分配 0,出于比较的目的,组合字母的值为合并中最早出现的字母的值。)源符号的最终编码由每次形成的目标字符组成。
目标字符以相反顺序连接,最终编码序列中第一个字符为分配给组合字母的最后一个目标字符。
下面的两个插图展示了 R = 2 的过程。
当 R>2 时,每一个步骤分配 R 个符号。由于每个步骤将 R 个字母或组合字母合并为一个组合字母,并且最后一次合并必须合并 R 个字母和组合字母,源字母必须包含 k*(R-1)+R个字母, k 为整数。由于 N 可能不是很大,因此必须包括适当数量具有零频率的虚拟字母。
这些虚拟的字母不包含在输出中。在进行比较时,虚拟字母晚于字母表中的任何字母。
霍夫曼编码的基本过程与 R = 2 情况相同。在每次合并中,将具有最低频率的 R 个字母合并,形成新的组合字母,其频率等于组中包括的字母频率的总和。被合并的字母被分配目标字母符号 0 到 R-1。0 被分配给具有最低频率的组合中的字母,1 被分配给下一个最低频率,等等。 如果组中的几个字母具有相同的频率,则字母表中最早的字母被分配较小的目标符号,依此类推。
下图说明了 R = 3 的过程:
输入:
输入将包含一个或多个数据集,每行一个。 每个数据集都包含一个整数值 R(2≤R≤10),整数值 N(2≤R≤26)和整数频率 f 1 …f N ,每个都在 1 到 999 之间。
整个输入的数据结束是 R 为 0; 它不被认为是单独的数据集。
输出:
对于每个数据集,在一行上显示其编号(编号从 1 开始按顺序排列)和平均目标符号长度(四舍五入到小数点后两位)。 然后显示 N 个源字母和相应的霍夫曼代码,每行一个字母和代码。在每个测试用例后打印一个空行。
输入样例
2 5 5 10 20 25 40
2 5 4 2 2 1 1
3 7 20 5 8 5 12 6 9
4 6 10 23 18 25 9 12
0
输出样例
Set 1; average length 2.10
A: 1100
B: 1101
C: 111
D: 10
E: 0
Set 2; average length 2.20
A: 11
B: 00
C: 01
D: 100
E: 101
Set 3; average length 1.69
A: 1
B: 00
C: 20
D: 01
E: 22
F: 02
G: 21
Set 4; average length 1.32
A: 32
B: 1
C: 0
D: 2
E: 31
F: 33
题解:
可变基哈夫曼编码,普通的哈夫曼编码为 R=2。
举例:
3 4 5 7 8 15 // R=3,N=4,A: 5 B: 7 C: 8 D: 15
算法设计:
- 先补充虚拟字符,使 N 满足 k*(R-1)+R,k 为整数,即(N-R)%(R-1)=0;
while((n-R)%(R-1)!=0)//补虚拟结点
n++;- 定义结点结构体,包含 3 个域:int frequency,va,id;//频率,优先值,序号
- 定义优先级:
bool operator <(const node &b) const {
if(frequency==b.frequency)
return va>b.va;
return frequency>b.frequency;
}- 将所有结点入优先队列
for(int i=0;i<n;i++)//所有结点入队
Q.push(node(fre[i],i,i));- 构建哈夫曼树
c=n;//新合成结点编号
int rec=0;//统计所有和值
while(Q.size()!=1)//剩余一个结点停止合并
{
int sum=0,minva=n;
for(int i=0;i<R;i++)
{
sum+=Q.top().frequency;//统计频率和
minva=min(Q.top().va,minva);//求最小优先值
father[Q.top().id]=c;//记录双亲
code[Q.top().id]=i;//记录编码
Q.pop(); //出队
}
Q.push(node(sum,minva,c));//新结点入队
c++;
rec+=sum;
3
}
c–;
printf(“Set %d; average length %0.2f\n”,cas,1.0*rec/total);- 进行哈夫曼编码
for(int i=0;i<N;i++)
{
int cur=i;
string s;
while(cur!=c)
{
s.push_back(code[cur]+‘0’);
cur=father[cur];
}
reverse(s.begin(),s.end());//翻转编码
cout<<" “<<char(‘A’+i)<<”: "<<s<<endl;
}
特别注意:需要补虚拟结点,值和存储序号不同。
参考代码
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 100;
struct node
{
int frequency, va, id;//频率,优先值,序号
node(int x = 0, int y = 0, int z = 0)
{
frequency = x;
va = y;
id = z;
}
bool operator <(const node& b) const {//优先级队列比较时需要用到.
if (frequency == b.frequency)
return va > b.va;//当是 < 时,是从小到大,从队尾取出的将是最大的.>时表示从大到小,取出的将是优先级最小的.
return frequency > b.frequency;
}
};
int R, N;//基数,字母个数
int n, c;//补虚拟字母后的个数,新生成字母的编号
int fre[maxn], father[maxn], code[maxn];//节点数组,父节点数组,编码数组
priority_queue<node> Q;//优先队列,头元素最小.
int main()
{
int cas = 1;//对测试实例进行计数
while (cin >> R && R)
{
cin >> N;
memset(fre, 0, sizeof(fre));//初始化节点数组
int res = 0;//记录所有的节点之和
for (int i = 0; i < N; i++)
{
cin >> fre[i];
res += fre[i];
}
n = N;//新节点索引将从N开始
while ((n - R) % (R - 1) != 0)
{
n++;
}
while (!Q.empty())//清空优先队列
{
Q.pop();
}
for (int i = 0; i < n; i++)
{
Q.push(node(fre[i], i, i));//所有结点入队,优先级为出现的次序.
}
c = n;//新生成节点编号
int total = 0;//统计哈夫曼树长度之和.//构建哈夫曼树
while (Q.size() > 1)
{
int sum = 0, minva = n;//sum:新生成节点频率之和,minva:最小的优先级.
for (int i = 0; i < R; i++)//R基:0-- R-1
{
sum += Q.top().frequency;//统计待合并节点频率之和
minva = min(Q.top().va, minva);//求最小优先级
father[Q.top().id] = c;//记录当前的双亲
code[Q.top().id] = i;//记录当前节点的编码
Q.pop();//出队进行下次循环
}
Q.push(node(sum, minva, c));//新节点入队
c++;
total += sum;
}
c--;//根节点索引
printf("Set %d; average length %0.2f\n", cas, 1.0 * total / res);
for (int i = 0; i < N; i++)//输出哈夫曼编码
{
int cur = i;
string s;//将编码存到s中
while (cur != c)
{
s.push_back(code[cur] + '0');//把编码存到字符串中
cur = father[cur];//进行下一个
}
reverse(s.begin(), s.end());//反转编码
cout << " " << char('A' + i) << ": " << s << endl;
}
cout << endl;//每个样例空一行.
cas++;
}
return 0;
}
这个题目自己花了好几个小时才搞定,虽然比较累,但还是搞懂了.难度确实很大,不过感觉该题思考方式以及解题很妙(我是根据老师讲的写的).从高中开始我渐渐对于难题变的厌烦起来,总把自己脑子太笨为借口,不想去挑战难题,这个题放到前几个星期自己也应该不会去着手,但其实坚持把它搞完也并没有很累.挑战难题对于一些基础知识掌握的的会更深,这个题就用到了<号的重载,还有优先队列等知识点.今后还得多去挑战难题,不断挑战不断进步!