huffman.cpp

HuffMan编码,用于压缩信源,稍加修改可用于实际应用。

/*===============================
程序名:霍夫曼编码
作者:何震 研通信0704班 07120075
注意:没有考虑汉字宽字符,所以请以全英文文件进行测试
如有问题请联系:[e-mail]
================================*/
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define TABLELENGTH 128
#define MAXSIZE 512
typedef struct tagHTNode
{
	int Parent;//父节点
	int LeftChild;//左子节点
	int RightChild;//右子节点
	int Weight;//权重
}HTNode;//霍夫曼树的节点结构
typedef struct tagCode
{
	char code[MAXSIZE];//Huffman编码的字符形式数组
	int Weight;//Ascii码在文中的权重
}Code;//Huffman码结构
typedef HTNode HuffTree[2*TABLELENGTH];//Huffman树
typedef Code HuffCode[TABLELENGTH];//128个Ascii码的Huffman码结构
int SelectHTNode(HuffTree HT,int n,int *min1,int *min2)
{//选择0~n-1个Code中权重最小的两个
	int cnt=0;//剩余有效Code的个数，有效是指循环中的条件，即权重大于0,且未分配父节点
	for(int i=0;i<n;i++)
	{	
		if(HT[i].Weight>0 && HT[i].Parent==-1)
			cnt++;
	}
	if(cnt<=1)//如果少于两个，就说明树已经构造到树顶了
		return 0;//返回0表示到树顶
	for(i=0;i<n;i++)
	{//找最小权重节点的序号，先初始化min1
		if(HT[i].Parent==-1 && HT[i].Weight>0)
		{
			*min1=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{//找次最小节点的序号，先初始化min2,注意条件i!=*min1,不能使之初始指向同一节点，否则结果有重合错误
		if(HT[i].Parent==-1 && HT[i].Weight>0 && i!=*min1)
		{
			*min2=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{
		if(HT[i].Parent==-1 && HT[i].Weight>0)
		{
			if(HT[*min1].Weight>HT[i].Weight)
			{//如果找到一个有效节点，其权重比上一最小权重节点权重小
				*min2=*min1;//把上一最小权重节点的序号赋予次最小权重节点
				*min1=i;//更新最小权重节点序号
			}
			else if(HT[*min2].Weight>HT[i].Weight && i!=*min1)//如果该节点权重不比最小权重节点小，
				*min2=i;//但比次最小权重节点小，且该节点不是最小权重节点，则更新次最小权重节点序号
		}
	}
	return 1;//返回1说明应该继续构造树
}
void GenerateTree(HuffTree HT,HuffCode hc)
{
	int min1,min2;
	for(int i=0;i<TABLELENGTH;i++)
	{//以下两个循环初始化霍夫曼树的左子，右子和父节点，并为树底的权赋值
		HT[i].Weight=hc[i].Weight;
		HT[i].LeftChild=HT[i].RightChild=HT[i].Parent=-1;
	}
	for(;i<2*TABLELENGTH-1;i++)
	{
		HT[i].LeftChild=HT[i].RightChild=HT[i].Parent=-1;
	}
	for(i=TABLELENGTH;i<2*TABLELENGTH-1;i++)
	{//从第TABLELENGTH个节点开始为上层节点
		int r=SelectHTNode(HT,i,&min1,&min2);
		if(r<1)//从第0到i-1的底层节点中没有赋给父节点的节点中找两个最小权值
			break;//如果没有找到2个最小的说明已经到了树顶
		HT[min1].Parent=i;//为他们赋予父节点指针
		HT[min2].Parent=i;
		HT[i].LeftChild=min1;//设置当前节点左子
		HT[i].RightChild=min2;//设置当前节点右子
		HT[i].Weight=HT[min1].Weight+HT[min2].Weight;//设置当前节点权
	}
}
void GenerateCode(HuffTree HT,HuffCode hc)
{//Huffman编码
	int Stack[MAXSIZE],top=-1,tc;
	char flag[MAXSIZE];
	HTNode th;
	for(int i=0;i<TABLELENGTH /*&& HT[i].Weight>0*/;i++)
	{//从树底开始遍历
		top=-1;//编码路径的跳数，或者说路径的长度
		int j=0;//编码序号
		th=HT[i];//获得树的一个节点
		tc=i;//获得其序号
		while(th.Parent!=-1)
		{//如果其仍有父节点
			Stack[++top]=th.Parent;//将其父节点序号压栈
			if(HT[th.Parent].LeftChild==tc)
			{//如果其父节点的左子为当前节点
				flag[top]='L';//flag存放编码所依据的路径信息
				tc=th.Parent;//向上一层
			}
			else if(HT[th.Parent].RightChild==tc)
			{//如果父节点右子为当前节点
				flag[top]='R';//路径为向右
				tc=th.Parent;//向上一层
			}
			th=HT[Stack[top]];//获得上一层的节点
		}
		while(top!=-1)
		{//如果路径长度不为负数
			if(flag[top]=='L')
				hc[i].code[j++]='0';//根据flag数组进行编码
			else
				hc[i].code[j++]='1';
			top--;
		}
		hc[i].code[j]='\0';
	}
}
int GetProbability(HuffCode hc,char *file)
{//读文件初始化128个ascii码的权重
	FILE *in;
	int c,nTotal=0;
	for(int i=0;i<TABLELENGTH;i++)
	{
		hc[i].Weight=0;//初始为0
	}
	in=fopen(file,"rb");//打开文件
	if(in==NULL)
	{
		printf("No such file!");
		return 0;
	}	
	while((c=fgetc(in))!=EOF)
	{//读字符，根据Ascii码值累加权值
		hc[c].Weight++;
		nTotal++;
		//printf("%c\n",c);
	}
	fclose(in);
	return nTotal;
}
void main()
{
	int nCount;
	char file[128];
	HuffTree HT;//Huffman树结构
	HuffCode hc;//Huffman码表	
	printf("Input file name:");
	gets(file);//获取文件名
	nCount=GetProbability(hc,file);//读文件初始化信源概率数组	
	GenerateTree(HT,hc);//构造霍夫曼树
	GenerateCode(HT,hc);//根据霍夫曼树进行编码
	//测试	
	for(int i=0;i<TABLELENGTH;i++)
	{
		if(hc[i].Weight!=0)
		{
			printf("Ascii Value:%d,Weight:%5.4lf,Encode to:%s\n",i,(double)hc[i].Weight/nCount,hc[i].code);
		}
	}
	getch();
}