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

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

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

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

4、到只含一棵樹為止，這棵樹即哈夫曼樹。對(duì)于Haffman的創(chuàng)建算法，有以下幾點(diǎn)說明：a) 這里的Haffman樹采用的是基于數(shù)組的帶左右兒子結(jié)點(diǎn)及父結(jié)點(diǎn)下標(biāo)作為存儲(chǔ)結(jié)點(diǎn)的二叉樹形式，這種空間上的消耗帶來了算法實(shí)現(xiàn)上的便捷。b) 由于對(duì)于最后生成的Haffman樹，其所有葉子結(jié)點(diǎn)均為從一個(gè)內(nèi)部樹擴(kuò)充出去的，所以，當(dāng)外部葉子結(jié)點(diǎn)數(shù)為m個(gè)時(shí)，內(nèi)部結(jié)點(diǎn)數(shù)為m-1，整個(gè)Haffman樹的需要的結(jié)點(diǎn)數(shù)為2m-1c) 初始化Hafffman樹分兩步進(jìn)行，先將所有結(jié)點(diǎn)賦值，再將前m個(gè)葉子結(jié)點(diǎn)賦初值。d) 在查找權(quán)值最小并且父結(jié)點(diǎn)為空的兩個(gè)結(jié)點(diǎn)時(shí)，通過逐個(gè)比較，將兩結(jié)點(diǎn)的位置下標(biāo)與權(quán)值分別保存。方便在與其父結(jié)點(diǎn)建

5、立聯(lián)系時(shí)調(diào)用。開始定義Hafffman樹初始化Hafffman樹i=0im-1Hafffman創(chuàng)建完畢i+將下標(biāo)為m+i的結(jié)點(diǎn)作為所找出的兩結(jié)點(diǎn)的父結(jié)點(diǎn)，建立聯(lián)系在前m+i個(gè)結(jié)點(diǎn)中找出權(quán)值最小并且父結(jié)點(diǎn)為空的兩結(jié)點(diǎn)2）壓縮過程的實(shí)現(xiàn)：壓縮過程的流程是清晰而簡單的：1創(chuàng)建Haffman樹2打開需壓縮文件3將需壓縮文件中的每個(gè)ASCII碼對(duì)應(yīng)的Haffman編碼按bit單位輸出4文件壓縮結(jié)束。其中，步驟1和步驟3是壓縮過程的關(guān)鍵。a) 步驟1:這里所要做工作是得到Haffman數(shù)中各葉子結(jié)點(diǎn)字符出現(xiàn)的頻率并進(jìn)行創(chuàng)建。b) 步驟3: 將需壓縮文件中的每個(gè)ASCII碼對(duì)應(yīng)的Haffman編碼按bit單

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

7、ffman編碼的工作便變得相當(dāng)輕松了,如下：sHaffCode=codeListinChar.haffCode;數(shù)組codeList128的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進(jìn)行置數(shù)的方式，十分的方便。以下流程圖采用的是前序遍歷的方式創(chuàng)建：說明：1 在流程圖中，youBiao中存放字符對(duì)應(yīng)的Haffman編碼，sDepth中存放其Haffman編碼的長度。2 在代碼的編寫過程中，可用遞歸調(diào)用實(shí)現(xiàn)。判斷當(dāng)前結(jié)點(diǎn)是否有孩子結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)是否有 左孩子結(jié)點(diǎn)點(diǎn)當(dāng)前結(jié)點(diǎn)是否有右孩子結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)是否有父結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)的左右孩子是否都已訪問YouBiao1,sDepth+向其左結(jié)點(diǎn)youBiao,sDep

