用哈夫曼編碼實現(xiàn)文件壓縮0001

1、用哈夫曼編碼實現(xiàn)文件壓縮實驗報告課程名稱實驗學期 2011數(shù)據(jù)結(jié)構(gòu)至 2012 學年 第 2學期學生所在系部計算機學院年級 2010 級專業(yè)班級 *學生姓名 *學號 *任課教師#實驗成績一、實驗題目哈夫曼編碼實現(xiàn)文件壓縮二、實驗?zāi)康模?、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握 Huffman 樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲結(jié)構(gòu)及遍歷算法。5、利用 Huffman 樹及 Huffman 編碼，掌握實現(xiàn)文件壓縮的一般原理。三、實驗設(shè)備與環(huán)境：微型計算機、 Windows 系列操作系統(tǒng)、 Visual C+6.0 軟件。四、實驗內(nèi)容：根據(jù) ASCII 碼文件中各 AS

2、CII 字符出現(xiàn)的頻率情況創(chuàng)建 Haffman 樹，再將各字 符對應(yīng)的哈夫曼編碼寫入文件中，實現(xiàn)文件壓縮。五、概要設(shè)計：本次實驗采用將字符用長度盡可能短的二進制數(shù)位表示的方法， 即對于文件中 出現(xiàn)的字符，無須全部都用 8位的 ASCII 碼進行存儲，根據(jù)他們在文件中出現(xiàn)的 頻率不同，我們利用 Haffman 算法使每個字符能以最短的二進制字符進行存儲， 以達到節(jié)省存儲空間， 壓縮文件的目的。 解決了壓縮需采用的算法， 程序的思路 已然清晰：1統(tǒng)計需壓縮文件中每個字符出現(xiàn)的頻率。2將每個字符的出現(xiàn)頻率作為葉子結(jié)點構(gòu)建 Haffman 樹，然后將樹中結(jié)點引 向其左孩子的分支標“ 0”，引向其右孩子

3、的分支標“ 1”；每個字符的編碼即為從 根到每個葉子的路徑上得到的 0、 1 序列，這樣便完成了 Haffman 編碼，將每個 字符用最短的二進制字符表示。3打開需壓縮文件，再將需壓縮文件中的每個 ASCII 碼對應(yīng)的 Haffman 編碼 按 bit 單位輸出。4文件壓縮結(jié)束。六、詳細設(shè)計：（ 1）構(gòu)造 Hufffman 樹的方法 Hafffman 算法構(gòu)造 Huffman 樹步驟：I. 根據(jù)給定的 n 個權(quán)值 w1,w2, ? wn，構(gòu)造 n 棵只有根結(jié)點的二叉樹， 令起權(quán)值為 wj 。II. 在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的 二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右

4、子樹根結(jié)點權(quán)值之和。III. 在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。 . 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。對于 Haffman 的創(chuàng)建算法，有以下幾點說明：a) 這里的 Haffman 樹采用的是基于數(shù)組的帶左右兒子結(jié)點及父結(jié)點下標作為 存儲結(jié)點的二叉樹形式，這種空間上的消耗帶來了算法實現(xiàn)上的便捷。b) 由于對于最后生成的 Haffman 樹，其所有葉子結(jié)點均為從一個內(nèi)部樹擴充 出去的，所以，當外部葉子結(jié)點數(shù)為 m個時，內(nèi)部結(jié)點數(shù)為 m-1，整個 Haffman 樹的需要的結(jié)點數(shù)為 2m-1c) 初始化 Hafffman 樹分兩步進行， 先將所有結(jié)點賦值，

