test.txt

实现Huffman编码统计压缩算法

#include "En_Decode.h"

void En_Decode::BuildHufTree()
{
	int NodeCounter = 256;
	int i;

	for (i = 0; i < NodeCounter; i++)
	{
		OurTree[i].parent = -1;
		OurTree[i].right = -1;
		OurTree[i].left = -1;
	}

	while (1)
	{
		int MinFreq0 = -1;
		int MinFreq1 = -1;
		
		for (i = 0; i < NodeCounter; i++)
		{
			if (i != MinFreq0)
			{
				if (OurTree[i].freq > 0 && OurTree[i].parent == -1)
				{
					if (MinFreq0 == -1 || OurTree[i].freq < OurTree[MinFreq0].freq)
					{
						if (MinFreq1 == -1 || OurTree[i].freq < OurTree[MinFreq1].freq)
							MinFreq1 = MinFreq0;
						MinFreq0 = i;
					}
					else if (MinFreq1 == -1 || OurTree[i].freq < OurTree[MinFreq1].freq)
						MinFreq1 = i;
				}
			}
		}
		if (MinFreq1 == -1)
		{
			NumOfRootNode = MinFreq0;
			break;
		}

		//Combine two nodes to form a parent node
		OurTree[MinFreq0].parent = NodeCounter;
		OurTree[MinFreq1].parent = NodeCounter;
		OurTree[NodeCounter].freq = OurTree[MinFreq0].freq + OurTree[MinFreq1].freq;
		OurTree[NodeCounter].right = MinFreq0;
		OurTree[NodeCounter].left = MinFreq1;
		OurTree[NodeCounter].parent = -1;
		NodeCounter++;
	}
}

void En_Decode::Output1Bit(int bit)
{
	if (BitCounter == 8 || bit == -1)
	{
		while (BitCounter < 8)
		{
			BitContainer <<= 1;
			BitCounter += 1;
		}
		out_file.put(BitContainer);
		BitCounter = 0;
	}
	BitContainer = (BitContainer << 1) | bit;
	BitCounter++;
}

void En_Decode::Compress1Byte(int node, int child)
{
	if (OurTree[node].parent != -1)
		Compress1Byte(OurTree[node].parent, node);
	if (child != -1)
	{
		if (child == OurTree[node].right)
			Output1Bit(0);
		else if(child == OurTree[node].left)
			Output1Bit(1);
	}
}

void En_Decode::Encode()
{
	char c;
	unsigned char uc;
	int idx;
	FREQCOUNTER OrigBytes = 0;
	int ActiveSymbs = 0;

	while (!in_file.eof())
	{
		in_file.get(c);
		uc = static_cast<unsigned char>(c);
		if (OurTree[uc].freq == 0)
		{
			ActiveSymbs++;
		}
		OurTree[uc].freq++;
		OrigBytes++;
	}

	out_file.write(reinterpret_cast<const char *>(&OrigBytes), sizeof(FREQCOUNTER));
	out_file.write(reinterpret_cast<const char *>(&ActiveSymbs), sizeof(ActiveSymbs));

	for (idx = 0; idx < 256; idx++)
	{
		if (OurTree[idx].freq > 0)
		{
			uc = static_cast<char>(idx);
			out_file.put(uc);
			out_file.write(reinterpret_cast<const char *>(&OurTree[idx].freq), sizeof(FREQCOUNTER));
		}
	}

	BuildHufTree();

	temp_file.seekg(0, std::ios::beg);
	while(1)
	{
		temp_file.get(c);
		if (temp_file.eof())
			break;
		uc = static_cast<unsigned char>(c);
		Compress1Byte(uc, -1);
	}
	Output1Bit(-1);
}

void En_Decode::Decode()
{
	FREQCOUNTER OrigBytes = 0;
	int ActiveSymbs = 0;

	in_file.read(reinterpret_cast<char *>(&OrigBytes), sizeof(FREQCOUNTER));
	in_file.read(reinterpret_cast<char *>(&ActiveSymbs), sizeof(int));

	char c;
	unsigned char uc;
	while (ActiveSymbs--)
	{
		in_file.get(c);
		uc = static_cast<unsigned char>(c);
		in_file.read(reinterpret_cast<char *>(&OurTree[uc].freq), sizeof(FREQCOUNTER));
	}
	BuildHufTree();

	while (OrigBytes--)
	{
		int NumOfTgtSymb;
		NumOfTgtSymb = NumOfRootNode;

		while (OurTree[NumOfTgtSymb].right != -1)
		{
			if (BitCounter == 0)
			{
				in_file.get(c);
				BitContainer = static_cast<unsigned char>(c);
				if (in_file.eof())
					return;
				BitCounter = 8;
			}
			if (BitContainer & 0x80)
				NumOfTgtSymb = OurTree[NumOfTgtSymb].left;
			else
				NumOfTgtSymb = OurTree[NumOfTgtSymb].right;
			BitContainer <<= 1;
			BitCounter--;
		}
		out_file.write(reinterpret_cast<const char *>(&NumOfTgtSymb), sizeof(char));
	}
}