encodetree.cpp

使用半适应的huffman算法实现了文件的压缩和解压

#include <math.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include "bitio.h"
#include "encodetree.h"

using namespace std; 

encodetree::encodetree(const char* filepath){
	for(int i = 0;i < 512;i ++){
		tn[i].id = i;
		tn[i].count = 0;
		tn[i].left_child = -1;
		tn[i].right_child = -1;
		tn[i].code_value = 0;
	}
	wordcount = 0;
	strcpy_s(path,filepath);
}

void encodetree::buildTree(void){
	int rt,rt_c;
	int flag = 0;
	unsigned char remain = 0;
	int remain_lenth = 0;
	int count = 0;
	int rootid = -1;
	unsigned char buffer[100];
	unsigned char buffer_c[300];
	bitFile in("in.txt");

	while(1){
		rt = in.getBlock(buffer);
		for(int i = 0;i < rt;i ++)
			tn[buffer[i]].count ++;
		wordcount += rt;
		if(rt != 100)
			break;
	}

	std::sort(tn,tn+256);

	nodecount = 256;

	while(1){	//tree build
		for(int i = 0;i < nodecount;i ++){
			if(tn[i].count == 0)
				continue;
			nodecount ++;
			tn[nodecount - 1].left_child = tn[i].id;
			tn[nodecount - 1].right_child = tn[i + 1].id;
			tn[nodecount - 1].count = tn[i].count + tn[i + 1].count;
			tn[i].count = 0;
			tn[i + 1].count = 0;
			if(i == nodecount - 3)
				flag = 1;
			break;
		}
 
		std::sort(tn, tn+nodecount);
		if(flag)
			break;
	}

	encoding(&tn[nodecount - 1],0,0);
	in.reInstall();

	for(int i = 0;i < 512;i ++){
		if(tn[i].left_child != -1 || tn[i].right_child != -1){
			if(tn[i].count == 0)
				rootid = tn[i].id;
			count ++;
		}
	}

	ofstream outt("out.txt");	//compress the lib into file
	outt << count << " " << rootid << " " << wordcount << " ";
	for(int i = 0;i < 512;i ++){
		if(tn[i].left_child != -1 || tn[i].right_child != -1)
			outt << tn[i].id << " " << tn[i].left_child << " " << tn[i].right_child << " ";
	}
	outt << 'a';
	outt.close();

	bitFile out("out.txt");		//compress the content
	out.toTail();
	count = 0;
	while(1){
		rt = in.getBlock(buffer);
		convetCode(buffer,rt,buffer_c,rt_c,remain,remain_lenth);
		out.putBlock(buffer_c,rt_c);

		count += rt;
		cout << int(count * 100 / wordcount) << "%\r";
		if(rt != 100)
			break;
	}
}

void encodetree::encoding(treeNode* ttn,unsigned int code,int level){
//	cout << ttn->id << endl;
	if(ttn -> left_child != -1)
		encoding(&tn[findNode(ttn -> left_child)],code << 1,level + 1);
	if(ttn -> right_child != -1)
		encoding(&tn[findNode(ttn -> right_child)],(code << 1) + 1,level + 1);
	ttn -> code_value = code;
	ttn -> count = level; //variable count convete to anothor usage for the tree level count from now on 
}

int encodetree::findNode(int nodeid){
	for(int i = 0;i < 512;i ++){
		if(nodeid == tn[i].id)
			return i;
	}
	return -1;
}

void encodetree::nodeInfo(int nodeid,unsigned int& code,unsigned int& digit){
	for(int i = 0;i < 512;i ++){
		if(nodeid == tn[i].id){
			code = tn[i].code_value;
			digit = tn[i].count;
			break;
		}
	}
}

void encodetree::showState(void){
	ofstream out("info.txt");

	for(int i = 0;i < 512;i ++){
		out << tn[i].id << "	";
//		out << (char)tn[i].id << "  ";
		out << tn[i].left_child << "	";
		out << tn[i].right_child << "	";
		out << tn[i].count << "	";
		out << tn[i].code_value << endl;
	}
}

void encodetree::convetCode(unsigned char* src,int count_s,unsigned char* dest,int& count_d,unsigned char& remain,int& lenth){
	unsigned int code;
	unsigned int digit;
	unsigned int tempcode;
	int digitflag;
	int num = 0;	//output count

	for(int i = 0;i < count_s;i ++){
		nodeInfo(src[i],code,digit);
		digitflag = digit + lenth;
		tempcode = (remain << digit) + code;
		while(digitflag >= 8){
			dest[num] = (tempcode >> (digitflag - 8));
			tempcode = tempcode - (dest[num] << (digitflag - 8));
			num ++;
			digitflag -= 8;
		}
		remain = tempcode;
		lenth = digitflag;
	}
	if(count_s != 100){
		dest[num] = (remain << (8 - lenth));
		num ++;
	}
	count_d = num ++;
}