5、再將前 m個葉子結(jié)點 賦初值。d) 在查找權(quán)值最小并且父結(jié)點為空的兩個結(jié)點時，通過逐個比較，將兩結(jié)點 的位置下標與權(quán)值分別保存。方便在與其父結(jié)點建立聯(lián)系時調(diào)用。2)壓縮過程的實現(xiàn)： 壓縮過程的流程是清晰而簡單的： 1創(chuàng)建 Haffman樹 2打開需壓縮文件 3將需壓縮文件中的每個 ASCII 碼對應(yīng) 的 Haffman 編碼按 bit 單位輸出 4 文件壓縮結(jié)束。 其中，步驟 1和步驟 3是壓縮過程的關(guān)鍵。a) 步驟 1: 這里所要做工作是得到 Haffman 數(shù)中各葉子結(jié)點字符出現(xiàn)的頻率并進 行創(chuàng)建。b) 步驟 3: 將需壓縮文件中的每個 ASCII 碼對應(yīng)的 Haffman 編碼按 bit

6、 單位輸 出，這是本壓縮程序中最關(guān)鍵的部分。 這里涉及“轉(zhuǎn)換”和“輸出”兩個關(guān)鍵步驟：“轉(zhuǎn)換”部分大可不必去通過遍歷 Haffman 樹來找到每個字符對應(yīng)的哈夫曼編 碼，可以將每個碼值及其對應(yīng)的 ASCII 碼存放于如下所示的結(jié)構(gòu)體中： typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode; 創(chuàng)建由該結(jié)構(gòu)體結(jié)點所組成的，長度為 128 的一維數(shù)組 codeList128 ， 且 codeList 中的下標和 asciiCode 滿足下面的順序存放關(guān)系：codeListi.asciiCode=i;

7、這樣的話，查找某個字符 inChar 的 Haffman編碼的工作便變得相當輕松了 , 如下： sHaffCode=codeListinChar.haffCode;數(shù)組 codeList128 的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進行置數(shù) 的方式，十分的方便。以下流程圖采用的是前序遍歷的方式創(chuàng)建：說明：1 在流程圖中， youBiao 中存放字符對應(yīng)的 Haffman 編碼， sDepth 中存放其 Haffman 編碼的長度。2 在代碼的編寫過程中，可用遞歸調(diào)用實現(xiàn)。（3）“輸出”部分是最重要的部分，也是最易出錯的部分。每個字符要能合 理的結(jié)束。這主要是為解壓縮考慮的，比如在最后 ,這

8、里涉及到C語言的位操作 , 要求這個算法能處理好以下幾個問題：1）每個字符所對應(yīng)的 haffCode 的比特位長度由 523位不等長，不可少輸， 多輸，輸錯任何一位，后一個字符的 haffCode 要緊跟在前一個字符的 haffCode 后面。2) 最后一個要輸出的 haffCode 的最后一位，它恰好是位于最后一個有效字符 的第一位，剩下的七個空位是要用無效的 haffCode加以填充的。 否則，如果填充 的haffCode亦為某個 ascii 字符的haffCode 時，那么在解壓縮時，則該在原被壓 縮文件中不存在的字符便會無中生有的在解壓后的文件中出現(xiàn)， 這顯然是不正確 的，應(yīng)在程序中加

9、以處理。4)main 函數(shù)部分七、測試結(jié)果及分析：運行結(jié)果：壓縮情況：實驗分析：利用 Huffman 樹進行編碼進行文件的壓縮 ,這一思想在上一學期的離散數(shù)學 課程里我們有接觸到 , 好在當時學的還不錯 , 所以在構(gòu)建 Huffman 樹和編碼這一 過程還是很容易接受的。 困難就在于怎么構(gòu)造出函數(shù)， 構(gòu)造出一個工程， 做出一 個能夠順利實現(xiàn)壓縮的程序。 這是動手能力， 實踐能力， 需要長時間的編程訓練 作為基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)， 是計算機學科的核心課程 之一。它將各個抽象的數(shù)據(jù)之間的關(guān)系建立起來， 無論是線性的、 循環(huán)的還是分 支的，都是為了建立一種方便程序的實現(xiàn)和

