huffcompress.cpp

通过输入文本文件(待压缩文件)的文件名(.txt)向指定目标文件夹输出压缩文件(文本文件)

#include <fstream> 
#include <string>
#include <iostream> 
#include "Huffcompress.h" 
using namespace std; 

//有序表类 
SAList::SAList(int size) {
	maxSize = size; 
	listSize = fence = 0; 
	listArray = new HuffTree*[maxSize]; 
} 

SAList::~SAList(){ 
	delete []listArray; 
}

void SAList::setStart() { 
	fence = 0; 
} 

void SAList::next() { 
	if(fence <= listSize) 
		++fence; 
} 

int SAList::getLength() {
	return listSize; 
} 

bool SAList::insert(HuffTree* item) {
	if (listSize == maxSize) 
		return false; 
	
	HuffTree *current; 
	for (fence=0; fence<listSize; fence++) { 
		current = listArray[fence]; 
		if(!lessThan(current, item)) 
			break; 
	} 
	for (int i=listSize; i>fence; i--) { 
		listArray[i] = listArray[i-1]; 
	} 
	listArray[fence] = item; 
	++listSize; 
	return true; 
} 

HuffTree* SAList::remove() { 
	if(listSize == fence) { 
		return NULL; 
	} 
	HuffTree *temp = listArray[fence]; 
	for(int i=fence; i<listSize-1; ++i) { 
		listArray[i] = listArray[i+1]; 
	} 
	--listSize; 
	return temp; 
} 

bool SAList::lessThan(HuffTree* x, HuffTree* y) { 
	return x->subRoot->weight < y->subRoot->weight; 
} 

//哈夫曼树的实现 
HuffTree::HuffTree() { 
	subRoot = new HuffTreeNode; 
	subRoot->weight = 0; 
} 

HuffTree::HuffTree(unsigned char val, unsigned long int freq) { 
	subRoot = new HuffTreeNode; 
	subRoot->value = val; 
	subRoot->weight = freq; 
	subRoot->isLeaf = true; 
} 

HuffTree::HuffTree(HuffTree* l, HuffTree* r) { 
	subRoot = new HuffTreeNode; 
	subRoot->leftChild = l->subRoot; 
	subRoot->rightChild = r->subRoot; 
	subRoot->leftChild->parent = subRoot->rightChild->parent = subRoot; 
	subRoot->weight = l->subRoot->weight + r->subRoot->weight; 
	subRoot->isLeaf = false; 
} 

HuffTree* HuffTree::buildHuffTree(SAList *sal, SAList *copy) { //创建HuffTree
	HuffTree *temp1, *temp2, *temp3; 
	temp1 = temp2 = temp3 = new HuffTree; 
	for(int i=sal->getLength(); i>1; i--) { 
		sal->setStart(); 
		temp1 = sal->remove(); 
		temp2 = sal->remove(); 
		temp1->subRoot->leftOrRight = 0; //左孩子标记0
		temp2->subRoot->leftOrRight = 1; //右孩子标记1
		temp3 = new HuffTree(temp1, temp2); 
		if(temp1->subRoot->isLeaf) 
			copy->insert(temp1); 
		if(temp2->subRoot->isLeaf) 
			copy->insert(temp2); 
		sal->insert(temp3); 
	} 
	return temp3; 
} 
Link::Link(const unsigned int &elemval, Link *nextval) { 
	element = elemval; 
	next = nextval; 
} 

Link::Link( Link *nextval) { 
	next = nextval; 
} 

void LStack::clear() { 
	while(top != NULL){ 
		Link *temp = top; 
		top = top->next; 
		delete temp; 
	} 
	size = 0; 
} 

bool LStack::push(const unsigned int &item) { 
	top = new Link(item, top); 
	size++; 
	return true; 
} 

bool LStack::pop(unsigned int &it) { 
	if(size == 0) return false; 
	it = top->element; 
	Link *temp = top; 
	top = top->next; 
	size--; 
	delete temp; 
	return true; 
} 

void Buffer::clear() { 
	bits = 0; 
	byte = 0; 
} 

