基于C語言利用哈夫曼樹實(shí)現(xiàn)文件壓縮的問題
一、哈夫曼樹
具有n個權(quán)值的n個葉子結(jié)點(diǎn),構(gòu)造出一個二叉樹,使得該樹的帶權(quán)路徑長度(WPL)最小,則稱此二叉樹為最優(yōu)二叉樹,也稱為哈夫曼樹(Huffman Tree)。
注意:哈夫曼樹是帶權(quán)路徑長度最短的樹,且權(quán)值越大的葉子結(jié)點(diǎn)離根結(jié)點(diǎn)越近。
二、哈夫曼編碼
哈夫曼編碼是一種編碼方式,又稱“霍夫曼編碼”,其是可變字長的編碼(VCL)的一種,是由霍夫曼于1952年提出的一種編碼方式,有時被稱為最佳編碼,一般稱為Huffman編碼。
那么我們?yōu)槭裁匆褂霉蚵幋a進(jìn)行壓縮?
首先原因在于,傳統(tǒng)壓縮方式中,字符的編碼是以等字長的方式進(jìn)行壓縮,相比于哈夫曼編碼的可變字長而言壓縮率會降低。其次,傳統(tǒng)方式中可能會出現(xiàn)某些字符的編碼相同,存在二義性,相比于哈夫曼編碼的唯一性。可以大大提高正確性。
2.1 如何得到哈夫曼編碼
通過已經(jīng)構(gòu)造的哈夫曼樹,結(jié)點(diǎn)左分支記為二進(jìn)制數(shù)“0”,結(jié)點(diǎn)右分支記為二進(jìn)制數(shù)“1”。從根結(jié)點(diǎn)向下到該葉子結(jié)點(diǎn)路途經(jīng)過的數(shù)字拼接成為的編碼即為該字符的哈夫曼編碼。現(xiàn)通過以下圖例進(jìn)行演示。
此時各字符對應(yīng)的哈夫曼編碼可表示為:
A:00 B:01 C:1
三、哈夫曼樹實(shí)現(xiàn)文件壓縮基本步驟
3.1 基本實(shí)現(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é)點(diǎn),其出現(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補(bǔ)齊,實(shí)現(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 實(shí)現(xiàn)效果
3.8 計算壓縮率
最后為驗(yàn)證是否實(shí)現(xiàn)壓縮,可通過計算文件壓縮率來驗(yà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語言利用哈夫曼樹實(shí)現(xiàn)文件壓縮的文章就介紹到這了,更多相關(guān)C語言實(shí)現(xiàn)文件壓縮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)inline hook的原理及應(yīng)用實(shí)例
這篇文章主要介紹了C++實(shí)現(xiàn)inline hook的原理及應(yīng)用,需要的朋友可以參考下2014-08-08OpenCV利用高斯模糊實(shí)現(xiàn)簡單的磨皮美顏效果
這篇文章主要介紹了通過OpenCV中的高斯模糊以及雙邊模糊來實(shí)現(xiàn)一個簡單的磨皮美顏效果,文中的講解很詳細(xì),感興趣的同學(xué)可以學(xué)習(xí)一下2021-12-12C++函數(shù)的嵌套調(diào)用和遞歸調(diào)用學(xué)習(xí)教程
這篇文章主要介紹了C++函數(shù)的嵌套調(diào)用和遞歸調(diào)用學(xué)習(xí)教程,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09C++ 將字符串值賦給CHAR數(shù)組的實(shí)現(xiàn)
這篇文章主要介紹了C++ 將字符串值賦給CHAR數(shù)組的實(shí)現(xiàn),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-01-01C++基于easyx圖形庫實(shí)現(xiàn)推箱子游戲
這篇文章主要為大家詳細(xì)介紹了C++基于easyx圖形庫實(shí)現(xiàn)推箱子游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2020-06-06