10、運行的結(jié)構(gòu)， 使得數(shù)據(jù)之間不再是孤 立的。它能使得我們在編程時在腦海中顯現(xiàn)更為清晰的數(shù)據(jù)關(guān)系畫面。 而且在學 習數(shù)據(jù)結(jié)構(gòu)時我們更應(yīng)該聯(lián)系所屬語言 （我們所學的是 C語言版） 的特性，這樣 才能更好的理解數(shù)據(jù)結(jié)構(gòu)的思想體系。總的來說，這次實驗帶來的收獲是很大的，提取文件數(shù)據(jù)、分析數(shù)據(jù)、構(gòu)建 Huffman 樹、替換數(shù)據(jù)對文件進行壓縮、輸出文件，一次大的實驗幾乎運用到了 我們一學期所學的所有知識。 經(jīng)過分、 析調(diào)試和了解程序的代碼， 鞏固了上課學 習的知識。平時的小程序的編寫是訓練， 而最后的綜合實驗是作為驗收 “產(chǎn)品” 是否合 格的重要依據(jù)之一。所以，我們平時的作業(yè)要認真獨立完成，否則，在考試和

11、做 綜合實驗時都會很吃力的。八、教師評語：教 師 評 價評定項目ABCD評定項目ABCD算法正確界面美觀，布局合理程序結(jié)構(gòu)合理操作熟練語法、語義正確解析完整實驗結(jié)果正確文字流暢報告規(guī)范題解正確其他：評價教師簽名：年月日附程序：Code.c #include "ECBTree.h" #include "MyAssert.h" #include <stdio.h>#include <stdlib.h>#include <string.h>#define LENGTH 128#define DEBUG 1#define RE

12、ARPOS 80 char dotTxt=".txt" char dotRer=".rer"int getBinLen(unsigned long inData);void main(int argc,char* argv)long wListLENGTH;unsigned long haffCodeListLENGTH;int haffCodeLenLENGTH;HaffCode haffListLENGTH;PHtTree myHtTree;char inputFileNameLENGTH,outputFileNameLENGTH;FILE* inp