void Huffcompress::compress() { //压缩
	char *sourceFileName = new char[]; //用数组存储源文件文件名
	char *targetFileName = new char[]; //用数组存储压缩文件文件名
	total = 0; 
	numOfLeaf = 0; 
	
	cout << "●请输入源文件文件名或路径："; 
	cin >> sourceFileName; 
	sourceFile = fopen(sourceFileName, "rb"); 
	while (sourceFile == NULL) { 
		cout << "▲您输入的源文件不存在！请重新输入："; 

		cin >> sourceFileName; 
		sourceFile = fopen(sourceFileName, "rb"); 
	} 
	
	fgetc(sourceFile); 
	if (feof(sourceFile)) { 
		cout << "▲文件内容为空！"; 
		system("PAUSE"); 
		exit(-1); 
	} 
	
	//计算源文件大小
	string sourceFileName0;
	sourceFileName0 = sourceFileName;//将源文件名转成string类型
	ifstream fin1(sourceFileName0.c_str());
	fin1.seekg(0,ios::end);
    streampos ps1 = fin1.tellg();//获取源文件大小
	cout<<"源文件大小为 "<<ps1<<" bits"<<endl;
	
	cout << "●请输入压缩文件文件名或路径："; 
	cin >> targetFileName; 
	targetFile = fopen(targetFileName, "wb"); 
	while (targetFile == NULL) { 
		cout << "▲无法创建压缩文件！请重新输入："; 
		cin >> targetFileName; 
		targetFile = fopen(targetFileName, "wb"); 
	} 
	cout << "\n文件压缩中…"; 
	
	buildSAList(); //建立有序表，并保存编码信息 
	tree = tree->buildHuffTree(list, copy); //利用已建立的有序表，建立哈夫曼树 
	cout << "10%…"; 
	//开始编码，并将编码后的内容输出到目标文件 
	rewind(sourceFile); //将文件指针指向文件内容起始处 
	unsigned char tempChar = fgetc(sourceFile); //取文件内容的下一个字符 
	unsigned int tempInt; 
	HuffTreeNode *tempTreeNode; 
	stack = new LStack(); 
	buffer.clear(); //清空缓存区 
	cout << "20%………………"; 
	//当文件内容全部被扫描完，循环结束
	while (!feof(sourceFile)) { 
		//搜索匹配tempChar的叶子的值
		for (int i=0; i< copy->getLength(); i++) { 
			if (tempChar == copy->listArray[i]->subRoot->value) { 
				stack->clear(); 
				tempTreeNode = copy->listArray[i]->subRoot; 
				while (tempTreeNode != tree->subRoot) { 
					stack->push(tempTreeNode->leftOrRight); 
					tempTreeNode = tempTreeNode->parent; 
				}
				while (stack->pop(tempInt)) { 
					write(tempInt); 
				}
				break; 
			}
		}
		tempChar = fgetc(sourceFile); 
	}
	cout << "80%……";
	//如果缓存区还有剩余的位，则添加0到缓存区，直到够满8个位建立个字符，并向目标文件写入该字符 
	if (buffer.bits > 0) { 
		for (unsigned int i=buffer.bits; i<8; i++) 
			write(0); 
	} 
	cout << "100%";
	cout << "文件压缩成功！" << endl; 
	
	//计算压缩文件大小
	string targetFileName0;
	targetFileName0 = targetFileName;//将压缩文件名转成string类型
	ifstream fin2(targetFileName0.c_str());
	fin2.seekg(0,ios::end);//获取压缩文件大小
    streampos ps2 = fin2.tellg();
	
	cout<<"压缩文件大小为 "<<ps2<<" bits"<<endl;
	
	//计算压缩率
	double b = ps2,a = ps1;
	int percent;
	percent = b/a*100;
	cout<<"\n文件压缩率为"<<percent<<"%"<<endl;
		
	delete stack; //清空堆栈
	delete list; //清空有序表
	fclose(sourceFile); //关闭文件流 
	fclose(targetFile); //关闭文件流 
} 

