huffmancodec.cpp

这是本人编写的一个Huffman压缩算法,压缩效率最好能达到％20左右,已将所有的编码串转换成为二进制码

#include "HuffmanCodec.h"
#include <malloc.h>
#include <string.h>



CHuffmanCodec::CHuffmanCodec()
{

	pCodecPar = NULL;
	HT        = NULL;
	nNodeNum = 0;
}
CHuffmanCodec::~CHuffmanCodec()
{
	free(HT);
	free(pCodecPar);
}

void CHuffmanCodec::HuffmanEncode(unsigned char    * pData,       //原始数据区 
								  long               nLen,
								  unsigned char    * pCompressData,//压缩数据区
								  long             & nCompressLen, //压缩数据区长度
								  unsigned char    & nBitLen       //压缩数据余位数
								  )

{
	CountDataFrequence(pData,nLen);
	HuffmanCoding();


//	unsigned int	nLastRestCode     = 0x00;	   //表示上次剩余的位编码
	unsigned int    nCurrentCode      = 0x00;      //存储当前的位编码
	unsigned char   nCurrentCodeLen   = 0x00;      //标示当前位编码长度
//	int				nLastRectCodeLen  = 0x00;      //表示上次剩余的位编码的长度
	unsigned int	nLastFillBitPlace = 0x00;      //表示填充位数据的位置	
	unsigned char   clog1			  = 0x80;
	unsigned char   clogPlace	      = clog1;


	nCompressLen	= 0 ;
	for(int i = 0 ; i < nLen ; i ++)
	{
		for(int j = 1 ; j < nCodecParLen ; j++)
		{
			if(pData[i] == HT[j].cNum)
				break;
		}

		nCurrentCode	= HT[j].nCode;
		nCurrentCodeLen = HT[j].nCodeLen;

/*//先压缩原来剩下的码字！没用，错了，当时脑袋大了！
    也他妈不知道怎么想的，不过还好为后来的工作有了
	很多的奠基工作 -------李伟！嗬嗬
		for(int bitCount = 0 ; bitCount < nLastRectCodeLen ; bitCount++)
		
		{
			clogPlace = clog1 >> nLastFillBitPlace;
			if(nLastRestCode & 0x80000000)
				pCompressData[nCompressLen] |= clogPlace;
			else
				pCompressData[nCompressLen] &= ~clogPlace;

			nLastRestCode <<= 1;
			
			if(++nLastFillBitPlace == 8)
			{
				nCompressLen++;
				nLastFillBitPlace = 0;
			}
		}
*/
		for(int bitCount = 0 ; bitCount < nCurrentCodeLen ; bitCount++)
		{
			clogPlace = clog1 >> nLastFillBitPlace;

			if(nCurrentCode & 0x80000000)
				pCompressData[nCompressLen] |= clogPlace;
			else
				pCompressData[nCompressLen] &= ~clogPlace;

			nCurrentCode <<= 1;

			if(++nLastFillBitPlace == 8)
			{
				nCompressLen++;
				nLastFillBitPlace = 0;
			}
		}		
	}
//
//结尾有的时候未编码到整个字节，所以要对结尾处进行处理
//是舍去还是还是精确处理，看需求要求了，
//精确处理可以通过相除取模法进行处理 nCompressLen * 8 + nLastFillBitPlace
//还原时可
	if(nLastFillBitPlace != 0);
	{
		nBitLen = nLastFillBitPlace;
		nCompressLen++;
	}
	pCompressData[nCompressLen] = '\0';
//	nCompressLen++;
//	if(nLastFillBitPlace < 4)
//		nCompressLen--;
//	else
//		nCompressLen++;
	
}


