haffmancode.cpp

哈夫曼编码在文件压缩中有其独特一点

// HaffmanCode.cpp: implementation of the CHaffmanCode class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "haffuman.h"
#include "HaffmanCode.h"

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHaffmanCode::CHaffmanCode()
{
	hArray = new HaffNode[iNumofCode];//一共申请了511个节点，其中256个叶子节点
	codes= new Code[256];//对每个叶子节点相应的编码
	
}

CHaffmanCode::~CHaffmanCode()
{

}
//////////////////////////////////////////////////////////////////////////
float CHaffmanCode::OpenandCloseFile(char *OpenFile,char *CloseFile)
{
	//打开一个待压缩文件，提供压缩后存储的地址
	
	int iPos;
	float fCompre;
	ifstream infile(OpenFile, ios::in | ios::binary);
	do 
	{
		infile.read(Temp,iMax);
		iNumofBits = infile.gcount();//每次实际读入的字节数
		for (iPos = 0; iPos <= iNumofBits; ++iPos)
		{
			++hArray[Temp[iPos] + 128].iWeight;  //统计每个节点在ASCII中的出现频率
		}
		
	} while(iNumofBits == iMax); //每次读入1024个字节
	
	CreateHaffmanTree(hArray); //使用得到的权值构建哈夫曼树，这里用矩阵实现
	EnHaffmanCode(hArray,codes);//对已经构建好的哈夫曼树的每个叶结点进行编码
    fCompre = ChangtoCode(OpenFile,CloseFile);//把所有的内容都按照编码存入一个新文件

	infile.clear();//清理文件读取和写入指针
	infile.close();//关闭文件
	return fCompre;
	
}
//////////////////////////////////////////////////////////////////////////
void CHaffmanCode::CreateHaffmanTree(HaffNode *p)// 压缩函数
{//构建哈夫曼树
	
	int iTemp,iFirstPos,iSecondPos,i;
	unsigned int iFirstValue,iSecondValue;
	
	for (i = 0; i < iBits - 1; ++i)
	{
		iFirstValue = iMaxValue;
		iSecondValue = iMaxValue;
		iFirstPos = 0;
		iSecondPos = 0;
		for (iTemp = 0; iTemp < iBits + i; ++iTemp)
		{
			if(p[iTemp].iWeight < iFirstValue && 0 == p[iTemp].iFlag)
			{
				iSecondValue = iFirstValue;
				iSecondPos = iFirstPos;
				iFirstValue = p[iTemp].iWeight;
				iFirstPos = iTemp;
			}
			else if(p[iTemp].iWeight < iSecondValue && 0 == p[iTemp].iFlag)
			{
				iSecondValue = p[iTemp].iWeight;
				iSecondPos = iTemp;
			}
		}
		
		p[iFirstPos].iParent = iBits + i;
		p[iSecondPos].iParent = iBits + i;
		p[iFirstPos].iFlag = 1;
		p[iSecondPos].iFlag = 1;
		p[iBits + i].iWeight = p[iFirstPos].iWeight + p[iSecondPos].iWeight;
		p[iBits + i].iLeftChild = iFirstPos;
		p[iBits + i].iRightChild = iSecondPos;
	}
}
//////////////////////////////////////////////////////////////////////////
void CHaffmanCode::EnHaffmanCode(HaffNode *p,Code *cd)
{
    //使用已经构建的哈夫曼树对每个叶子节点进行编码
	int child,parent,j;
	for (int i = 0; i < iBits; ++i)
	{
		cd[i].iStart = 23;
		child = i;
		parent = p[child].iParent;
		while (parent != -1)
		{
			j = cd[i].iStart;
			if (p[parent].iLeftChild == child)
			{
				
				cd[i].Bit[j] = 0; //左孩子就编码为0
			}
			else
			{
				cd[i].Bit[j] = 1;//右孩子就编码为1
			}
			cd[i].iStart -= 1;//控制每次的开始端
			
			child = parent;
			parent = p[child].iParent; 
		}
	}

 }
