huffmanコード---zoj_1117

huffman符号化は最適化された符号化方法であり,ASCIIなどの固定長の符号化方法と比較して符号化の長さを短縮することができる.その主な考え方は,出現頻度の高い文字に短い符号化を持たせ,出現頻度の低い文字に長い符号化を持たせることである.しかしながら、このような符号化方式では、任意の文字の符号化が他の文字符号化のプレフィックスではないことが要求され、通常、このような符号化方式をプレフィックス符号化と呼ぶ.huffman符号化はhuffmanTreeを構築することによって実現され,貪欲な思想である.重み値(周波数)が最も低い2つのノードは,新しいノードの左右のサブノードであり,新しいノードの重み値はサブノードの重み値の和である.処理後、サブノードは処理済みとマークされ、新しいノードは未処理とマークされます.プロセスをループ処理します.huffmanTreeにm個のリーフノードがある場合、huffmanTreeにはn=2*m−1個のノードがあるに違いない.したがって,huffmanTreeに2*m−1個のノードがある場合,huffmanTree構造は終了する.

//zoj1117.cpp  
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
class huffmanNode
{
public:
	int value,parent,left,right,pos;
	bool isset;
	int  dir;
	huffmanNode()
	{
		this->isset=false;
		this->left=-1;
		this->right=-1;	
		this->parent=-1;
		this->pos=-1;
		this->dir=1;
	}
	huffmanNode(int value,int pos):value(value),pos(pos)
	{
		this->isset=false;
		this->left=-1;
		this->right=-1;
		this->parent=-1;
		this->dir=-1;	
	}
};
class huffmanTree
{
public:
	huffmanNode hflist[20000];
	int n,count,flag;
	huffmanTree(int count,int n)
	{
		this->count=count;
		this->n=n;
		this->flag=count;
	}
	void createTree()
	{
		while(flag<n)
		{
			int a=0;
			int b=0;
			int va=99999998;
			int vb=99999999;
			for(int i=0;i<flag;i++)
			{
				if(hflist[i].isset)
				continue;
				if(hflist[i].value<vb)
				{	
					b=i;
					vb=hflist[i].value;
				}
				if(vb<va)
				{
					int temp=vb;
					vb=va;
					va=temp;
					temp=b;
					b=a;
					a=temp;
				}
			}
			huffmanNode node(hflist[a].value+hflist[b].value,flag);
			node.left=a;
			node.right=b;
			hflist[flag]=node;
			hflist[a].parent=flag;
			hflist[a].dir=0;
			hflist[b].dir=1;
			hflist[b].parent=flag;
			hflist[a].isset=true;
			hflist[b].isset=true;
			++flag;
		}	
	}
	int  getEncoding(int n)
	{
		if(n>=count)
			return 0;
		int flag=n;
		int result=0;
		while(hflist[flag].parent!=-1)
		{
			//cout<<hflist[flag].dir<<" ";
			flag=hflist[flag].parent;
			++result;
		}
		return result;
	}

};
int num[27];
int flag,m,n;
int main()
{
	char ch[20000];
	memset(ch,0,sizeof(ch));
	while(scanf("%s",ch)!=EOF)
	{
		//cout<<ch<<endl;
		if(ch[0]=='E'&&ch[1]=='N'&&ch[2]=='D'&&ch[3]=='\0')
		break;
		memset(num,0,sizeof(num));
		flag=0;
		m=0;
		while(ch[flag]!=0)
		{
			if(ch[flag]=='_')
			{
				if(num[26]==0)
				++m;
				++num[26];
			}
			else
			{
				if(num[ch[flag]-65]==0)
				++m;
				++num[ch[flag]-65];
			}
			++flag;
		}
		n=m*2-1;
		int j=0;
		huffmanTree tree(m,n);
		for(int i=0;i<27;i++)
		{
			if(i!=26&&num[i]>0)
			{
				huffmanNode node(num[i],j);
				tree.hflist[j]=node;
				j++;
			}
			if(i==26)
			{
				huffmanNode node(num[26],j);
				tree.hflist[j]=node;
				j++;	
			}
			
		}
		/*for(int i=0;i<m;i++)
		{
			cout<<tree.hflist[i].value<<endl;
		}*/
		cout<<flag*8<<" ";
		tree.createTree();
		int result=0;
		if(m<=1)
		result=tree.hflist[0].value;
		else
		{
			for(int i=0;i<m;i++)
			{
			result+=tree.getEncoding(i)*tree.hflist[i].value;
			//cout<<endl;		
			}
		}
		cout<<result<<" ";
		printf("%.1f
",(float)8*flag/result);
		memset(ch,0,sizeof(ch));
	}

	
}