bool CHuffmanCodec::HuffmanDecode(unsigned char     * pCompressData,	//压缩数据区
								  long  			  nCompressLen,     //压缩数据区长度
								  unsigned char       nBitLen,           //压缩数据余位数
								  unsigned char     * pData,           //原始数据区
								  long              & nLen             //原始数据区长度
								  )
{
	if(HT == NULL)
		return false;
	
	unsigned char   clog1			  = 0x80;
	unsigned char   clogPlace	      = clog1;
	unsigned int	nLastFillBitPlace = 0x00;      //表示位数据的位置
	
	unsigned int    nCurrentNodePlace = 0;         //表示当前编码对应的赫夫曼树结点
	unsigned int    nTempNode         = 0;
	bool            bFindLeafFlag     = false;

	if(nBitLen != 0);
	{
		nCompressLen--;
	}

	nLen = 0;

	nCurrentNodePlace	= nNodeNum; //得到根节点位置
	

    int		nDecodeByte = 0 ;	
	while(nDecodeByte <nCompressLen)	
	{
		while(!bFindLeafFlag)
		{
			clogPlace = clog1 >> nLastFillBitPlace;

			if(pCompressData[nDecodeByte] & clogPlace)
			//位为1为右子树
			{
				nTempNode = this->GetRightChild(HT+nCurrentNodePlace);
	
				if(nTempNode == 0)
				{
					bFindLeafFlag = true;
					pData[nLen] = HT[nCurrentNodePlace].cNum;
					nCurrentNodePlace	= nNodeNum; //得到根节点位置
					break;
				}
				else
					nCurrentNodePlace = nTempNode;
			}
			else
			//位为0为左子树
			{
				nTempNode = this->GetLeftChild(HT+nCurrentNodePlace);

				if(nTempNode == 0)
				{
					bFindLeafFlag = true;
					pData[nLen] = HT[nCurrentNodePlace].cNum;
					nCurrentNodePlace	= nNodeNum; //得到根节点位置
					break;
				}
				else
					nCurrentNodePlace = nTempNode;
			}

			if(++nLastFillBitPlace == 8)
			{
				nDecodeByte++;
				nLastFillBitPlace = 0;
			}
		}
		nLen++;
		bFindLeafFlag = false;
	}
	bFindLeafFlag = false;

	while(nLastFillBitPlace < nBitLen)
	{
		while(!bFindLeafFlag)
		{	
			clogPlace = clog1 >> nLastFillBitPlace;

			if(pCompressData[nDecodeByte] & clogPlace)
			//位为1为右子树
			{
				nTempNode = this->GetRightChild(HT+nCurrentNodePlace);
				if(nTempNode == 0)
				{
					bFindLeafFlag = true;
					pData[nLen] = HT[nCurrentNodePlace].cNum;
					nCurrentNodePlace	= nNodeNum; //得到根节点位置
					break;
				}
				else
					nCurrentNodePlace = nTempNode;
			}
			else
			//位为0为左子树
			{
				nTempNode = this->GetLeftChild(HT+nCurrentNodePlace);
				if(nTempNode == 0)
				{
					bFindLeafFlag = true;
					pData[nLen] = HT[nCurrentNodePlace].cNum;
					nCurrentNodePlace	= nNodeNum; //得到根节点位置
					break;
				}
				else
					nCurrentNodePlace = nTempNode;
			}
			if(++nLastFillBitPlace == 8)
			{
				nDecodeByte++;
				nLastFillBitPlace = 0;
			}
		}
		nLen++;
		bFindLeafFlag = false;
	}
	pData[nLen] = '\0';



}


void CHuffmanCodec::SelectTwoMin(unsigned int nNum)
{
	//在HT[1..num]选择parent为0，且weight最小的两个节点
    //从1到num中找出最小的两个数
	unsigned int min1=100000;
	unsigned int min2=100000;
    
 	for(int i = 1 ; i <= nNum ; ++i)
	{
		if(HT[i].parent != NULL)
			continue;
		else
		{
			if(HT[i].weight < min1)
			{	min1 = HT[i].weight;
			    m_nMin1=i;		
			}
		}
	}
	for(i=1 ; i <= nNum ; i++)
	{
		if(HT[i].parent!=NULL)
			continue;
		else 
		{
			if(HT[i].weight < min2 && i != m_nMin1)
			{
				min2 = HT[i].weight;
			    m_nMin2 = i;
			}
		}
	}
}