//////////////////////////////////////////////////////////////////////////
float CHaffmanCode::ChangtoCode(char *OpenFile,char *CloseFile)
{
	
	ifstream ifile(OpenFile,ios::in | ios::binary); //再次读入待压缩的文件
	ofstream outfile(CloseFile, ios::out | ios::binary);//保存压缩文件	
	int bit,i = 0,iPos,start,j,h,ArrayCode[1024],flag =1;
	char ArrayChar[128];
	
	for(int iWright = 0; iWright < 256; ++iWright)
	{
		outfile.write((char*)&hArray[iWright].iWeight,4); //在压缩文件中存入每个叶子节点的权值
	}
	char FileName[4] = {'*','*','*','*'}; //构建一个char[4]的数组，用来存入待压缩文件的后缀名
	int NewFilePos = 0;
	int FileNameLength = strlen(OpenFile);
	for (int iFileNamePos = ( FileNameLength - 4); iFileNamePos < FileNameLength; ++iFileNamePos)
	{
		if ('.' == OpenFile[iFileNamePos])
		{
			continue;  //跳过文件后缀名前的点
		}
		else
		{
			FileName[NewFilePos] = OpenFile[iFileNamePos];
			++NewFilePos;
		}
	}
    outfile.write(FileName,4);
	do 
	{
		ifile.read(Temp,iMax);  //每次在待压缩文件中读入1024个字节
		iNumofBits = ifile.gcount();//每次实际的读出字节的数目
		for (iPos = 0; iPos < iNumofBits; ++iPos)
		{
            bit = Temp[iPos]+128;//每个字节的ASCII码都加上128，使其全部在正数中	
			for (start = codes[bit].iStart + 1; start < 24; )
			{
                ArrayCode[i++] = codes[bit].Bit[start++];

				if (i >= 1024)//在数组中存入了1024个后就开始将其转换为char数组，存入压缩文件
				{				
		          	for ( j=0; j < 128; ++j) //每次都操作8个0或者1的数字（将其作为二进制对待）
					{
						h = j*8;
						ArrayChar[j] = 
							char(ArrayCode[h+0]*128 + ArrayCode[h+1]*64 +
							ArrayCode[h+2]*32 + ArrayCode[h+3]*16 + 
							ArrayCode[h+4]*8 +ArrayCode[h+5]*4 + 
							ArrayCode[h+6]*2 + ArrayCode[h+7] - 128);
						
					}//每一位根据其在二进制中的位置对其进行相应的二进制转换
					outfile.write(ArrayChar,128);//存入压缩文件
					i = 0;
				}
			}
			
		}	
	} while(iNumofBits == iMax);//如果读入的数据不足iMax也就是1024位，结束循环
//处理在ArrayCode[1024]中不足1024个数时，对其进行的转换为char的工作
	int Else = i % 8;//得到不足八位的数 
	int ElseTimes = (i - Else) / 8;//得到可以直接转换为char的个数
	int last;
	
	for ( j=0; j < ElseTimes; ++j)
	{
		h = j*8;
		ArrayChar[j] = 
			char(ArrayCode[h+0]*128 + ArrayCode[h+1]*64 +
			ArrayCode[h+2]*32 + ArrayCode[h+3]*16 + 
			ArrayCode[h+4]*8 +ArrayCode[h+5]*4 + 
			ArrayCode[h+6]*2 + ArrayCode[h+7] - 128);
		
	}
	int sum =0, swa = 1,ChangeBits = 0;
    for ( int t=ElseTimes*8; t < i; ++t, swa *= 2)
    {
		sum += ArrayCode[t] * (128 / swa);
    }
	if (swa != 1)
	{
		ArrayChar[j] = char(sum-128);
		ChangeBits = 1;
	}
	outfile.write(ArrayChar,ElseTimes + ChangeBits);

	last = 0;//在不足八位时，对其补充的0的个数
	if (Else != 0)
	{
		last = 8 - Else;
	}
	outfile << last;//将加入的0的个数读入文件
    ifile.clear();
	ifile.seekg(0,ios::end);  
	long double ldOriginSize = ifile.tellg();//计算原文件的长度，保存在ldOriginSize中
	outfile.clear();
	outfile.seekp(0,ios::end);
	long double ldChangedSize = outfile.tellp();//计算压缩文件的长度，保存在ldChangedSize中
	
	return (float)((ldOriginSize - ldChangedSize)/ldOriginSize)*100;//计算文件的压缩率并且返回

	ifile.close();
	outfile.close();//关闭文件

}
//////////////////////////////////////////////////////////////////////////
void CHaffmanCode::TranslateCodes(char* OpenFile,char *CloseFile) //解压函数
{
	ifstream infile(OpenFile,ios::in | ios::binary);
	
	int iRead;
	for (iRead = 0; iRead < 256; ++iRead)
	{
		infile.read((char*)&hArray[iRead].iWeight,4);  //把每个节点的权值读出文件
	}
    CreateHaffmanTree(hArray);  //再次使用这些权值建立一个哈夫曼树
	char FileName[4];
	infile.read(FileName,4); //文件的后缀名一共存了4个字节，是因为当前的文件的后缀名主要是2到4位
	int FileNameLength = strlen(CloseFile);  //得到要保存文件的文件名（该文件名没有包含后缀名）
	CloseFile[FileNameLength] = '.';//给要保存的文件名后面加上点
	int iOriginNamePos = 0;
	for (int FileNamePos = FileNameLength+1; FileNamePos < FileNameLength + 5; )
	{//给要保存的文件后面加上后缀名
		if ('*' == FileName[iOriginNamePos])//跳过*号
		{
			break;
		}
		CloseFile[FileNamePos++] = FileName[iOriginNamePos++];
	}
	CloseFile[FileNamePos] = '\0'; //给要保存的文件名末尾加上结束符号
    ofstream outfile(CloseFile,ios::out | ios::binary);
	int iNumofBits, i, j, num = 0, pos = 510, times, flag;
	char TranTemp[512],Final[1024],t; 
	int  *iTemp = new int[4096];//用来存储TranTemp[512]转换成二进制代码的数组
	int w,TotalTimes,Last;	
	do 
	{
		infile.read(TranTemp,512);  //每次从文件中得到512个字节
		iNumofBits = infile.gcount();//每次从文件中实际得到的字节数
		
		for (i = 0; i < iNumofBits; ++i)
		{
			w = int(TranTemp[i]) + 128; 
			j = i * 8;
			for (int k = j+8-1; k >= j; --k)
			{ 
				iTemp[k] = w%2;  //使用求余数的方法得到每个字节的二进制代码
				w = w / 2;
			}
			
		}
		TotalTimes = iNumofBits*8;
		if (iNumofBits != 512 && iNumofBits != 0) //如果是最后一次读入文件
		{
			infile.clear();
		    infile.seekg(-1,ios_base::end);//最后一次就把读文件的指针前移一位
    		infile>>Last;	//读出最后存在文件最后一位的数值
			TotalTimes -= (Last + 8);//这个数值就是文件压缩时的存入的为补成最后一个字符所补足的0的个数
		}
	       times = 0;
        while (times < TotalTimes)//这里使用的是递推的方法求得其叶子节点
        {
           flag = iTemp[times];
		   if (flag == 0)
		   {
			   pos = hArray[pos].iLeftChild;  //在建立的哈夫曼树种查找被压缩的文件的实际每个字符
		   }
		   else if (flag == 1)
		   {
			
			  pos = hArray[pos].iRightChild;
		   }
		    if (hArray[pos].iLeftChild == -1 || hArray[pos].iRightChild == -1)
		   {
			   t = char(pos + 128);
			   Final[num] = t;//读入Final[1024]数组中
			   pos = 510;
			   ++num;
			   if(num == 1024)//当满足了1024个元素时，一起读到解压后的文件中 
			   {
				   outfile.write(Final,1024);
				   num = 0;
			   }
		   }
		   ++times;
        }
       
		
	} while(iNumofBits == 512);//每次读入的不足512位那就结束循环
	outfile.write(Final,num);
	infile.clear();
	outfile.clear();
	infile.close();
	outfile.close();
}