compress.cpp

利用Huffman编码法做的一个文本文件压缩程序

#include "stdafx.h"
#include "Compress.h"


/*----------------------------压缩函数--------------------------------*/
/*
参数：存储被压缩文件的地址字符串
作用：根据文件地址遍历文件，获得字符及其权值，排序后根据huffman算法将字符
      编码，并将将编码存入新生成的二进制文件，再次遍历文本文件，同时对获得
	  的字符编码，并存入二进制文件中
*/

int fnCompress(char sAdress[])
{
	HTNODE HufTree[512];									// huffman树
	CODE *arCode;											//编码节点指针，分配内存后存储编码
	CODECELL codecell;										//无符号字符型变量，作为二进制编码的存储单元
	FILE *fpTxt,*fpHuf;										//文件指针，fpTxt为文本文件，fp为二进制文件，
	char ch,sBatAdress[256],archCodeList[32767]={0};		//字符，二进制文件地址，存储二进制编码的数组
	unsigned char nCodenLenth;								//用来记录编码大小，如此定义可最大限度减小压缩文件大小
	int i,j,nTextSize=0,nSize;

	//初始化huffman树
	for(i = 0 ;i < 512 ;i++)
	{
		HufTree[i].weight = 0;
		HufTree[i].lchild = HufTree[i].rchild = HufTree[i].parent = 0;
	}
	//生成压缩文件地址
	strcpy(sBatAdress,sAdress);
	sBatAdress[strlen(sBatAdress)-3] = 0;
	strcat(sBatAdress,"huf");

	//打开被压缩文件
	fpTxt=fopen(sAdress,"rt");
	if(fpTxt == NULL)
	{
		printf("目标文件不存在！！\n");
		return -1;
	}

	printf("正在准备压缩......\n");
	while(1)							//遍历，获得字符权值
	{
		ch=fgetc(fpTxt);
		if(ch==EOF)
			break;
		HufTree[ch+1].ch=ch;
		HufTree[ch+1].weight++;
	}
	fclose(fpTxt);

	nSize = fnSelectsort(HufTree);		//对huftree按权值进行排序，得到字符个数
	arCode = (CODE *)malloc(nSize*sizeof(CODE));//按字符个数分配内存
	if(arCode == NULL)
	{
		printf("内存分配失败!!\n");
		getch();
		return 0;
	}
	fnHufcoding(HufTree,arCode,nSize);	//用haffman算法对字符进行编码
	
	fpHuf=fopen(sBatAdress,"wb");			//以二进制文件形式创建压缩文件
	if(fpHuf == NULL)
		return 0;
	
	//将字符个数存进文件，便于解压缩时给即将读取的节点分配内存，并以此确定编码在文件中的范围
	fwrite(&nSize,sizeof(int),1,fpHuf);

	//将字符代码转变成二进制代码，并以每八位为一个存储单元存入文件
	for(i=0;i<nSize;i++)
	{
		int k=0;
		nCodenLenth =(unsigned char)strlen(arCode[i].code);
		fwrite(&arCode[i].leaf,1,1,fpHuf);				//写入字符
		fwrite(&nCodenLenth,1,1,fpHuf);					//写入编码长度，确定编码结束位置
		while(1)										//将字符串转化，
		{
			codecell = 0;
			for(j=7;arCode[i].code[k]!=0&&j>=0;k++,j--)	//当字符串结束，或满八位后跳出
			{
				if(arCode[i].code[k] == '1')
					codecell += (char)pow(2,j);
			}
			fwrite(&codecell,1,1,fpHuf);
			if(arCode[i].code[k] == 0)					//若字符串结束，跳出，继续下一个字符编码
				break;
		}
	}
	fclose(fpHuf);

	printf("开始压缩文件......\n");
	fpTxt=fopen(sAdress,"rt");
	fpHuf=fopen(sBatAdress,"ab");
	if(fpTxt == NULL||fpHuf == NULL)
		return 0;

	i=0;
	//下面对文件进行译码，并存入文件，读取时，限于存储二进制编码字符串的大小，每128个字符
	//进行一次字符串与二进制的转换并存入文件，
	while(1)
	{
		if(i == 128)
		{
			myBatfWrite(fpHuf,archCodeList);
			archCodeList[0]=0;
			i=0;
		}
		ch=fgetc(fpTxt);
		if(ch==EOF)
			break;
		for(j=0;j<nSize;j++)
			if(ch==arCode[j].leaf)
				strcat(archCodeList,arCode[j].code);
		i++;
	}
	if(i != 0)
		myBatfWrite(fpHuf,archCodeList);
	
	fclose(fpTxt);
	fclose(fpHuf);

	//释放内存
	for(i=0;i<nSize;i++)
	{
		free(arCode[i].code);
	}
	free(arCode);
	return 1;
}