8、th與結(jié)點(diǎn)返回其父結(jié)點(diǎn)youBiao為Haffman編碼值即開始文件的壓縮編碼成功 NY YyouBiao1丨0x01,sDepth+；結(jié)點(diǎn)指向其右結(jié)點(diǎn) N Y N Y N N Y（3）“輸出”部分是最重要的部分，也是最易出錯(cuò)的部分。每個(gè)字符要能合理的結(jié)束。這主要是為解壓縮考慮的，比如在最后,這里涉及到C語言的位操作,要求這個(gè)算法能處理好以下幾個(gè)問題：1)每個(gè)字符所對(duì)應(yīng)的haffCode的比特位長度由523位不等長，不可少輸，多輸，輸錯(cuò)任何一位，后一個(gè)字符的haffCode要緊跟在前一個(gè)字符的haffCode后面。 2)最后一個(gè)要輸出的haffCode的最后一位，它恰好是位于最后一個(gè)有效字符的

9、第一位，剩下的七個(gè)空位是要用無效的haffCode加以填充的。否則，如果填充的haffCode亦為某個(gè)ascii字符的haffCode時(shí)，那么在解壓縮時(shí)，則該在原被壓縮文件中不存在的字符便會(huì)無中生有的在解壓后的文件中出現(xiàn)，這顯然是不正確的，應(yīng)在程序中加以處理。當(dāng)文件不為空時(shí)count = 0count8當(dāng)前的一個(gè)字符對(duì)應(yīng) 的haffCode已輸出完畢將curCode中的當(dāng)前位賦值給輸 出字符左起的第count個(gè)位置輸出字符到壓縮文件讀入被壓縮文件的下一個(gè)字符，得到其 haffCode，設(shè)為 curCode，如是最后一個(gè)字符，則做相應(yīng)y的處理Count+NYN YY N（4）main 函數(shù)部分

10、開始是否成功輸入要打開文件名稱是否找到 key.txt文件將 key 文件中的值作為葉 子結(jié)點(diǎn)構(gòu)建 haffman樹實(shí)現(xiàn) haffman 編碼輸 出 ASCII 碼 對(duì) 應(yīng) 的 haffman 編碼及其長度輸出字符到壓縮文件文件壓縮結(jié)束，關(guān)閉打開的 文件返回 N Y N Y七、測試結(jié)果及分析：運(yùn)行結(jié)果：壓縮情況：實(shí)驗(yàn)分析： 利用Huffman樹進(jìn)行編碼進(jìn)行文件的壓縮,這一思想在上一學(xué)期的離散數(shù)學(xué)課程里我們有接觸到,好在當(dāng)時(shí)學(xué)的還不錯(cuò),所以在構(gòu)建Huffman樹和編碼這一過程還是很容易接受的。困難就在于怎么構(gòu)造出函數(shù)，構(gòu)造出一個(gè)工程，做出一個(gè)能夠順利實(shí)現(xiàn)壓縮的程序。這是動(dòng)手能力，實(shí)踐能力，需要長

11、時(shí)間的編程訓(xùn)練作為基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，是計(jì)算機(jī)學(xué)科的核心課程之一。它將各個(gè)抽象的數(shù)據(jù)之間的關(guān)系建立起來，無論是線性的、循環(huán)的還是分支的，都是為了建立一種方便程序的實(shí)現(xiàn)和運(yùn)行的結(jié)構(gòu)，使得數(shù)據(jù)之間不再是孤立的。它能使得我們在編程時(shí)在腦海中顯現(xiàn)更為清晰的數(shù)據(jù)關(guān)系畫面。而且在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)我們更應(yīng)該聯(lián)系所屬語言（我們所學(xué)的是C語言版）的特性，這樣才能更好的理解數(shù)據(jù)結(jié)構(gòu)的思想體系?？偟膩碚f，這次實(shí)驗(yàn)帶來的收獲是很大的，提取文件數(shù)據(jù)、分析數(shù)據(jù)、構(gòu)建Huffman樹、替換數(shù)據(jù)對(duì)文件進(jìn)行壓縮、輸出文件，一次大的實(shí)驗(yàn)幾乎運(yùn)用到了我們一學(xué)期所學(xué)的所有知識(shí)。經(jīng)過分、析調(diào)試和了解程序的代

