poj1521

Before solving this problem, you need to master two knowledge points .

1. No prefix encoding ：

That is, the code of any data cannot be the prefix of other data codes . for instance , take A Encoded as 0,B Make up for 01 It can be seen at this time A Just add it back 1 Namely B, therefore A by B The prefix of . Prefix free coding is the opposite of the above example , Take the same example ,A Encoded as 1,B Encoded as 01, You can see here A yes B No prefix encoding .

The role of prefix free coding , It is mainly used in unequal length coding , for instance , We will AAAABBAA This data is encoded , If you code by a fixed length , Each letter accounts for 8 Seats, then a total of 64 position , If we allocate the coding length according to the size of the frequency , For example, there will be a maximum number of A Encoded as 1,B Encoded as 01 In this way, the whole segment of data only needs to occupy 10 position , As for why to use prefixed encoding , It is to ensure that there is no reading error when reading the code , for instance , We make A by 0,B by 01,C by 001, When AB When two letters are put together , We can't tell if he is AB Two letters or a single letter C, So when we use unequal length coding , We need to use prefix free coding to ensure that we can read the data segment correctly .

2. Huffman tree ：

In fact, the unequal length and prefixed code we mentioned earlier can also be called Huffman code , The Huffman tree is to build a Huffman tree with the frequency of characters as the weight , The result is that every character is prefixed , Thus reducing the length of the code , To improve the compression ratio .

After understanding the above two knowledge points , In fact, I roughly understand the meaning of the topic

I use two examples to explain the general meaning of the topic

Example 1： To text AAAAABCD Encoding , If you use 8 Bit ASCII Coding requires 64 position , In Huffman code , We make A by 0、B by 10、C by 110、D by 111, Using this encoding only requires 13 by , Compare the two codes as 4.9:1.

Example 2： To text THE CAT IN THE HAT. Encoding , It should be noted that spaces should also be included . Use 8 Bit encoding requires 144 position , Using Huffman coding, we make the space as 00、A by 100、C by 1110、E by 1111、H by 110、I by 1010、N by 1011、T by 01. This kind of coding only needs 51 by . The comparison between the two is 2.8:1.

The requirement of the topic is to give a string 、 Then we need to output them separately 8 For the length of the code and the length of the Huffman code and the ratio of the two .

Input

The input file will contain a list of text strings , Each row of a . The text string will contain only uppercase alphanumeric characters and underscores （ Used in place of spaces ）. The end of the input will consist of only words “END” The line as a text string signals . This line should not be handled .

Output

For each text string in the input , Output 8 position ASCII Encoded bit length 、 The bit length of the optimal prefixed variable length coding and the compression rate accurate to the decimal point .

The sample input

AAAAABCD
THE_CAT_IN_THE_HAT
END

Sample output

64 13 4.9
144 51 2.8

The code is as follows ：

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
int a[30];
int main()
{
	string s;
	while(1)
	{
		cin >> s;
		if(s=="END") break;
		memset(a,0,sizeof(a));// You need to format the data before each input  
		int n=s.size();
		for(int i=0;i<n;i++)
		{
			if(s[i]=='_') a[26]++;// Judge whether it is a space  
			else a[s[i]-'A']++;
		}
		priority_queue<int,vector<int>,greater<int> >q;// Ascending priority queue , Ensure that the first element of the team is the minimum  
		for(int i=0;i<=26;i++)
		{
			if(a[i]) q.push(a[i]);// input data  
		}
		int ans=n;
		while(q.size()>2)// Simulate the operation of building Huffman tree , Specific Baidu  
		{
			int t,t1,t2;
			t1=q.top();q.pop();// Its construction method is to select two minimum merges at a time 
			t2=q.top();q.pop();// Until it merges into a tree  
			t=t1+t2;
			ans+=t;
			q.push(t);
		}
		printf("%d %d %.1lf\n",n*8,ans,(double)n*8/ans);
	}
	return 0;
}

big data 201 ly