POJ1521---Entropy

POJ—Entropy

题目描述 英文

熵编码器是一种数据编码方法，其通过对去除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。
考虑文本“AAAAABCD”。使用ASCII，编码需要64位。由于字形“A”以更高的频率出现，可以通过用更少的位编码来做得更好吗？最佳编码是将“A”编码为“0”，将“B”编码为“10”，将“C”编码为“110”，和“D”与“111”。（这显然不是唯一的最佳编码，因为很明显，对于任何给定的编码，B，C和D的编码可以自由地互换，而不会增加最终编码消息的大小。）使用此编码，消息编码为只有13位到“0000010110111”，压缩比为4.9:1（也就是说，最终编码消息中的每个位表示与原始编码中4.9位一样多的信息）。

输入

输入文件将包含一个文本字符串列表，每行一个。文本字符串将仅包含大写字母数字字符和下划线（用于代替空格）。输入的结尾将由仅包含单词“END”作为文本字符串的行发出信号。

输出

对于输入中的每个文本字符串，输出8位ASCII编码的位长度，最佳无前缀可变长度编码的位长度，以及精确到一个小数点的压缩率。

样例输入

AAAAABCD

THE_CAT_IN_THE_HAT

END

样例输出

64 13 4.9

144 51 2.8

解题思路

本题考察的主要内容为哈夫曼树
案例第一个输出表示字符串用ASCII存储所使用的位数,即 长度 * 8即可.第二个输出为使用二进制编码来存储字符,但要求位数最少,这时我们得使用哈夫曼编码了.我们在处理时只需要统计不同字符出现的个数,然后当做权值,从而根据新生成节点的频率之和便为最佳编码长度求得. 最后一个输出是前两个输出相除得到的.

代码

#include<iostream>
#include<queue>
#include<string>
using namespace std;
int arr[40];
string s;
int main()
{
   
	while (cin >> s && s != "END")
	{
   
		priority_queue<int, vector<int>, greater<int> > Q;
		int len = s.size();
		for (int i = 0; i < len; i++)
		{
   
			arr[s[i] - 'A']++;
		}
		cout << len * 8 << " ";
		for (int i = 0; i < 40; i++)
		{
   
			if (arr[i])
			{
   
				Q.push(arr[i]);
			}
		}
		/* * 方法一 */
		//int total = 0;
		//if (Q.size() == 1) {
   
		// total = len;
		//}
		//while (Q.size() > 1)
		//{
   
		// int sum = 0;
		// sum += Q.top();
		// Q.pop();
		// sum += Q.top();
		// Q.pop();
		// Q.push(sum);
		// //cout << sum << endl;
		// total += sum;
		//}
		//方法二
		int total = len;
		while (Q.size() > 2)
		{
   
			int sum = 0;
			sum += Q.top();
			Q.pop(); 
			sum += Q.top();
			Q.pop();
			Q.push(sum);
			//cout << sum << endl;
			total += sum;
		}
		cout << total << " ";
		printf("%.1lf\n", (double)len * 8 / total);
		memset(arr, 0, sizeof(arr));
	}
	return 0;
}

代码解析

这个题有两种思考方式.其中关键就在于全为一种字符的情况比如AAAAAAAAAAAAA,那么对于方法一,如果没有了对Q.size ==1 的这种判断是不行的,此时total是0明显不符合题意,所以得额外判断处理.如果多个字符组合则按照常规处理即可.
方法二则是直接给total一个初值–即字符串总长度,也就是构建哈夫曼树最后一步的操作. 总权值之和= = 字符个数 = = 哈夫曼树最后一次合并的结果. 这样就不要考虑为当全为一种字符时的情况了.
不过个人还是推荐第一种的,更便于理解,但得细心点.

心得收获

1. 当遇到字符时我们将其映射为数字的处理方式: 如A==> arr[0]=arr[ str[i] – ‘A’ ] (当str[i]
   == A), B==> arr[1]=arr[ str[i] – ‘B’ ] (当str[i] == B).
2. 在竞赛时对于输入输出最好用C语言的,效率更高.
3. 优先队列的使用.
4. 特殊情况的处理,如方法一需要考虑字符种类个数是否大于1,方法二则可不用考虑.