huffydict.cpp

有关huffman的程序对大家学习数据结构有好处但不是所有人都用得上

// HuffyDict.cpp: implementation of the HuffyDict class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "HuffmanTest.h"
#include "HuffyDict.h"

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

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

#pragma warning (disable: 4786)

HuffyDict::HuffyDict()
{
	MyTable=NULL;
	MyListener=NULL;
}

HuffyDict::~HuffyDict()
{
	delete[] MyTable;
}

HuffmanDict::EncEntry * HuffyDict::GetEncodeDict()
{
	return MyTable;
}

void HuffyDict::CreateAdaptedDict(FILE *FreqSource)
{
	unsigned int *FreqA=new unsigned int[256];
	FillFreqA(FreqSource,FreqA);

	HNode *HuffRoot=BuildHuffTree(FreqA);
	delete[] FreqA;

	MyTable=new EncEntry[256];
	BuildHuffTable(HuffRoot,MyTable);

	delete HuffRoot;
}

 //////////////////////////////////////
// Adaptive dictionary helpers

/*As we know the maximum number of symbols, this
dinamic tree method can be optimized to a statically
linked list-like one.
One just needs to calculate the maximum number of nodes
needed to create a huffman tree for N symbols.*/
HuffyDict::HNode *HuffyDict::BuildHuffTree(unsigned int *FreqA)
{
	std::list<HNode *> BaseList;
	
	unsigned int x;
	for (x=0; x<256; x++)
	{
		if (FreqA[x])
			OrderedInsert(BaseList,new HNode(x,FreqA[x]) );
	}

	HNode *CurrNode;
	std::list<HNode *>::iterator CurrLeft,CurrRight;
	while (BaseList.size()>1)
	{
		CurrLeft=CurrRight=BaseList.begin();
		++CurrRight;

		CurrNode=new HNode;
		CurrNode->Left=*(CurrLeft.operator->());
		CurrNode->Right=*(CurrRight.operator->());

		CurrNode->Left->Parent=CurrNode->Right->Parent=CurrNode;
		CurrNode->Weight=CurrNode->Left->Weight + CurrNode->Right->Weight;

		BaseList.erase(CurrLeft);
		BaseList.erase(CurrRight);

		OrderedInsert(BaseList,CurrNode);
	}

	//The only one remaining node must be the root.
	return *(BaseList.begin().operator->());
}

void HuffyDict::BuildHuffTable(HNode *HTreeRoot, EncEntry *OutTable)
{
	if (HTreeRoot->Left)
	{
		BuildTableInternal(HTreeRoot->Left,0,1,OutTable);
		BuildTableInternal(HTreeRoot->Right,(unsigned int)1 << 31,1,OutTable);
	}
	else
	{
		OutTable[HTreeRoot->Symbol].Code=0;
		OutTable[HTreeRoot->Symbol].CodeLen=1;
	}
}

/*The codes are built to be aligned with the  _left_
side of the integer. For example, a huffman code 'b1'
is represented by "b1000...00".*/
void HuffyDict::BuildTableInternal(HNode *HTreeRoot, unsigned int CurrCode, unsigned char CurrCodeLen, EncEntry *OutTable)
{
	if (HTreeRoot->Left)
	{
		CurrCodeLen++;
		BuildTableInternal(HTreeRoot->Left,CurrCode,CurrCodeLen,OutTable);
		//Append bit "1" after the current code
		BuildTableInternal(HTreeRoot->Right,CurrCode | (1 << (32-CurrCodeLen)),CurrCodeLen,OutTable);
	}
	else
	{
		OutTable[HTreeRoot->Symbol].Code=CurrCode;
		OutTable[HTreeRoot->Symbol].CodeLen=CurrCodeLen;
	}
}

//Assumes a buffered file!! (Means it's slow as hell.)
void HuffyDict::FillFreqA(FILE *InFile, unsigned int *OutA)
{
	unsigned int x;
	for (x=0; x<256; x++)
		OutA[x]=0;

	x=0;
	unsigned char InChar;
	while(!feof(InFile))
	{
		fread(&InChar,1,1,InFile);
		OutA[InChar]++;
		
		x++;
		if ((x & 0xFFF)==0x800)
			MyListener->Update(x);
	}
}