12、碼，鞏固了上課學(xué)習(xí)的知識(shí)。平時(shí)的小程序的編寫是訓(xùn)練，而最后的綜合實(shí)驗(yàn)是作為驗(yàn)收“產(chǎn)品”是否合格的重要依據(jù)之一。所以，我們平時(shí)的作業(yè)要認(rèn)真獨(dú)立完成，否則，在考試和做綜合實(shí)驗(yàn)時(shí)都會(huì)很吃力的。八、教師評(píng)語：教 師 評(píng) 價(jià)評(píng)定項(xiàng)目ABCD評(píng)定項(xiàng)目ABCD算法正確界面美觀，布局合理程序結(jié)構(gòu)合理操作熟練語法、語義正確解析完整實(shí)驗(yàn)結(jié)果正確文字流暢報(bào)告規(guī)范題解正確其他：評(píng)價(jià)教師簽名：年 月 日附程序：Code.c#include ECBTree.h#include MyAssert.h#include #include #include #define LENGTH 128#define DEBUG 1#de

13、fine REARPOS 80char 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* inputFile,* outputFi

14、le,* 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-keyFile not founded-n);return;for(i=0;iLENGTH-1;i+)fscanf(keyFile,%d,&wListi);fscanf(keyFile,%d;,&wLis

15、ti);myHtTree=haffmanAlgorithm(LENGTH,wList);for(i=0;irootIndex,0x000000,0,haffList);fprintf(stdout,haffCode List:rn);for(i=0;iLENGTH-1;i+)fprintf(stdout,%d,haffListi.haffCode);fprintf(stdout,%drn,haffListi.haffCode);fprintf(stdout,haffCode List Len:rn);for(i=0;iLENGTH-1;i+)fprintf(stdout,%d,haffList

16、i.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(count8)if(curIndex=curLen)/1.get data.if(feof(inputFile)break;inDat

17、a=fgetc(inputFile);if(inData=-1&feof(inputFile)if(count=0)outputData=-1;else/*the rear output adjust*/for(i=0;i8-count;i+)outputData(rearCodeLen-1-i)&0x01);/* the consult below will make error happen!outputData0)outputData(curLen-curIndex-1)&0x01;outputData=1;outputData|=(char)tmpBinData;/*-*/curInd

18、ex+;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#include ECBTree.h#include MyAssert.h#include #include PHtTr

19、ee 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 haffman algorithm,mem apply failuren);/*Initialize the tree array*/for(i=0;ihti.llinkIndex=-1;pht-hti.rlinkIndex=-1;pht

20、-hti.parentIndex=-1;if(ihti.ww=wi;=(char)i;elsepht-hti.ww=-1;for(i=0;im-1;i+)/new Inner Node Num:m-1firstMinW=MAXCHAR;firstMinIndex=-1;secondMinW=MAXCHAR;secondMinIndex=-1;for(j=0;jhtj.wwhtj.parentIndex=-1) /trans minFirst info to minSecond infosecondMinIndex=firstMinIndex;secondMinW=fir

21、stMinW;/set new first min node.firstMinIndex=j;firstMinW=pht-htj.ww;else if(pht-htj.wwhtj.parentIndex=-1) secondMinW=pht-htj.ww;secondMinIndex=j;/Construct a new node. m+i is current new nodes indexpht-htfirstMinIndex.parentIndex=m+i;pht-htsecondMinIndex.parentIndex=m+i;pht-htm+i.ww=firstMinW+second

22、MinW;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)if(inTree-htrootIndex.llin

23、kIndex=-1&inTree-htrootIndex.rlinkIndex=-1)inListinTree-htrootI.haffCode=youBiao;inListinTree-htrootI.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree-htrootIndex.llinkIndex,youBiaohtrootIndex.rlinkIndex,(youBiao1)|0x01,sDepth+1,inList);MyAssert.c#include myAssert.h#include #include void assertF(int condition,char* errorMsg)if(!condition)printf(n%sn,errorMsg);abort();ECBTree.h#ifndef