/*------------------选择排序函数--------------------*/
//用选择排序法对haffman树进行排序

int fnSelectsort(HTNODE HufTree[])
{
	HTNODE TempCode;
	int nMark=256,i,j,k;

	for(i=0;i<=nMark;i++)
	{
		k=i;
		for(j=i+1;j<=nMark;j++)
		{
			//如果权值是零，表示此字符在文件中不存在，应放到后面，这里采用和后面字符交换的形式，字道不为零为止
			while(HufTree[j].weight == 0&&nMark>=j)
			{
				TempCode = HufTree[nMark];
				HufTree[nMark] = HufTree[j];
				HufTree[j] = TempCode;
				nMark--;
			}
			if(HufTree[j].weight<HufTree[k].weight)
			{
				k=j;
			}
		}
		if(k!=i)
		{
			TempCode=HufTree[i];
			HufTree[i]=HufTree[k];
			HufTree[k]=TempCode;
		}
	}
	return nMark;
}



/*-----------------------------huffman编码函数----------------------*/
//通过huffman算法对已按升序排好的节点进行编码，及时为编码分配内存来存储编码

void  fnHufcoding(HTNODE  HufTree[], CODE Code[],int nLeavesNum)
{ 
	int i,j,k,s1,s2,s,nCodeNum,f,c,nSum;
	char archTempCode[MAX];

	k=0;
	nCodeNum=2*nLeavesNum-1;
	for(i=nLeavesNum+1;i<=nCodeNum;i++)
	{
		s1=2*k+1;
		s2=s1+1;
		k++;
		
		nSum=HufTree[s1].weight+HufTree[s2].weight;
		j=i-1;
		while(j>=s2+1&&nSum<HufTree[j].weight)
        {
			HufTree[j+1]=HufTree[j];
			j--;
		}
		HufTree[j+1].weight=nSum;
		HufTree[s1].parent=HufTree[s2].parent=j+1;
		HufTree[j+1].lchild=s1;
		HufTree[j+1].rchild=s2;
	}

	s=0;

	for(i=1;i<=nCodeNum;i++)
	{
		c=0;
		if(HufTree[i].lchild==0&&HufTree[i].rchild==0)
		{
			j=i;
			for(k=j,f=HufTree[j].parent;f!=0;k=f,f=HufTree[f].parent)
			{
				if(HufTree[f].lchild==k)
				{
					archTempCode[c]='0';
					c++;
				}
				else
				{
					archTempCode[c]='1';
					c++;
				}
			}
				Code[s].code=(char *)malloc(c+1);
				Code[s].code[c]=0;
				c--;
				k=0;
				while(c>=0)
				{
					Code[s].code[k++]=archTempCode[c--];
				}
				Code[s].leaf=HufTree[j].ch;
				s++;
				if(s==nLeavesNum)
					break;
		}
	}
}



/*--------------------写入函数-----------------------*/
/*
作用：根据字符串生成二进制码，以每字节为存储单元存入文件
*/

void myBatfWrite(FILE *fpHuf,char archCodeList[])
{
	CODECELL codecell;
	int nLenth=strlen(archCodeList);
	unsigned char nCellNum,nBitNum;  //分别记录字节数和最后字节有效数字数，nLenth也可以完成，但这种方式比nLenth少两字节
	int i=0,j;

	nCellNum=(nLenth-1)/8;			//lennt-1是针对nCellNum,防止nLenth为8的倍数时读取编码多出一位
	nBitNum=nLenth%8;
	fwrite(&nCellNum,sizeof(char),1,fpHuf);
	fwrite(&nBitNum,sizeof(char),1,fpHuf);
	while(1)
	{
		codecell = 0;
		for(j=7;archCodeList[i]!=0&&j>=0;i++,j--)
		{
			if(archCodeList[i] == '1')
				codecell += (char)pow(2,j);
		}
		fwrite(&codecell,1,1,fpHuf);
		if(archCodeList[i] == 0)
			break;
	}
}