void Huffcompress::decompress() { 
	char *sourceFileName = new char[]; 
	char *targetFileName = new char[]; 
	total = 0; 
	numOfLeaf = 0; 
	
	cout << "\n●请输入压缩文件文件名或路径："; 
	cin >> sourceFileName; 
	sourceFile = fopen(sourceFileName, "rb");  
	while (sourceFile == NULL) { 
		cout << "▲您输入的压缩文件不存在！请重新输入："; 
		cin >> sourceFileName; 
		sourceFile = fopen(sourceFileName, "rb"); 
	} 
	
	fgetc(sourceFile);  
	if (feof(sourceFile)) { 
		cout << "▲文件内容为空！"; 
		system("PAUSE"); 
		exit(-1); 
	} 
	
	cout << "●请输入解压文件文件名或路径："; 
	cin >> targetFileName; 
	targetFile = fopen(targetFileName, "wb"); 
	while (targetFile == NULL) { 
		cout << "▲无法创建解压文件！请重新输入："; 
		cin >> targetFileName; 
		targetFile = fopen(targetFileName, "wb"); 
	} 
	cout << "\n文件解压中…"; 
	
	rewind(sourceFile); //将源文件指针重新指向文件起始处 
	exportSAList(); //导出叶子结点有序表
	cout << "10%…"; 
	tree = tree->buildHuffTree(list, copy); //利用已建立的有序表，建立哈夫曼树 

	//解压
	buffer.clear(); //清空缓存
	unsigned int tempInt; 
	HuffTreeNode *tempTreeNode; 
	//cout << "20%………………";
	while (total > 0) { 
		tempTreeNode = tree->subRoot; 
		while(!tempTreeNode->isLeaf) { 
			tempInt = read(); 
			if(tempInt == 0) { 
				tempTreeNode = tempTreeNode->leftChild; 
			} 
			else { 
				tempTreeNode = tempTreeNode->rightChild; 
			} 
		} 
		fputc(tempTreeNode->value, targetFile); 
		total--; 
	} 
	cout << "80%……";
	
	delete list; 
	fclose(sourceFile); 
	fclose(targetFile); 
	cout << "100%";
	cout << "文件解压完毕！" << endl; 
} 

//按字符扫描源文件，统计源文件出现的字符及其权值 
//利用统计出的字符和和其权值建立叶子结点有序表，并将统计出的信息保存到目标文件 
void Huffcompress::buildSAList() { 
	unsigned char tempChar; 
	HuffTree *temp; 
	//初始化储存字符的数组 
	for (int i=0; i<257; i++) 
		ch[i] = 0; 
	
	rewind(sourceFile); //将文件指针重新指向文件内容起始处 
	tempChar = fgetc(sourceFile); //取文件内容的下一个字符 
	//当文件内容全部被扫描完，循环结束 
	while (!feof(sourceFile)) { 
		++ch[tempChar]; 
		++total; 
		tempChar = fgetc(sourceFile); 
	} 
	//计算应该建立的叶子结点总数 
	for(int j=0; j<257; j++) { 
		if(ch[j] > 0) 
			numOfLeaf++; 
	} 
	//将源文件的字符总数及叶子结点总数保存到目标文件 
	fwrite(&total, sizeof(unsigned long int), 1, targetFile); 
	fwrite(&numOfLeaf, sizeof(unsigned int), 1, targetFile); 
	
	//建立叶子结点有序表 
	list = new SAList(numOfLeaf); 
	copy = new SAList(numOfLeaf); 
	//依次扫描ch，将权值不为0的字符插入到叶子结点有序表中 
	//并将此字符及其权值保存到目标文件 
	for(int k=0; k<257; k++) { 
		if(ch[k] > 0) { 
			temp = new HuffTree(k, ch[k]); 
			list->insert(temp); 
			save.ch = k; 
			save.val = ch[k]; 
			fwrite(&save, sizeof(save), 1, targetFile); 
		} 
	} 
} 

//利用建立的缓存，向目标文件中输出字符 
void Huffcompress::write(unsigned int c) { 
	++buffer.bits; 
	buffer.byte = (buffer.byte << 1) + c; //将byte左移一位，并在末位加上c 
	//如果byte的8个位都被写满，则向目标文件输出byte，并清空缓存区 
	if (buffer.bits == 8) { 
		fputc(buffer.byte, targetFile); 
		buffer.clear(); 
	} 
} 

//从压缩文件中导出叶子结点有序表 
void Huffcompress::exportSAList() { 
	HuffTree *temp; 
	fread(&total, sizeof(unsigned long int), 1, sourceFile); 
	fread(&numOfLeaf, sizeof(unsigned int), 1, sourceFile); 
	list = new SAList(numOfLeaf); 
	for(int i=0; i<numOfLeaf; i++) { 
		fread(&save, sizeof(save), 1, sourceFile); 
		temp = new HuffTree(save.ch, save.val); 
		list->insert(temp); 
	} 
} 

//从压缩文件中读取bit 
unsigned int Huffcompress::read() { 
	if(buffer.bits == 0) { 
		buffer.bits = 8; 
		buffer.byte = fgetc(sourceFile); 
	} 
	if(buffer.byte & (1<<(buffer.bits-1))) { 
		buffer.bits--; 
		return 1; 
	} 
	else { 
		buffer.bits--; 
		return 0; 
	} 
}