test.cpp

这是一个基于huffman编码的简单数据流压缩算法

// test.cpp : Defines the entry point for the console application.
//
//
#include "stdafx.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define NUM	27
#define MAX 4294967295//权值不超过最大值

//haffman树的数据结构
typedef struct {
	unsigned long weight;//权值
	unsigned int parent,lchild,rchild;//父亲接点，左右孩子接点
}HTNode,*HuffmanTree;
//huffman编码的数据结构，用二维数组表示，一号不用，没一维的数据第一元素表示编码的个数
typedef char ** HuffmanCode;
//统计字符的个数数组
unsigned long lettercount[NUM];
//======================================================================
void Statistics(char *fname,unsigned long lc[NUM]);//统计字符的个数
void Select(HuffmanTree HT,int i,int &s1,int &s2);//选择两个节点的权值最小的节点
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned long *w,int n);//进行haffman编码
void print(HuffmanCode HC,int n);//输出haffman的编码
int	 gettype(char ch);//得到haffman编码的类型，其编码是按顺序排列a--z
void creatbin(char *fsou,char *fdes,HuffmanCode HC,int num);//生成二进制代码，并存贮在文件1.B中
void decoding(char *fsou,char *fdes,HuffmanCode HC);//对二进制代码进行解码，使还原成字符串
int  equtype(HuffmanCode HC,char *str);//对编码进行查找，看是否存在与str字符串相同的编码，存在，返回类型
char gchar(int flag);//根据类型得到字符

//=======================统计字符的个数====================
void Statistics(char *fname,unsigned long lc[NUM])
{
	FILE *fp;
	char ch;
	fp=fopen(fname,"r");
	if(fp==NULL)//打开文件，以只读的方式
	{
		printf("Can't open the file\n");
		exit(1);
	}
	;
	while((ch=fgetc(fp))!=EOF)//逐个读文件的字符，分别统计字符的个数
	{
		switch(ch)
		{
			case 'a':lc[0]++;
			case 'A':lc[0]++;break;
			case 'b':lc[1]++;
			case 'B':lc[1]++;break;
			case 'c':lc[2]++;
			case 'C':lc[2]++;break;
			case 'd':lc[3]++;
			case 'D':lc[3]++;break;
			case 'e':lc[4]++;
			case 'E':lc[4]++;break;
			case 'f':lc[5]++;
			case 'F':lc[5]++;break;
			case 'g':lc[6]++;
			case 'G':lc[6]++;break;
			case 'h':lc[7]++;
			case 'H':lc[7]++;break;
			case 'i':lc[8]++;
			case 'I':lc[8]++;break;
			case 'j':lc[9]++;
			case 'J':lc[9]++;break;
			case 'k':lc[10]++;
			case 'K':lc[10]++;break;
			case 'l':lc[11]++;
			case 'L':lc[11]++;break;
			case 'm':lc[12]++;
			case 'M':lc[12]++;break;
			case 'n':lc[13]++;
			case 'N':lc[13]++;break;
			case 'o':lc[14]++;
			case 'O':lc[14]++;break;
			case 'p':lc[15]++;
			case 'P':lc[15]++;break;
			case 'q':lc[16]++;
			case 'Q':lc[16]++;break;
			case 'r':lc[17]++;
			case 'R':lc[17]++;break;
			case 's':lc[18]++;
			case 'S':lc[18]++;break;
			case 't':lc[19]++;
			case 'T':lc[19]++;break;
			case 'u':lc[20]++;
			case 'U':lc[20]++;break;
			case 'v':lc[21]++;
			case 'V':lc[21]++;break;
			case 'w':lc[22]++;
			case 'W':lc[22]++;break;
			case 'x':lc[23]++;
			case 'X':lc[23]++;break;
			case 'y':lc[24]++;
			case 'Y':lc[24]++;break;
			case 'z':lc[25]++;
			case 'Z':lc[25]++;break;
			default:lc[26]++;break;
		}
	}
	fclose(fp);//关闭文件
}