void CHuffmanCodec::HuffmanCoding()
{
	if(nCodecParLen <= 1) return;
	nNodeNum = 2 * nCodecParLen - 1;

	HT = (PHUFFMANTREE)malloc( ( nNodeNum + 1 ) * sizeof(HTNODE));//0号单元未用
	PHUFFMANTREE   tempHuffmantree;
	memset(HT,0,( nNodeNum + 1 ) * sizeof(HTNODE));

	tempHuffmantree = HT;
	int		i;

	//初始化叶子节点信息
	for(++tempHuffmantree , i = 1 ; i <= nCodecParLen ; ++i , ++tempHuffmantree ) 
	{
	   tempHuffmantree->weight = pCodecPar[i - 1].nWeight;
	   tempHuffmantree->cNum   = pCodecPar[i - 1].cNum;
	   tempHuffmantree->parent =0;
	   tempHuffmantree->lchild =0;
	   tempHuffmantree->rchild =0;
	}

	for( ; i <= nNodeNum ; ++i , ++tempHuffmantree)
	{
		tempHuffmantree->cNum  =0;
		tempHuffmantree->weight=0;
		tempHuffmantree->parent=0;
		tempHuffmantree->lchild=0;
		tempHuffmantree->rchild=0;
	}

	for(i = nCodecParLen + 1 ; i <= nNodeNum ; ++i)
	{
		//建立赫夫曼树
		//在HT[1..i-1]选择parent为0且weight最小的两个节点
		//其序号分别为s1和s2
		SelectTwoMin(i-1);//调用同类里的另一个函数
		HT[m_nMin1].parent = i ; 
		HT[m_nMin2].parent = i;
		HT[i].lchild = m_nMin1;
		HT[i].rchild = m_nMin2;
		HT[i].weight = HT[m_nMin1].weight+HT[m_nMin2].weight;
	}

	//－－－从叶子到根逆向求每个字符的赫夫曼编码

	unsigned char  *cd;
	unsigned int   start,c;
	unsigned int   f;
	//求分配编码的工作空间
	cd = (unsigned char *) malloc(nCodecParLen * sizeof(char));
	//编码结束符
	cd[nCodecParLen - 1] = '\0';

	for( i = 1 ; i <= nCodecParLen ; ++i)
	{
		//逐个字符求编码的工作空间
		start = nCodecParLen - 1;
		for( c = i , f = HT[i].parent ; f != 0 ; c = f , f = HT[f].parent)
		//从叶子到根节点逆向求编码
		{
			if(HT[f].lchild == c) 
				cd[--start] = '0';
			else 
				cd[--start] = '1';
		}
		EncodeHuffmanStr(&cd[start] , HT[i].nCode , HT[i].nCodeLen);
	}
	free(cd);
}

void CHuffmanCodec::EncodeHuffmanStr(unsigned char * str , unsigned int & nCode , unsigned char & nCodeLen )
{
	nCode &= 0x0;
	unsigned int log1 = 0x80000000;
	unsigned int log0 = ~log1;
	for(int i = 0 ; str[i] != '\0' ; i++)
	{
		if(str[i] == '1')
		{
			nCode |= log1;
		}
		else
		{
			nCode &= log0;
		}
		log1 >>= 1;
		log0 = ~log1;
	}
	nCodeLen = i;
}


void CHuffmanCodec::HuffmanDeding()
{

}
void CHuffmanCodec::DecodeHuffmanCode(unsigned char	    * pCompressData,	//压缩数据区
									  long              nCompressLen,        //压缩数据区长度
									  unsigned char     * pData,             //原始数据区
									  long              & nLen			 	//原始数据区长度
									  )
{

}