13、utFile,* outputFile,* keyFile;int fileNameLen;char inData,outputData;unsigned long curCode,tmpBinData;int curLen,realLen,curIndex;int i;int count;unsigned long rearCode;/*rear data consult*/int rearCodeLen;if (argc<=1)printf("please enter your file address.n");return;elsestrcpy(inputFil

14、eName,argv1); strcpy(outputFileName,argv1); fileNameLen=strlen(argv1); outputFileNamefileNameLen-4='0' strcat(outputFileName,dotRer); inputFileNamefileNameLen='0' outputFileNamefileNameLen+4='0'if(inputFile=fopen(inputFileName,"rb")=NULL)printf("file path not f

15、oundn");return;fileif (DEBUG) printf("input file open successn"); assertF(outputFile=fopen(outputFileName,"wb")!=NULL,"output error");if (DEBUG) printf("output file open successn");if(keyFile=fopen("KEY .txt","rb")=NULL)printf("&g

16、t;-keyFile not founded-<n");return; for(i=0;i<LENGTH-1;i+) fscanf(keyFile,"%d,",&wListi); fscanf(keyFile,"%d;",&wListi); myHtTree=haffmanAlgorithm(LENGTH,wList);for(i=0;i<LENGTH;i+) haffListi.asciiCode=(char)i; preHaffListMake(myHtTree,myHtTree->rootIndex

17、,0x000000,0,haffList); fprintf(stdout,"haffCode List:rn");for(i=0;i<LENGTH-1;i+) fprintf(stdout,"%d,",haffListi.haffCode); fprintf(stdout,"%drn",haffListi.haffCode); fprintf(stdout,"haffCode List Len:rn");for(i=0;i<LENGTH-1;i+) fprintf(stdout,"%d,&q

18、uot;,haffListi.haffCodeLen); fprintf(stdout,"%drn",haffListi.haffCodeLen);if(DEBUG)printf("ntest start.n");curIndex=curLen=0; rearCode=haffListREARPOS.haffCode; rearCodeLen=haffListREARPOS.haffCodeLen;while(!feof(inputFile) count=0;outputData=0x01;while(count<8)if(curIndex=cur

19、Len)/1.get data.if(feof(inputFile)break;inData=fgetc(inputFile);if(inData=-1&&feof(inputFile)if(count=0)outputData=-1;else/*the rear output adjust*/for(i=0;i<8-count;i+)outputData<<=1;outputData|=(rearCode>>(rearCodeLen-1-i)&0x01);/* the consult below will make error happe

20、n! outputData<<=(8-count);*/break;curCode=haffListinData.haffCode; curLen=haffListinData.haffCodeLen; realLen=getBinLen(curCode);i=curLen-realLen;curIndex=0;if(i>0)outputData<<=1;/no need to fill bit data.i-;elsetmpBinData=(curCode>>(curLen-curIndex-1)&0x01; outputData<&l

21、t;=1;outputData|=(char)tmpBinData;curIndex+;count+;fputc(outputData,outputFile);if(DEBUG)printf("ntest ends.n");fclose(inputFile);fclose(outputFile);getchar();return;int getBinLen(unsigned long inData)int i=0;if( inData=0)return 1;elsewhile(inData!=0)inData/=2; i+;return i;ECBTree.c#includ

22、e "ECBTree.h"#include "MyAssert.h"#include <stdio.h>#include <stdlib.h>PHtTree haffmanAlgorithm(int m,EBTreeType* w)PHtTree pht;int i,j;int firstMinIndex,secondMinIndex;int firstMinW,secondMinW;pht=(PHtTree)malloc(sizeof(struct HtTree); assertF(pht!=NULL,"in haff

23、man algorithm,mem apply failuren"); /*Initialize the tree array*/for(i=0;i<2*m-1;i+) pht->hti.llinkIndex=-1; pht->hti.rlinkIndex=-1;pht->hti.parentIndex=-1;if(i<m) pht->hti.ww=wi; pht->=(char)i;else pht->hti.ww=-1;for(i=0;i<m-1;i+)/new Inner Node Num:m-1 first

24、MinW=MAXCHAR; firstMinIndex=-1;secondMinW=MAXCHAR; secondMinIndex=-1;for(j=0;j<m+i;j+) if(pht->htj.ww<firstMinW&&pht->htj.parentIndex=-1)/trans minFirst info to minSecond info secondMinIndex=firstMinIndex; secondMinW=firstMinW;/set new first min node. firstMinIndex=j;firstMinW=ph

25、t->htj.ww;else if(pht->htj.ww<secondMinW&&pht->htj.parentIndex=-1) secondMinW=pht->htj.ww; secondMinIndex=j; /Construct a new node. m+i is current new node's index pht->htfirstMinIndex.parentIndex=m+i; pht->htsecondMinIndex.parentIndex=m+i; pht->htm+i.ww=firstMinW

26、+secondMinW; pht->htm+i.llinkIndex=firstMinIndex; pht->htm+i.rlinkIndex=secondMinIndex;pht->rootIndex=m+i;return pht;/*Invoke: preHaffListMake(myHtTree,myHtTree->rootIndex,0x00,0,myList) */void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inList

27、) if(inTree->htrootIndex.llinkIndex=-1&&inTree->htrootIndex.rlinkIndex=-1) inListinTree->htrootI.haffCode=youBiao; inListinTree->htrootI.haffCodeLen=sDepth; else preHaffListMake(inTree,inTree->htrootIndex.llinkIndex,youBiao<<1,sDepth+1 ,inList);preHaffListMake(inTree,inTree->htrootIndex.rlinkIndex,(youBiao<<1)|0x01,sD epth+1,inList); MyAssert.c #include "myAssert.h"#include <stdlib.h>#include <stdi