欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基于C語言利用哈夫曼樹實(shí)現(xiàn)文件壓縮的問題

 更新時間:2021年08月04日 10:05:37   作者:Small Program  
哈夫曼編碼是一種編碼方式,又稱“霍夫曼編碼”,其是可變字長的編碼(VCL)的一種,這篇文章主要介紹了基于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)用實(shí)例

    這篇文章主要介紹了C++實(shí)現(xiàn)inline hook的原理及應(yīng)用,需要的朋友可以參考下
    2014-08-08
  • OpenCV利用高斯模糊實(shí)現(xiàn)簡單的磨皮美顏效果

    OpenCV利用高斯模糊實(shí)現(xiàn)簡單的磨皮美顏效果

    這篇文章主要介紹了通過OpenCV中的高斯模糊以及雙邊模糊來實(shí)現(xiàn)一個簡單的磨皮美顏效果,文中的講解很詳細(xì),感興趣的同學(xué)可以學(xué)習(xí)一下
    2021-12-12
  • c語言:金幣陣列的問題

    c語言:金幣陣列的問題

    本文介紹了關(guān)于c語言:金幣陣列的問題,需要的朋友可以參考一下
    2013-03-03
  • C++函數(shù)的嵌套調(diào)用和遞歸調(diào)用學(xué)習(xí)教程

    C++函數(shù)的嵌套調(diào)用和遞歸調(diào)用學(xué)習(xí)教程

    這篇文章主要介紹了C++函數(shù)的嵌套調(diào)用和遞歸調(diào)用學(xué)習(xí)教程,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下
    2015-09-09
  • C++實(shí)用庫之字節(jié)流合成器

    C++實(shí)用庫之字節(jié)流合成器

    在處理跨平臺的數(shù)據(jù)交換或網(wǎng)絡(luò)通信時,字節(jié)流的重要性更加突出,不同的系統(tǒng)可能有不同的字節(jié)序(大端序或小端序),因此在發(fā)送和接收字節(jié)流時,可能需要考慮字節(jié)序的轉(zhuǎn)換,這篇文章主要介紹了C++實(shí)用庫之字節(jié)流合成器,需要的朋友可以參考下
    2024-04-04
  • Qt增加版本公司等信息兩種方式

    Qt增加版本公司等信息兩種方式

    在項目中生成exe或者動態(tài)庫過程中可能需要加入公司信息、版本號、說明等等,下面這篇文章主要給大家介紹了關(guān)于Qt增加版本公司等信息的兩種方式,需要的朋友可以參考下
    2024-01-01
  • C++ 將字符串值賦給CHAR數(shù)組的實(shí)現(xiàn)

    C++ 將字符串值賦給CHAR數(shù)組的實(shí)現(xiàn)

    這篇文章主要介紹了C++ 將字符串值賦給CHAR數(shù)組的實(shí)現(xiàn),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-01-01
  • C++基于easyx圖形庫實(shí)現(xiàn)推箱子游戲

    C++基于easyx圖形庫實(shí)現(xiàn)推箱子游戲

    這篇文章主要為大家詳細(xì)介紹了C++基于easyx圖形庫實(shí)現(xiàn)推箱子游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-06-06
  • C++映像劫持后門實(shí)例分析

    C++映像劫持后門實(shí)例分析

    這篇文章主要介紹了C++映像劫持后門,實(shí)例分析了C++映像劫持后門的原理與相關(guān)實(shí)現(xiàn)技巧,有助于進(jìn)一步了解后門的原理,需要的朋友可以參考下
    2015-04-04
  • C++中模板和STL介紹詳解

    C++中模板和STL介紹詳解

    今天小編就為大家分享一篇關(guān)于C++模板和STL的介紹,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2021-09-09

最新評論