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 的过程。

当 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

算法设计：

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;
}

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