UVA240 Variable Radix Huffman Encoding

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 的过程。
UVA240 Variable Radix Huffman Encoding
当 R>2 时,每一个步骤分配 R 个符号。由于每个步骤将 R 个字母或组合字母合并为一个组合字母,并且最后一次合并必须合并 R 个字母和组合字母,源字母必须包含 k*(R-1)+R个字母, k 为整数。由于 N 可能不是很大,因此必须包括适当数量具有零频率的虚拟字母。
这些虚拟的字母不包含在输出中。在进行比较时,虚拟字母晚于字母表中的任何字母。
霍夫曼编码的基本过程与 R = 2 情况相同。在每次合并中,将具有最低频率的 R 个字母合并,形成新的组合字母,其频率等于组中包括的字母频率的总和。被合并的字母被分配目标字母符号 0 到 R-1。0 被分配给具有最低频率的组合中的字母,1 被分配给下一个最低频率,等等。 如果组中的几个字母具有相同的频率,则字母表中最早的字母被分配较小的目标符号,依此类推。
下图说明了 R = 3 的过程:
UVA240 Variable Radix Huffman Encoding

输入:

输入将包含一个或多个数据集,每行一个。 每个数据集都包含一个整数值 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
UVA240 Variable Radix Huffman Encoding
算法设计:

  1. 先补充虚拟字符,使 N 满足 k*(R-1)+R,k 为整数,即(N-R)%(R-1)=0;
    while((n-R)%(R-1)!=0)//补虚拟结点
    n++;
  2. 定义结点结构体,包含 3 个域:int frequency,va,id;//频率,优先值,序号
  3. 定义优先级:
    bool operator <(const node &b) const {
    if(frequency==b.frequency)
    return va>b.va;
    return frequency>b.frequency;
    }
  4. 将所有结点入优先队列
    for(int i=0;i<n;i++)//所有结点入队
    Q.push(node(fre[i],i,i));
  5. 构建哈夫曼树
    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);
  6. 进行哈夫曼编码
    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;
}

这个题目自己花了好几个小时才搞定,虽然比较累,但还是搞懂了.难度确实很大,不过感觉该题思考方式以及解题很妙(我是根据老师讲的写的).从高中开始我渐渐对于难题变的厌烦起来,总把自己脑子太笨为借口,不想去挑战难题,这个题放到前几个星期自己也应该不会去着手,但其实坚持把它搞完也并没有很累.挑战难题对于一些基础知识掌握的的会更深,这个题就用到了<号的重载,还有优先队列等知识点.今后还得多去挑战难题,不断挑战不断进步!

上一篇:TCPDUMP捕获SQL


下一篇:Jmeter系列(31)- 获取并使用 JDBC Request 返回的数据