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