一、哈夫曼樹

        具有n個權(quán)值的n個葉子結(jié)點，構(gòu)造出一個二叉樹，使得該樹的帶權(quán)路徑長度（WPL）最小，則稱此二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹（Huffman Tree）。

注意：哈夫曼樹是帶權(quán)路徑長度最短的樹，且權(quán)值越大的葉子結(jié)點離根結(jié)點越近。

二、哈夫曼編碼

        哈夫曼編碼是一種編碼方式，又稱“霍夫曼編碼”，其是可變字長的編碼（VCL）的一種，是由霍夫曼于1952年提出的一種編碼方式，有時被稱為最佳編碼，一般稱為Huffman編碼。

那么我們?yōu)槭裁匆褂霉蚵幋a進(jìn)行壓縮？

首先原因在于，傳統(tǒng)壓縮方式中，字符的編碼是以等字長的方式進(jìn)行壓縮，相比于哈夫曼編碼的可變字長而言壓縮率會降低。其次，傳統(tǒng)方式中可能會出現(xiàn)某些字符的編碼相同，存在二義性，相比于哈夫曼編碼的唯一性。可以大大提高正確性。

2.1 如何得到哈夫曼編碼

        通過已經(jīng)構(gòu)造的哈夫曼樹，結(jié)點左分支記為二進(jìn)制數(shù)“0”，結(jié)點右分支記為二進(jìn)制數(shù)“1”。從根結(jié)點向下到該葉子結(jié)點路途經(jīng)過的數(shù)字拼接成為的編碼即為該字符的哈夫曼編碼?，F(xiàn)通過以下圖例進(jìn)行演示。

此時各字符對應(yīng)的哈夫曼編碼可表示為：

A：00        B：01        C：1

三、哈夫曼樹實現(xiàn)文件壓縮基本步驟

3.1 基本實現(xiàn)流程

3.2 使用文件輸入流讀取需壓縮的文件，并判斷該文件是否存在

存在后執(zhí)行接下來的步驟，不存在提示用戶，效果圖如下

3.3 讀取，統(tǒng)計字符

        用戶輸入正確文件路徑且存在時使用文件輸入流讀取文件，將文件放于一個字符數(shù)組中（注意字符數(shù)組開辟空間應(yīng)足夠大）。統(tǒng)計出現(xiàn)的字符及其出現(xiàn)的次數(shù)。

char ch;
		while(feof(fp) == 0){
			fscanf(fp,"%c",&ch);
			str[ch]++;
		}
		printf("\n");
		for(i = 0; i < 1024; i++){
			if(str[i] != 0){
				count[n++] = i; 
			}
		}

3.4 構(gòu)造哈夫曼樹

注：由于后續(xù)會使用此哈夫曼編碼，為了方便獲取，這里將求出的哈夫曼編碼放置于一個二維數(shù)組中。

 CreateHT(ht,node);
		char strarr[256][256];
		int aa,bb;
		for(aa=0; aa<256;aa++)
			for(bb=0;bb<256;bb++)
				strarr[aa][bb]=-1; 
		
		for(k = 0;k < node;k++){
			huffmanCode(ht,k,strarr[k]);
		}

void CreateHT(HTNode *ht, int n){
	int i, j, lnode, rnode n1, n2;
	for(i = n; i < 2*n-1; i++){
		lnode = 65432; rnode = lnode;
		n1 = 0; n2 = 0;
		for(j = 0; j < i; j++){
			if(ht[j].parent == -1){
				if(ht[j].weight <lnode){
					rnode = lnode;
					n2 =n1;
					lnode = ht[j].weight;
					n1 = j; 
				} else if(ht[j].weight < rnode){
					rnode = ht[j].weight;
					n2 = j; 
				}
			} 
		}
		ht[n1].parent = i;
		ht[n2].parent = i;
		
		ht[i].weight = lnode+rnode;
		ht[i].parent = -1;
		ht[i].lchild = n1;
		ht[i].rchild = n2;
	}
}

3.5 根據(jù)構(gòu)造哈夫曼樹得到哈夫曼編碼

        此時我們使用3.3中統(tǒng)計的字符作為葉子結(jié)點，其出現(xiàn)次數(shù)作為權(quán)值，構(gòu)造哈夫曼樹求出哈夫曼編碼。下面以此段英文為例，得到每個字符對應(yīng)哈夫曼編碼。

You can take away our money,house,car,or even our clothes and we can surive.But if our health was taken away,we would surely die.That is why we always try to eat in a healthy way and excise regularly..

3.6 替換字符為其哈夫曼編碼

        用戶輸入壓縮至的文件路徑，將替換好的0 1數(shù)字字符數(shù)組寫入該文件。由于C語言沒有基于字符串的操做，所以我們替換時只能通過對字符數(shù)組進(jìn)行操作，涉及到了被替換字符串長度與替換字符串長度的問題，以及字符數(shù)組的長度是否充足。由于此次替換被替換字符串只是一個字符，且字符數(shù)組開辟空間足夠大。所以只考慮替換字符串長度，即字符對應(yīng)哈夫曼編碼的長度，在這里使用一個方法來進(jìn)行替換。

void replace(char oldstr[], char key[], char rep[]){
	int oldstrLen, lengthOfKey, lengthOfRep, i, j , flag;
	char tmp[1000]; 
	oldstrLen = strlen(oldstr);
	lengthOfKey = strlen(key);
	lengthOfRep = strlen(rep);
 
	for( i = 0; i <= oldstrLen - lengthOfKey; i++){
		flag = 1;
		for(j = 0; j < lengthOfKey; j++){
			if(oldstr[i + j] != key[j]){
				flag = 0; 
				break;
			}
		}
		if(flag){
			strcpy(tmp, oldstr);
			strcpy(&tmp[i], rep);
			strcpy(&tmp[i + lengthOfRep], &oldstr[i + lengthOfKey]);
			strcpy(oldstr, tmp);
			i += lengthOfRep - 1;
			oldstrLen = strlen(oldstr);
		}
	}
}

替換完成后的字符數(shù)組使用輸出流寫入用戶輸入文件路徑。

3.7 進(jìn)制轉(zhuǎn)換

        將文件中每八位二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)，再轉(zhuǎn)換為其對應(yīng)的ASCII碼值，最后不足八位的二進(jìn)制數(shù)以0補齊，實現(xiàn)文件壓縮。

3.7.1 進(jìn)制轉(zhuǎn)換方法

int retTen(char str[]){
	int ten = 0;
	int t = 0;
	for(t = 0;t < strlen(str);t++){
		ten += (str[t]-'0') * pow(2,strlen(str) - t - 1); 
	} 
	return ten;
}

3.7.2 實現(xiàn)效果

3.8 計算壓縮率

        最后為驗證是否實現(xiàn)壓縮，可通過計算文件壓縮率來驗證。其中，壓縮率=原文件字節(jié)大小/壓縮后文件大小。

int oldFileSize=getFileSize(path);
int newFileSize=getFileSize(Gopath);
		
printf("\n");
printf("壓縮成功!,文件已壓縮至%s\n",Gopath); 
printf("該文件壓縮率為：%.2lf\n",(double)newFileSize/(double)oldFileSize);

注：注意計算壓縮率時的類型轉(zhuǎn)換

到此這篇關(guān)于基于C語言利用哈夫曼樹實現(xiàn)文件壓縮的文章就介紹到這了,更多相關(guān)C語言實現(xiàn)文件壓縮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論