/*This should be fast enough for building
the huffman tree for now. However, it
definitely needs improvement.*/
void HuffyDict::OrderedInsert(std::list<HNode *> &TargetList, HNode *NewNode)
{
	std::list<HNode *>::iterator NowI=TargetList.begin(),EndI=TargetList.end();
	unsigned int NewNodeWeight=NewNode->Weight;
	while ((NowI!=EndI) && ( (*( NowI.operator->()) )->Weight<=NewNodeWeight))
		++NowI;

	TargetList.insert(NowI,NewNode);
}

 //////////////////////////////////////
// Serialize / Deserialize helpers

bool HuffyDict::Deserialize(FILE *TableSource)
{
	delete[] MyTable;
	MyTable=new EncEntry[256];

	unsigned int x;
	//Init the table, as if a complete table was present.
	for (x=0; x<256; x++)
		MyTable[x].CodeLen=0;

	unsigned char CodeMax;
	fread(&CodeMax,1,1,TableSource);
	if (!CodeMax)
		return false;

	unsigned short CodeCount=CodeMax+1;

	unsigned int CurrCode;
	unsigned char CurrSymbol;
	for (x=0; x<CodeCount; x++)
	{
		fread(&CurrSymbol,1,1,TableSource);
		fread(&(MyTable[CurrSymbol].CodeLen),1,1,TableSource);
		//Debug: reads 4-byte codes only.
		//fread(&(MyTable[CurrSymbol].Code),4,1,TableSource);
		if (MyTable[CurrSymbol].CodeLen>24)
			fread(&(MyTable[CurrSymbol].Code),4,1,TableSource);
		else if ((MyTable[CurrSymbol].CodeLen<25) && (MyTable[CurrSymbol].CodeLen>16))
		{
			fread(&CurrCode,3,1,TableSource);
			MyTable[CurrSymbol].Code=CurrCode << 8;
		}
		else if ((MyTable[CurrSymbol].CodeLen<17) && (MyTable[CurrSymbol].CodeLen>8))
		{
			fread(&CurrCode,2,1,TableSource);
			MyTable[CurrSymbol].Code=CurrCode << 16;
		}
		else //if (MyTable[CurrSymbol].CodeLen<9)
		{
			fread(&CurrCode,1,1,TableSource);
			MyTable[CurrSymbol].Code=CurrCode << 24;
		}
	}

	return true;
}

bool HuffyDict::Serialize(FILE *TableTarget)
{
	if (!MyTable)
		return false;

	unsigned int x;
	unsigned short CodeCount=0;
	for (x=0; x<256; x++)
	{
		if (MyTable[x].CodeLen)
			CodeCount++;
	}

	unsigned char CodeMax=CodeCount-1;
	fwrite(&CodeMax,1,1,TableTarget);

	unsigned int CurrCode;
	for (x=0; x<256; x++)
	{
		if (MyTable[x].CodeLen)
		{
			fwrite(&x,1,1,TableTarget);
			fwrite(&(MyTable[x].CodeLen),1,1,TableTarget);
			//Debug: outputs 4-byte codes only.
			//fwrite(&(MyTable[x].Code),4,1,TableTarget);
			if (MyTable[x].CodeLen>24)
				fwrite(&(MyTable[x].Code),4,1,TableTarget);
			else if ((MyTable[x].CodeLen<25) && (MyTable[x].CodeLen>16))
			{
				CurrCode=MyTable[x].Code >> 8;
				fwrite(&CurrCode,3,1,TableTarget);
			}
			else if ((MyTable[x].CodeLen<17) && (MyTable[x].CodeLen>8))
			{
				CurrCode=MyTable[x].Code >> 16;
				fwrite(&CurrCode,2,1,TableTarget);
			}
			else //if (MyTable[x].CodeLen<9)
			{
				CurrCode=MyTable[x].Code >> 24;
				fwrite(&CurrCode,1,1,TableTarget);
			}
		}
	}

	return true;
}