void CHuffmanCodec::CountDataFrequence(unsigned char     * pData,
									   long              nLen)
{
	HUFFMANCODECPAR huffmanPar[256];
	memset(huffmanPar , 0 , 256 * sizeof(HUFFMANCODECPAR));

	for(int j = 0 ; j < 256 ; j ++)
	{
		huffmanPar[j].cNum = j;
	}

    for(int i = 0 ; i < nLen ; i++)
	{
		huffmanPar[pData[i]].nWeight ++;		
	}

	nCodecParLen = 0 ;
	for(j = 0 ; j < 256 ; j ++)
	{
		if(huffmanPar[j].nWeight != 0 )
		{
			nCodecParLen ++;
		}
	}

	pCodecPar = (PHUFFMANCODECPAR)malloc(nCodecParLen * sizeof(HUFFMANCODECPAR));
	int k = 0; 
	for(j = 0 ; j < 256 ; j ++)
	{
		if(huffmanPar[j].nWeight != 0 )
		{
			pCodecPar[k].cNum		= huffmanPar[j].cNum;
			pCodecPar[k].nWeight	= huffmanPar[j].nWeight;
//			pCodecPar[k].nCode		= huffmanPar[j].nCode;
//			pCodecPar[k].nCodeLen	= huffmanPar[j].nCodeLen;
			k++;
		}
	}	
}



void CHuffmanCodec::GetHuffmanTree(PHUFFMANTREE pTreePtr)
{
	memcpy(pTreePtr , HT + 1 ,nNodeNum * sizeof(HTNODE));
}

void CHuffmanCodec::SetHuffmanTree(PHUFFMANTREE pTreePtr , unsigned int nTreeNodeNum)
{
	this->nNodeNum = nTreeNodeNum;
	HT = (PHUFFMANTREE)malloc(( nNodeNum + 1 ) * sizeof(HTNODE));
	memcpy(HT + 1 , pTreePtr , nNodeNum * sizeof(HTNODE));
}



unsigned int CHuffmanCodec::GetLeftChild(PHUFFMANTREE TreeNode)
{
	return TreeNode->lchild;
}

unsigned int CHuffmanCodec::GetRightChild(PHUFFMANTREE TreeNode)
{
	return TreeNode->rchild;
}

int main()
{
	CHuffmanCodec  * m_tree;
	m_tree = new CHuffmanCodec;
	unsigned char data[5]=

	{
		'a','b','b','a','a'
	};
	unsigned char data2[100];

    unsigned char compressData[25];
	memcpy(compressData,data,100);

	long nLen;
	unsigned char bitLen;
	m_tree->HuffmanEncode(data,5,compressData,nLen,bitLen);
    long nLen1;
	m_tree->HuffmanDecode(compressData,nLen,bitLen,data2,nLen1);

	PHUFFMANTREE pHuffmanTreePtr;
	int nNodeLen; 
	nNodeLen = m_tree->GetHuffmanTreeNodeNum();
	pHuffmanTreePtr = (PHUFFMANTREE)malloc(nNodeLen * sizeof(HTNODE));
	memset(pHuffmanTreePtr,0,nNodeLen * sizeof(HTNODE));


	m_tree->GetHuffmanTree(pHuffmanTreePtr);

	cout<<"赫夫曼树的结构为:"<<endl;
	for(int i = 0 ; i < nNodeLen ;  i++)
	{
		    
			cout<<"节点: "<<i
				<<""
			    <<"源码:"<<pHuffmanTreePtr[i].cNum
			    <<""
			    <<"权值: "<<pHuffmanTreePtr[i].weight
				<<""
				<<"编码:"<<pHuffmanTreePtr[i].nCode
				<<""
				<<"长度:"<<pHuffmanTreePtr[i].nCodeLen
				<<""
				<<"父亲节点: "<<pHuffmanTreePtr[i].parent
				<<""
				<<"左孩子节点: "
				<<pHuffmanTreePtr[i].lchild
				<<""
				<<"右孩子节点 :"
				<<pHuffmanTreePtr[i].rchild
				<<endl;
	}
	cout <<"压缩后的程度为:" <<nLen<<endl;
	for(int l = 0 ; l < nLen1 ; l ++)
	{	
		if(l %10 == 0)
			cout<<endl;
		cout << data2[l];

	}
	cout <<endl;

	delete m_tree;
	return 0;
}