huf3doc.cpp

Huffman编码1． 给出信源符号的一阶概率分布

// HUF3Doc.cpp : implementation of the CHUF3Doc class
//

#include "stdafx.h"
#include "HUF3.h"

#include "HUF3Doc.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CHUF3Doc

IMPLEMENT_DYNCREATE(CHUF3Doc, CDocument)

BEGIN_MESSAGE_MAP(CHUF3Doc, CDocument)
	//{{AFX_MSG_MAP(CHUF3Doc)
	ON_COMMAND(ID_BUTTON_HUF, OnButtonHuf)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHUF3Doc construction/destruction

CHUF3Doc::CHUF3Doc()
{
	// TODO: add one-time construction code here

}

CHUF3Doc::~CHUF3Doc()
{
}

BOOL CHUF3Doc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CHUF3Doc serialization

void CHUF3Doc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CHUF3Doc diagnostics

#ifdef _DEBUG
void CHUF3Doc::AssertValid() const
{
	CDocument::AssertValid();
}

void CHUF3Doc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CHUF3Doc commands

void CHUF3Doc::OnButtonHuf() 
{/////-----------------------
	double* d_frequency;
	HufNode* d_tree;
	int d_len=91;
	char* d_str="Huffman is probably best known for the developnent of Huffman Coding Proceduce,the result of a term paper he wrote a graduate student at Massachusetts Institute of Technology.Huffman Codes are used in nearly every application that involves the compression and transmission of digital data,such as fax machines, modems,computer networks,and high-definition television.";
////-------------------------///////
	d_frequency=new double[d_len];
	d_tree=new HufNode[2*d_len-1];
	for(int i=0;i<d_len;i++)d_frequency[i]=0;
	for(i=0;i<123;i++)d_tree[i].initnode();///////////123计算得来
////-----------------------------////////
	ofstream outfile("outfile.txt");
	int totle=0;
	char cha=d_str[totle];
	int j;
/////----------------------/////////
	while(cha!='\0')
	{
		j=(int)(cha-' ');
		++totle;
		d_frequency[j]+=1;
		cha=d_str[totle];
	}

	for(i=0;i<d_len;i++)
	{
		d_frequency[i]/=totle;
		d_tree[i].PutName((char)(i+32));
		d_tree[i].PutWeight(d_frequency[i]);
		char tname=d_tree[i].GetName();
		double tweight=d_tree[i].GetWeight();
	}
////-----------------------//////////////
//构造huffman树
	int m=123;       //huffman树中的节点数
	int min1,min2;
	double dmin1,dmin2;
	int k,t;
	for(i=0;i<d_len;i++)
	{
		if(d_tree[i].weight==0)
			d_tree[i].parent=2*d_len;////////////////????????
	}

	for(i=d_len;i<m;++i){
		//先找出最小概率的两个节点
		k=0;
		for(k=0;(d_tree[k].parent)!=0&&k<i;k++);
//		if(k==i)return ERROR;

		min1=k;  //first point p!=0
		for(k=min1+1;k<i&&d_tree[k].parent!=0;k++);
		min2=k;  //second point p!=0
		if(d_tree[min2].weight<d_tree[min1].weight)
		{
			t=min1;
			min1=min2;
			min2=t;
		}
		++k;
		for(;k<i;k++)
		{
			if(d_tree[k].parent==0)
			{
				if(d_tree[k].weight<d_tree[min1].weight)
				{
					min2=min1;
					min1=k;
				}
				else if(d_tree[k].weight<d_tree[min2].weight)
					min2=k;
			}
		}
	///////然后构造节点
		d_tree[min1].parent=i;
		d_tree[min2].parent=i;
		d_tree[i].lchild=min1;
		d_tree[i].rchild=min2;

		dmin1=d_tree[min1].weight;
		dmin2=d_tree[min2].weight;
		d_tree[i].PutWeight(dmin1+dmin2);
	}
////////////////---------------------------//////////////////
//----从叶子到根逆向求每一个字符的编码----
	int c,f;      //huffman树指针可以改成int
	char *cd;     //编码空间
	int start;
	double codelen=0;
	cd=new char[d_len];
	cd[d_len-1]='\0';

	for(i=0;i<d_len;++i)
	{
		if(d_tree[i].weight!=0)
		{
			start=d_len-1;
			for(c=i,f=d_tree[i].parent;f!=0;c=f,f=d_tree[f].parent)
			{
				if(d_tree[f].lchild==c) cd[--start]='0';
				else cd[--start]='1';
			}
			d_tree[i].code=new char[d_len-start+1];////////???
			strcpy(d_tree[i].code,&cd[start]);
			codelen+=(d_len-start-1)*d_tree[i].weight;
		}
	}
	
//////////////////------------------------------////////////
//计算熵
	double entropy=0;
	double temp;
	for(i=0;i<d_len;i++)
	{
		temp=d_frequency[i];
		if(temp!=0)entropy-=d_frequency[i]*log(d_frequency[i])/log(2);
	}
/////////////////--------------------------------///////////
	outfile<<"------------------Huffman Coding----------------\n\n";
	outfile<<"The source code are:"<<'\n';
	outfile<<d_str<<'\n';
	outfile<<"-------------------------------------"<<'\n';
	for(i=0;i<d_len;i++)
	{
		if(d_tree[i].code!=NULL)
		{
		//	outfile<<i<<'\t';
			outfile<<d_tree[i].name<<'\t';
		//	outfile<<d_tree[i].parent<<'\t';
		//	outfile<<d_tree[i].lchild<<'\t';
		//	outfile<<d_tree[i].rchild<<'\t';
		//	outfile<<"..."<<'\t';
			outfile<<d_tree[i].weight<<'\t';
			outfile<<d_tree[i].code<<'\n';
		}
	//	else 
	}
	outfile<<"-------------------------------------"<<'\n';
//压缩以及计算压缩比
	totle=0;
	cha=d_str[totle];
	int code_lenth=0;
	outfile<<"The Huffman Coding is:\n";
	while(cha!='\0')
	{
		j=(int)(cha-' ');
		++totle;
		if(d_tree[j].code!=NULL)
		{
			outfile<<d_tree[j].code;
			code_lenth+=strlen(d_tree[j].code);
		}
		cha=d_str[totle];
	}
	outfile<<"\n------------------------------"<<"End Coding!\n";
	outfile<<"There are "<<totle<<"  alphabets"<<'\n';
	outfile<<"The length of the Huffman Coding is :"<<code_lenth<<" bits\n";
	outfile<<"The entropy is:  "<<entropy<<'\n';
	outfile<<"the average length of coding is:"<<codelen<<'\n';
	outfile<<"The ratio of Huffman Coding compress is:"<<(float)totle*7/code_lenth<<'\n';

/////////////////-------------------------------///////////
	outfile.close();
///////////--------------------------------
}