//=============================================
//选择两个权值最小的节点
//==============================================================
void Select (HuffmanTree HT,int i,int &s1,int &s2)
{//s1,s2为HT[i..i-1]中parent==0且weight最小的两个结点
	int count;
	unsigned long min1=MAX;
	for(count=1;count<=i;count++)
	{
		if(HT[count].weight<min1&&HT[count].parent==0)
		{
			min1=HT[count].weight;
		    s1=count;
		}
	}
	min1=MAX;
	for(count=1;count<=i;count++)
	{
		if(HT[count].weight<min1&&HT[count].parent==0&&count!=s1)
		{
			min1=HT[count].weight;
			s2=count;
		}
	}

}
//=====================================================================
//编码
//=======================================================================
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned long *w,int n)
{
	if(n<=1)    return;
	int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元不用
	int i;
    for(i=1;i<=n;++i)
	{
		HT[i].weight=w[i-1];
		HT[i].lchild=0;
		HT[i].parent=0;
	    HT[i].rchild=0;                       //初始化 
	}
	for(;i<=m;++i)
	{
	    HT[i].lchild=0;
		HT[i].parent=0;
		HT[i].rchild=0;
		HT[i].weight=0;
	}
	//=============建huffmantree===========================

    int s1=1,s2=2;
    for(i=n+1;i<=m;++i)
	{
		Select(HT,i-1,s1,s2);
	   
		HT[s1].parent=i;HT[s2].parent=i;
		HT[i].lchild=s1;HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	//===================求huffmancode从叶子到根==================
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	int fag=0;
    int start=1;
	for(i=1;i<=n;++i)
	{
		fag=0;
		start=1;
		unsigned int c;
		int f;
			HC[i]=(char *)malloc((n+1)*sizeof(char));
		for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		{
			if(HT[f].lchild==c)
			   HC[i][start++]='0';
			else
				HC[i][start++]='1';
			fag++;
		}
		HC[i][start]='\0';//字符串结束符
		HC[i][0]=fag;
	}
}

//==============================================================
//显示haffman编码
//===============================================================
void print(HuffmanCode HC,int n)
{
	int i;
	for(i=1;i<=n;i++)//一号不用
	{
		printf("%c的编码是：%s",('a'+i-1),&HC[i][1]);
		printf("\n");
	}printf("\n");
}

//=============================================================
//生成二进制代码
//==============================================================
void creatbin(char *fsou,char *fdes,HuffmanCode HC,int num)
{
	int count;//进行左移时需要移动的位数
	int index;//调用gettype函数时，需要保存的类型
	int flag;//存放对应字符的haffman编码，此编码的1和0的个数
	FILE *fpsou,*fpdes;
	char ch;//存放读文件时需要存放的8位二进制码
	unsigned char temp;
	unsigned char result;//进行左移8位存放的结果，再把二进制结果存进文件
	fpsou=fopen(fsou,"rt");//打开原文件，只读，文本文件方式

	if(fpsou==NULL)
	{
		printf("Can't open the file\n");
		exit(1);
	}
	fpdes=fopen(fdes,"wb");//打开目标文件，只写，二进制方式

	if(fpdes==NULL)
	{
		printf("Can't open the file\n");
		exit(1);
	}
	count=7;//初始化
	result=0;
	while((ch=fgetc(fpsou))!=EOF)
	{
		index=gettype(ch);//类型
		flag=HC[index][0];//0号为haffman编码的个数
		while(flag>0)
		{
			temp=0x01&(HC[index][flag]-48);//把ascii编码变成二进制编码，存进temp中
			result=result|(temp<<count);//左移count位
			count--;//
			if(count==-1)//已经左了8位
			{
				fputc(result,fpdes);//写进文件
				result=0;//初始化
				count=7;
			}
			flag--;
		}
	}
	fputc(result,fpdes);
	fputc(0,fpdes);//0表示文件读结束
	fputc(0,fpdes);
	fputc(0,fpdes);
	fclose(fpdes);//关文件
	fclose(fpsou);
}
//==========================================================================
//字符类型判断
//==========================================================================
int gettype(char ch)
{
	if(ch>='a'&&ch<='z')
		return (ch-'a'+1);
	else if(ch>='A'&&ch<='Z')
		return (ch-'A'+1);
	else 
		return 27;
}
//=========================================================================
//解码
//==========================================================================
void decoding(char *fsou,char *fdes,HuffmanCode HC)
{
	unsigned char ch,chtemp;//ch存放读文件的二进制代码，chtemp是根据flag的类型得到相应的字符
	unsigned char temp;//temp是临时存放ch的二进制代码
	char str[NUM+1];//每读一个二进制码，把他转换成ascii码，
					//并添加到str的尾部，最后进行比较，存在就把str清空
	int count;//右移的位数
	int end;
	int j,i;
	int flag;//类型
	FILE *fpsou,*fpdes;
	HuffmanCode HCTemp;//反转后要存放的haffman编码
	fpsou=fopen(fsou,"rb");//文件只读，二进制

	if(fpsou==NULL)
	{
		printf("Can't open the file\n");
		exit(1);
	}
	fpdes=fopen(fdes,"wt");//文件只写，文本文件

	if(fpdes==NULL)
	{
		printf("Can't open the file\n");
		exit(1);
	}
	//反转haffman的编码
	HCTemp=(HuffmanCode)malloc((NUM+1)*sizeof(char *));
	for(i=1;i<=NUM;i++)
	{
		HCTemp[i]=(char *)malloc((NUM+1)*sizeof(char));
		flag=HC[i][0];
		HCTemp[i][flag]='\0';
		for(j=flag-1;j>=0;j--)
			HCTemp[i][j]=HC[i][flag-j];
	}/*//反转后的编码
	for(i=1;i<=NUM;i++)
		printf("%s\n",HCTemp[i]);*/
	count=7;//初始化
	j=0;
	end=0;
	while((ch=fgetc(fpsou))!=-1)
	{//逐个取出二进制的代码，进行assci码的转换，并跟haffman编码前缀比较，看是否存在。
		//存在输出对应的字符，并存放进文件，否则继续读文件
		count=7;
		if(ch==0)
		{
			end++;
			if(end==3)break;
		}
		else
			end=0;
		while(count>=0)
		{
			
			temp=ch;
			temp=temp>>count;//右移count位
			temp=temp&0x01;
			str[j]=(temp+0x30);
			str[j+1]='\0';
			flag=equtype(HCTemp,str);//是否有haffman编码
			if(flag!=0)
			{
				j=-1;
				chtemp=gchar(flag);
				fputc(chtemp,fpdes);//printf("%c",chtemp);
			}
			j++;
			count--;
		}
		
	}
	fclose(fpdes);//关文件
	fclose(fpsou);
}
//===============================================================
//haffman前缀的判断，返回相应的类型
//===============================================================
int equtype(HuffmanCode HC,char *str)
{
	int index=0;
	int i;
	for(i=1;i<=NUM;i++)
	{
		if(strcmp(&HC[i][0],str)==0)
		{
			index=i;
			break;
		}
	}
	if(i==NUM+1)index=0;
	return index;

}
//===============================================================
//根据类型得到字符，只有小写的字符
//===============================================================
char gchar(int flag)
{
	if(flag!=27)
		return ('a'+flag-1);
	else
		return ' ';
}


//=============================================================
int main(int argc, char* argv[])
{
	
	int i;
	for(i=0;i<NUM;i++)
		lettercount[i]=0;
	printf("================统计字符的个数=============\n");
	Statistics("test.txt",lettercount);//统计字符
	for(i=0;i<NUM;i++)
		printf("'%c'=%d ",gchar(i+1),lettercount[i]);
	printf("\n");
	HuffmanTree HT;
	HuffmanCode HC;
	printf("================encoding====================\n");
	HuffmanCoding(HT,HC,lettercount,NUM);//编码
	printf("Huffman编码是反向读如：1100是表示编码0011\n");
	print(HC,NUM);//输出编码
	printf("================create binary================\n");
	creatbin("test.txt","1.B",HC,NUM);//根据haffman编码生成二进制代码
	printf("================decoding=====================\n");
	decoding("1.B","yyz.txt",HC);//解码
	printf("\n");
	return 0;
}