poj1521

在解决这道题之前需要掌握两个知识点。

1.无前缀编码：

就是任何一个数据的编码不能是其他数据编码的前缀。举个例子，将A编码为0，B编为01 这时候可以看出来A只要往后加1就是B，因此A为B的前缀。而无前缀编码就是以上例子的反义，同样举个例子，A编码为1，B编码为01，这里可以看出A是B的无前缀编码。

无前缀编码的作用，它主要作用不等长的编码中，举个例子，我们将AAAABBAA这段数据编码，如果按固定长度编码，每个字母占8位那么总共就要64位，如果我们将其按频率的大小来分配编码长度，例如将出现最多次数的A编码为1，B编码为01这样整段数据只需要占10位，至于为什么要使用无前缀编码，就是为了保证在读码时不会发生读错，举个例子，我们令A为0，B为01,C为001，当AB两个字母放在一起时，我们就不能区分他是AB两个字母还是单个字母C，因此我们在使用不等长的编码时，需要使用无前缀编码来保证我们能正确的读出数据段。

2.哈夫曼树：

前面我们所讲的不等长并且无前缀的编码其实也可以称作为哈夫曼编码，而哈夫曼树就是以字符的频率为权值来构建一个哈夫曼树，这样得到的结果就是每个字符都是无前缀的，从而减少编码的长度，来提高压缩率。

在理解以上两个知识点后，其实就大概理解了题目意思

题目的大概意思我用两个样例来做解释

例子1：对文本AAAAABCD进行编码，如果使用8位的ASCII编码需要64位，用哈夫曼编码的话，我们令A为0、B为10、C为110、D为111，使用此编码只需要13为，将两中编码进行比较为 4.9:1。

例子2：对文本 THE CAT IN THE HAT。进行编码，需要注意的是空格也要算进去。使用8位编码需要144位，而使用哈夫曼编码我们令空格为00、A为100、C为1110、E为1111、H为110、I为1010、N为1011、T为01。这种编码一共只需要51为。二者相比为2.8:1.

题目的要求就是给一个字符串、然后需要我们分别输出8为编码的长度和哈夫曼编码的长度以及二者的比例。

输入

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

输出

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

样例输入

代码如下：

#include 
#include 
#include 
#include 
using namespace std;
int a[30];
int main()
{
	string s;
	while(1)
	{
		cin >> s;
		if(s=="END") break;
		memset(a,0,sizeof(a));//每次输入前需要将数据格式化 
		int n=s.size();
		for(int i=0;i
		{
			if(s[i]=='_') a[26]++;//判断是否为空格 
			else a[s[i]-'A']++;
		}
		priority_queue<int,vector<int>,greater<int> >q;//升序的优先队列，使队首元素保证为最小值 
		for(int i=0;i<=26;i++)
		{
			if(a[i]) q.push(a[i]);//输入数据 
		}
		int ans=n;
		while(q.size()>2)//模拟构建哈夫曼树的操作，具体可以百度 
		{
			int t,t1,t2;
			t1=q.top();q.pop();//其构建方法就是每次选择两个最小的合并
			t2=q.top();q.pop();//直到合并为一颗树 
			t=t1+t2;
			ans+=t;
			q.push(t);
		}
		printf("%d %d %.1lf\n",n*8,ans,(double)n*8/ans);
	}
	return 0;
}

大数据201 ly