數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)分析基于哈夫曼樹的文件壓縮解壓程序

1、PAGE PAGE 54數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)分析基于哈夫曼樹的文件壓縮/解壓程序 計(jì)算機(jī)科學(xué)學(xué)院專業(yè)班號 2010-10-20一 需求分析1.課題要求（實(shí)現(xiàn)文件的壓縮與解壓并計(jì)算壓縮率）A.描述壓縮基本符號的選擇方法B.運(yùn)行時(shí)壓縮原文件的規(guī)模應(yīng)不小于5KC.提供恢復(fù)文件與原文件相同性對比功能2.設(shè)計(jì)目標(biāo)A軟件名稱：基于哈夫曼編碼的文件壓縮實(shí)用程序系統(tǒng)B軟件組成：Winhfm.exe dosHfm.exe C制作平臺及相關(guān)調(diào)試工具： Windows2000sp4 Borland C+ Builder 6Dev-C+ UltraEdit-32D運(yùn)行環(huán)境：dos/win98/winMe/win2K/wi

2、nxpE性能特點(diǎn)：軟件由兩個(gè)可執(zhí)行文件組成，各具特點(diǎn)DosHfm.exe為dos系統(tǒng)應(yīng)用程序，體積小，高效快捷，適用范圍廣。WinHfm.exe 為windows應(yīng)用程序，界面友好，使用方便。2. 對單字節(jié)（256葉子）進(jìn)行哈夫曼編碼，壓縮率良好使用二級緩沖壓縮/解壓技術(shù)，速度比一般算法高75%以上3可壓縮最大體積為4G的文件，達(dá)到Fat32文件系統(tǒng)極限4. 文件索引體積比常規(guī)算法小50%5壓縮過程中顯示壓縮進(jìn)度并有相關(guān)信息提示6WinHfm.exe可圖形顯示源文件的哈夫曼編碼構(gòu)造樹二概要設(shè)計(jì)1.相關(guān)函數(shù)介紹 dos版本程序下的有關(guān)函數(shù).void Haffman(int nodeCode,in

3、t length,int sum,vector pair &hfmCode,vector &lchild,vector &rchild)哈夫曼樹編碼遞歸函數(shù)void indexSearch(int nodeCode,vector &lchild,vector &rchild,vector &index,vector&code)索引編碼遞歸函數(shù)void makeIndex(int nodeCode,int &tt,vector &index,int &indexNum,list &code,vector &lchild,vector &rchild)索引解碼遞歸函數(shù)void Compress()

4、壓縮函數(shù)void UnCompress()解壓縮函數(shù)windows版本程序下的新增函數(shù)AnsiString ShowNowTime()計(jì)算當(dāng)前時(shí)間（精確到毫秒，以字符串返回）。.void search(int nodeCode,int &i,vector &lchild,vector &rchild)遞歸計(jì)算每個(gè)節(jié)點(diǎn)的X坐標(biāo). void searchdraw(int nodeCode,int height,vector &lchild,vector &rchild)遞歸做圖函數(shù).void _fastcall TForm1:Paga1OnDrawTab(TCustomTabControl *Co

5、ntrol,int TabIndex, const TRect &Rect, bool Active)PageControl的標(biāo)簽頁的色彩描繪void _fastcall TForm1:CompareFiles(TObject *Sender)文件比對函數(shù) 當(dāng)然還有一些相關(guān)按鈕的響應(yīng)函數(shù)，在此不在贅述，詳見程序清單部分函數(shù)調(diào)用示意圖三 詳細(xì)設(shè)計(jì)壓縮算法部分A核心算法：文件由若干個(gè)字節(jié)組成，一個(gè)字節(jié)有8bits，故有28=256種字節(jié)構(gòu)成形式，對應(yīng)字節(jié)碼為0-255。按此256種字節(jié)出現(xiàn)頻率可構(gòu)造haffman樹進(jìn)行重新編碼，編碼后每字節(jié)的新編碼平均長度將8，輸出前8位（用&操作可屏蔽掉后24位

6、），此時(shí)緩沖器清除前8位（a=a8）,然后一次性讀入B的代碼置入a中，此時(shí)a容量為3+15=18位，此時(shí)輸出前8位，現(xiàn)在 a=10位仍然大于8,在輸出8位，剩余2位與下面的編碼繼續(xù)組合輸出。顯然，無論在運(yùn)算時(shí)間上和存儲(chǔ)空間上，后者均占明顯優(yōu)勢。當(dāng)然后者出現(xiàn)了&與運(yùn)算 王浩面向?qū)ο蟪绦蛟O(shè)計(jì)35-36頁2 沈美明 溫冬蟬ibm-pc匯編語言程度設(shè)計(jì)61-62頁，而這樣的運(yùn)算相當(dāng)于匯編語言的AND與SAL2指令，是非常高效迅速的，比從內(nèi)存讀編碼快捷，且操作次數(shù)也少的多。F寫入算法另一角度的優(yōu)化使用二級1024K緩沖器在寫入編碼的過程中，宏觀的過程是：以字節(jié)形式讀取原文件，然后找到該字節(jié)的編碼，進(jìn)而以

7、字節(jié)形式寫到壓縮文件中去。不停的字節(jié)讀寫會(huì)給cpu帶來頻繁的中斷并且硬盤的磁頭來回在磁道扇區(qū)中移動(dòng)，減慢了速度。而如果以數(shù)據(jù)塊的形式讀寫則可以有效地利用到DMA通訊 戴梅萼 史嘉權(quán)微型計(jì)算機(jī)技術(shù)及應(yīng)用第二版199-201頁，減少了cpu中斷，并使硬盤磁頭連續(xù)移動(dòng)，顯著加快了速度。而c+語言的iofstream類的read（）與write（）成員函數(shù)為此思想的實(shí)現(xiàn)提供了可能。 所以，可以開辟一個(gè)1024K的緩沖區(qū)，先將文件前1024K的字節(jié)讀入內(nèi)存緩沖區(qū)中（在本設(shè)計(jì)中，這稱為二級緩沖器），編碼后的字節(jié)也不急于寫入文件中，而是先寫到另一個(gè)二級緩沖區(qū)中，當(dāng)其足夠1024K時(shí)再以數(shù)據(jù)塊的形式寫到壓縮文

8、件中。然后清空緩沖區(qū)，繼續(xù)做下一個(gè)1024K的編碼寫入。而緩沖區(qū)本身，其實(shí)就是二個(gè)整形數(shù)組，read_buffer1048576和write_buffer1048576。不過這樣的數(shù)組聲明已經(jīng)太大了，可以用STL的vector向量類來代替這個(gè)數(shù)組（vector結(jié)構(gòu)實(shí)際也就是一個(gè)封裝了的加強(qiáng)型數(shù)組）。一級緩沖器在微觀上解決了寫編碼速度的問題，而二級緩沖器則在宏觀上改善了寫編碼的問題，兩者關(guān)系的嵌套的關(guān)系，實(shí)際的程序主結(jié)構(gòu)也就是一個(gè)二重循環(huán)，外層控制二級緩沖器，內(nèi)層控制一級緩沖器。G一些細(xì)節(jié)問題采用以單字節(jié)為單位構(gòu)造哈夫曼樹，這樣數(shù)的規(guī)模不會(huì)太過龐大，構(gòu)造的時(shí)間比較快，并且有比較良好的壓縮率（詳細(xì)

9、的壓縮報(bào)告見附錄二）。如果以雙字節(jié)構(gòu)造，則可能出現(xiàn)葉子數(shù)為65536的哈夫曼樹，雖然壓縮率可以得到相對提高，但已經(jīng)提升不明顯，而整個(gè)的壓縮過程將變的緩慢。如果進(jìn)行智能識別頻率采樣，一方面采樣過程又要花費(fèi)一定的時(shí)間，另一方面，哈夫曼樹本身的結(jié)構(gòu)也決定了這樣做并不劃算，也給解壓縮和寫入索引帶來了許多麻煩。用left和right數(shù)組來描述一顆二叉樹而沒有用指針，是為了避免指針可能帶來的由葉子到根的反向建樹的麻煩；另一方面，樹的節(jié)點(diǎn)和葉子數(shù)目基本確定，沒太多必要使用靈活的指針和相關(guān)的內(nèi)存分配語句。編碼寫出后，內(nèi)層緩沖器可能剩幾個(gè)bit，沒有達(dá)到8bit,此時(shí)應(yīng)補(bǔ)0或1以湊齊8位再寫出。文件的大小也不大

10、可能正好被1024K整除，要考慮到最后的剩余部分字節(jié)的編碼，即要計(jì)算好最后的實(shí)際字節(jié)讀取個(gè)數(shù)，fstream的成員函數(shù)gcount() 王浩 面向?qū)ο蟪绦蛟O(shè)計(jì) 第245頁能解決這個(gè)問題。如果把整個(gè)壓縮過程作為一個(gè)函數(shù)的話，二級緩沖區(qū)的定義最好在函數(shù)外作為全局量定義，否則可能棧溢出。2解壓縮算法部分A.基于字符匹配的解壓算法現(xiàn)在從已壓縮過的文件中讀取一段代碼，如”1001011101”,哈夫曼樹結(jié)構(gòu)入圖，先讀如第一個(gè)字節(jié)”10010111”,先取出“1”，在ABCD中均無這個(gè)編碼；于是再取出“0”和剛才的“1”組成“01”，仍無此編碼；再取出“0”，組成“010”，發(fā)現(xiàn)B葉子的編碼與之相等，此時(shí)

11、解碼得B,輸出到解碼文件中，以此類推。這是最容易想到的方法，但效率很低。首先，取出一個(gè)編碼后要和所有葉子的編碼比對；其次，編碼比對是基于字符串的比對，比較慢。對于前者的改進(jìn)可以通過：1.一旦比對成功就不再和剩下的比對2.按照編碼的長度之后長度相同的編碼比對等等。而后者的改進(jìn)則出現(xiàn)了B算法。B.基于數(shù)值匹配的算法既然字符比對比較慢，我們可以把編碼用2個(gè)整數(shù)表示，前者是編碼的十進(jìn)制值，后者是編碼長度。這樣只和編碼長度相等的十進(jìn)制相比就可以了。這樣把字符串的比較優(yōu)化為數(shù)字比較，據(jù)測算，速度提高了約10倍。但是這兩種算法都基于與葉子編碼比較，相當(dāng)于不斷的嘗試，解壓速度很難突破100KB/s。C.基于循

12、徑法既然所有的編碼都隱藏在一個(gè)樹中，那么根據(jù)遇0向左走遇1向右走的方法自然就能很容易地找到葉子，從而得到解碼。仍如前例，讀入”1”向右走，發(fā)現(xiàn)不是葉子，繼續(xù)；讀入”0”向左走，發(fā)現(xiàn)不是葉子，繼續(xù)；讀入”0”向左走，發(fā)現(xiàn)是葉子B，即可解碼為B寫入解碼文件。也就是說，循徑法充分地利用了每次讀進(jìn)來的編碼，能夠以確定的路徑找到葉子而不需要嘗試。不過要使用這種方法，就必須想建立一個(gè)原文件的哈夫曼樹，詳見索引算法部分。使用此方法后速度有極大飛躍。D.緩沖輸入輸出和壓縮時(shí)采用1M二級緩沖相同，如果的壓縮時(shí)也采用此技術(shù)，也會(huì)有很大的速度優(yōu)化，當(dāng)然程序也變得更加復(fù)雜。E.細(xì)節(jié)問題讀入和寫出仍然基于字節(jié)單位，基于

13、位的操作同樣要在程序內(nèi)部通過位運(yùn)算完成。最后一個(gè)字節(jié)在解碼時(shí)必須注意到壓縮時(shí)最后一個(gè)字節(jié)是用”0”或”1”填充的，要避免多余解碼，可以在索引中寫入文件大小，詳見下節(jié)。3文件索引算法簡介由解壓縮的算法可知，一個(gè)壓縮了的文件解壓縮的前提是知道原文件的具體每個(gè)字節(jié)的編碼。這些信息稱為索引。上頁的細(xì)節(jié)問題中提到最好在壓縮后的文件中標(biāo)出原文件的長度，這也是索引信息。一般索引信息放在文件的最前部分。寫入編碼法最直接的方法就是，把每個(gè)字節(jié)的編碼寫到壓縮后的文件中去。入圖，先寫入A及其編碼0，接著是B及編碼100,C101,D11。即：01000001 0 01000010 100 01000011 101

14、01000100 11A B C D當(dāng)然直接這樣寫會(huì)給閱讀信息造成困難，因?yàn)橛?jì)算機(jī)不知道A的編碼是幾位，它讀入0后就不知道是否下一位究竟是A的編碼還是B的ASCII的開始。所以我們還得標(biāo)識出編碼的長度A1 B3 C3 D2,即01000001 00000000 0 01000010 00000011 100 01000011 00000011 101 01000100 00000010 11A 長度0 B 長度3 C 長度3 D 長度2這樣的確是區(qū)別開了，沒有歧義，可是編碼變長了，我們可以規(guī)定葉子是按順序排列的，此時(shí)編碼就變短了，即：00000000 0 00000011 100 000000

15、11 101 00000010 11A的長度 B的長度 C的長度 D的長度事實(shí)上最大一共有256個(gè)葉子，計(jì)算機(jī)依次讀256次就可以了。這樣索引占用的長度一般是512K左右。不過一旦一個(gè)文件只有5片葉子，也得有256個(gè)字節(jié)來標(biāo)識編碼長度，這在壓縮只有幾個(gè)字節(jié)的小文件時(shí)，反而文件會(huì)擴(kuò)大幾十倍。寫入樹結(jié)構(gòu)法如果我們知道原文件的哈夫曼樹的結(jié)構(gòu)，也自然就可獲知每個(gè)葉子的編碼，那么，把這棵樹的結(jié)構(gòu)作為索引存入文件也可以，如果樹可大可小，索引的長度也會(huì)可大可小，解決了B方法索引長度始終大于256字節(jié)的問題。如上圖，如果非葉子節(jié)點(diǎn)為#,這個(gè)樹的結(jié)構(gòu)編碼 胡學(xué)鋼 王浩 軟件系列課程實(shí)踐教程第49頁“擴(kuò)展二叉樹”

16、就是”#A.#B.C.D.”而且哈夫曼樹有一個(gè)性質(zhì)，如果一個(gè)節(jié)點(diǎn)有左孩子，就一定有右孩子，如果沒有左孩子，也必然沒有右孩子。由此沒有必要再用點(diǎn)號來表示葉子了，因而樹結(jié)構(gòu)簡化成”#A#B#CD”,再用1表示葉子，0表示非葉子，則為”01001011”，這就是它的存儲(chǔ)實(shí)現(xiàn)。如下：00000100 01000001 01000010 01000011 01000100 01001011有4個(gè)節(jié)點(diǎn) A B C D 樹結(jié)構(gòu)對于一棵完整的有256個(gè)葉子的haffman樹，大約需要320字節(jié)就可以存儲(chǔ)它了。比前面的方法節(jié)省了38%。當(dāng)然，要使用這種方法，就必須在壓縮時(shí)用一個(gè)遞歸函數(shù)來遍歷這棵樹以獲得樹結(jié)構(gòu)編

17、碼。D.關(guān)于索引的解碼AB兩種建索引的方法都很方便于索引的解碼，但空間占用大后者靈活性差，而若使用C方法，則索引的解碼也成了問題。換句話說，我們得由“01001011”來還原出一棵haffman樹。本系統(tǒng)是這樣做的，首先得把樹結(jié)構(gòu)編碼從文件中讀到一個(gè)數(shù)組中，把葉子編號讀到另一個(gè)數(shù)組中，然后由這兩個(gè)數(shù)組用遞歸的方法造出樹。然后由這棵樹再求出每個(gè)葉子的編碼。當(dāng)然這一步可以略去了，因?yàn)榻鈮嚎s采用尋徑法，不需要再求每個(gè)葉子的具體編碼了。E.相關(guān)細(xì)節(jié)問題為了給正文部分解碼代碼方便并顯示解碼進(jìn)度，本系統(tǒng)在壓縮的文件開頭的四個(gè)字節(jié)記錄了原文件的長度。索引中，節(jié)點(diǎn)的順序和結(jié)構(gòu)樹的順序必須相同，例如都采用先序，

18、中序或后續(xù)，本系統(tǒng)采用先序。索引的編碼和解碼都用到了遞歸，而遞歸的參數(shù)都相當(dāng)多而且很多是數(shù)組，為了節(jié)省空間，要運(yùn)用引用操作。4. 哈夫曼樹顯示算法A.簡介在本系統(tǒng)的windows版本的程序中，有顯示哈夫曼樹的功能，這涉及到了計(jì)算機(jī)做圖以及一些具體的算法。B.節(jié)點(diǎn)的布局一棵樹在描繪之前必須要計(jì)算好每個(gè)節(jié)點(diǎn)的坐標(biāo)，否則漫無目的地從頭節(jié)點(diǎn)分左右畫下去就很可能造成節(jié)點(diǎn)位置的重合。Y軸的坐標(biāo)比較好控制，因?yàn)樗泄?jié)點(diǎn)的深度決定了。X軸呢？本系統(tǒng)利用中序遍歷haffman樹，對葉子節(jié)點(diǎn)X坐標(biāo)遞增的方法來確定的。例如左樹，中序依次遍歷了ABCD，于是ABCD的橫坐標(biāo)就是1，2，3，4。而非葉子節(jié)點(diǎn)的橫坐標(biāo)取左

19、右孩子的橫坐標(biāo)的平均值，顯然這是一個(gè)遞歸算法。C.具體的描繪知道每個(gè)節(jié)點(diǎn)的坐標(biāo)后，就可以開始描繪了，畫圓與直線的函數(shù)都有了，因而遍歷所有的節(jié)點(diǎn)也就可以把整個(gè)樹給畫出來了。細(xì)節(jié)問題計(jì)算坐標(biāo)和描繪節(jié)點(diǎn)都是遞歸方法，因?yàn)槌绦虻闹黧w就是二個(gè)遞歸程序。由于節(jié)點(diǎn)眾多，整個(gè)樹畫出來需要非常寬的幅面，大約個(gè)象素的寬度。在windows98系統(tǒng)中不支持如此大的幅面，而在window2000和windowsXP中支持，因而本系統(tǒng)作圖功能不能在win98下體現(xiàn)甚至出現(xiàn)異常而終止了整個(gè)壓縮程序。因而作圖這一部分得使用try/catch 任常銳 黎濤C+ builder高級編程296頁這樣的異常處理機(jī)制以確保壓縮程序在

20、各個(gè)系統(tǒng)的穩(wěn)定運(yùn)行。畫出來的圖比較大，一個(gè)屏幕顯示不下，而僅使用滾動(dòng)條又比較麻煩，因而本系統(tǒng)采用了“手抓”功能，可以用鼠標(biāo)拖動(dòng)畫面。5. 文件比對算法本系統(tǒng)具有文件比對功能，它的算法如下：首先，如果兩個(gè)文件長度不相等，顯然文件不相等，無須進(jìn)一步比較了。怎么知道指定的文件的長度呢？如果把文件讀一遍當(dāng)然可以知道它的長度，但這樣太消耗時(shí)間?？梢岳脦斓膄ilelength函數(shù)來直接求得文件長度。如果兩個(gè)文件長度相同，則可以正式比對。同樣為了加快速度，在此也用了全部變量的緩沖器。文件A可以用M的讀入緩沖器，文件B可以用M的寫出緩沖器。然后一一對比，一旦出現(xiàn)不相同，則停止比對，輸出“不相等”,程序返回。

21、如果均相同，則文件相等。至此，整個(gè)算法的描述都已經(jīng)敘述完了，本系統(tǒng)采用的算法均為以上各部分的最優(yōu)算法，因而程序的結(jié)構(gòu)比較復(fù)雜。四 調(diào)試分析序號時(shí)間相關(guān)信息110月30日dos版，基于字符串編碼211月6日編碼存儲(chǔ)結(jié)構(gòu)改為雙整數(shù)表達(dá)，改進(jìn)了解壓縮的性能。311月7日采用長度與數(shù)據(jù)分開存儲(chǔ)的方法構(gòu)建索引減少了索引長度411月16日基于位操作編碼及解碼，大幅度提高效率511月18日編碼方案采用二重緩沖，進(jìn)一步加快效率611月20日采用尋徑法解碼，提高解碼速度，并采用樹索引，取代代碼索引711月22日開發(fā)windows版本811月26日加入編碼部分的進(jìn)度提示911月29日加入選取文件功能，交互性更強(qiáng)1

22、012月4日圖形顯示哈夫曼構(gòu)造樹1112月5日改進(jìn)顯示外觀 使樹結(jié)構(gòu)更加對稱1212月6日加入“手抓”功能1312月10日更正了某些文件名不能壓縮的問題1412月12日加入文件比對功能1512月13日更正了壓縮時(shí)可能出現(xiàn)的一個(gè)重大錯(cuò)誤1612月14日完善用戶操作部分，避免了某些誤操作1712月15日解決了win98下因無法作大圖而終止運(yùn)行的問題五 用戶使用說明（略）六 測試結(jié)果（一）各種類型文件的壓縮率測試文件大小壓縮后壓縮率%文本文件（txt）文件1（英文文本1）77465515666657文件2（英文文本2）65194351165399文件3（中文文本1）2897722216957652文

23、件4（中文文本2）110421660885985文件5（混合文本）1679791321817869Word文檔（doc）文件1（英文文本1）2618791341725123文件2（英文文本2）1464321078097362文件3（中文文本1）50688308366083文件4（中文文本2）28672150905262文件5（混合文本）8376326496757760網(wǎng)頁文件（htm,mht）文件1（無圖片）431730767125文件2（有圖片）5045393734417401文件3（有圖片）1658321105566674幻燈片文件（ppt）文件11996801411517068文件210

24、2912566695506電子表格文件（xls）文件133280154524643文件23584001952865448位圖文件（bmp）文件1（16色文件）3082782833959192文件2（256色文件）137218407552970文件3（24位真彩）4302142631756117可執(zhí)行文件（exe）文件194208674537160文件26635524974007496文件3156627814593499317（二）速度測試 為避免偶然因素，本項(xiàng)測試選取一個(gè)600M左右（621889873 byte）的虛擬光驅(qū)文件，壓縮三次，取平均值。壓縮時(shí)間壓縮速率解壓縮時(shí)間解壓縮速率第一次1

25、10.297s5506Kb/s145.359s4178Kb/s第二次107.859s5631Kb/s150.344s4039Kb/s第三次120.359s5046Kb/s141.313s4298Kb/s平均值112.838s5382Kb/s145.611s4171Kb/s以上測試環(huán)境：CPU:celeron1.7GHz,內(nèi)存：DDR256M,硬盤：60GB（7200rpm）,系統(tǒng)：windows XP.七 設(shè)計(jì)心得體會(huì)數(shù)據(jù)結(jié)構(gòu)是一門重要并且艱深的課程，學(xué)好這門課既需要聰明的大腦，更需要長期的編程實(shí)踐。在做本課程設(shè)計(jì)中，前前后后花了一個(gè)半月的時(shí)間。算法也是越琢磨越明白，看問題也越來越深刻，本程序

26、共做了四次比較大規(guī)模的修改，如果沒有前面Pascal與c+的基礎(chǔ)，光修改程序的工作量就是不可想象的，其間還重寫了一次原代碼，可見，數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)是密不可分的。另外，本課程設(shè)計(jì)中，還直接或間接地聯(lián)系到了計(jì)算機(jī)組成原理，微機(jī)接口，匯編語言等其它相關(guān)課程，可見，計(jì)算機(jī)是一個(gè)統(tǒng)一的學(xué)科，沒有其他課程的知識儲(chǔ)備，仍然是不能實(shí)現(xiàn)本設(shè)計(jì)的。 另外在本課程設(shè)計(jì)中，我了解到了快速應(yīng)用程序開發(fā)的工具borland c+ builder 6這是一個(gè)龐大的系統(tǒng)，我閱讀很多相關(guān)的資料和網(wǎng)頁，這種知識則是課內(nèi)所學(xué)不到的。最后，感謝老師在平時(shí)對我的指導(dǎo)與鼓勵(lì)，正是課間給我的精辟回答使我有了更為明晰的思路，才有最終的設(shè)計(jì)

27、結(jié)果。八 附錄（此部分不用打印）程序清單在此，給出winhfm.exe的程序清單。Dos版本的程序清單在此略過。#include #pragma hdrstop#include Unit1.h#include Unit3.h#include #include #include #include #include #include #include #include using namespace std;#pragma package(smart_init)#pragma resource *.dfmchar inputFileBuffer1048576;char wantFileBuffer

28、1048576;vector X(511,0);AnsiString ShowNowTime()Word H, M, S,Ms;DecodeTime(Now(), H, M, S,Ms);AnsiString sH=AnsiString(H);AnsiString sM=AnsiString(M);AnsiString sS=AnsiString(S);AnsiString sMs=AnsiString(Ms);if (sM.Length()=1)sM=0+sM;if (sS.Length()=1)sS=0+sS;if (sMs.Length()=1)sMs=00+sMs;if (sMs.Le

29、ngth()=2)sMs=0+sMs;return sH+點(diǎn)+sM+分+sS+秒+sMs;void Haffman(int nodeCode,int length,int sum,vector pair &hfmCode,vector &lchild,vector &rchild) if (nodeCode=-1) return; if (nodeCode=255) hfmCodenodeCode.first=length; hfmCodenodeCode.second=sum; return; Haffman(lchildnodeCode,length+1,sum*2,hfmCode,lch

30、ild,rchild); Haffman(rchildnodeCode,length+1,sum*2+1,hfmCode,lchild,rchild);void search(int nodeCode,int &i,vector &lchild,vector &rchild) if (lchildnodeCode=-1) XnodeCode=i; i+; return; search(lchildnodeCode,i,lchild,rchild); search(rchildnodeCode,i,lchild,rchild); XnodeCode=(XlchildnodeCode+Xrchil

31、dnodeCode)/2;void searchdraw(int nodeCode,int height,vector &lchild,vector &rchild) if (nodeCode=-1) return; if (lchildnodeCode=-1) Form3-Image1-Canvas-Brush-Color=clWhite; Form3-Image1-Canvas-TextOut(XnodeCode*20-5,height*60+14,AnsiString(nodeCode); Form3-Image1-Canvas-Brush-Color=clRed; Form3-Imag

32、e1-Canvas-Ellipse(XnodeCode*20-5,height*60-4,XnodeCode*20+10+4,height*60+10+4); Form3-Image1-Canvas-TextOut(XnodeCode*20-1,height*60-1,height); Form3-Image1-Canvas-Brush-Color=clYellow; if (lchildnodeCode!=-1) Form3-Image1-Canvas-MoveTo(XnodeCode*20+5,height*60+10+4); Form3-Image1-Canvas-LineTo(Xlch

33、ildnodeCode*20+5,height*60+60-4); searchdraw(lchildnodeCode,height+1,lchild,rchild); Form3-Image1-Canvas-MoveTo(XnodeCode*20+5,height*60+10+4); Form3-Image1-Canvas-LineTo(XrchildnodeCode*20+5,height*60+60-4); searchdraw(rchildnodeCode,height+1,lchild,rchild); void indexSearch(int nodeCode,vector &lc

34、hild,vector &rchild,vector &index,vector&code) if (nodeCode256) index.push_back(1);code.push_back(nodeCode);return; index.push_back(0); indexSearch(lchildnodeCode,lchild,rchild,index,code); indexSearch(rchildnodeCode,lchild,rchild,index,code); void makeIndex(int nodeCode,int &tt,vector &index,int &i

35、ndexNum,list &code,vector &lchild,vector &rchild) if (indexindexNum+=1) lchildnodeCode=code.front();code.pop_front(); else lchildnodeCode=tt+; makeIndex(lchildnodeCode,tt,index,indexNum,code,lchild,rchild); if (indexindexNum+=1) rchildnodeCode=code.front();code.pop_front(); else rchildnodeCode=tt+;

36、makeIndex(rchildnodeCode,tt,index,indexNum,code,lchild,rchild); TForm1 *Form1;/_fastcall TForm1:TForm1(TComponent* Owner) : TForm(Owner)/void _fastcall TForm1:Compress(TObject *Sender) if (!FileExists(Edit1-Text) ShowMessage(Edit1-Text+ 文件不存在!); return; Edit8-Text=; Edit9-Text=; Edit10-Text=; Edit11

37、-Text=; Edit12-Text=; Edit13-Text=; Label1-Caption=; Label2-Caption=; Label3-Caption=; Label4-Caption=; Label5-Caption=; Label6-Caption=; Label20-Caption=; Label26-Font-Color=clOlive; ProgressBar1-Position=0; ProgressBar3-Position=0; StatusBar1-Panels-Items0-Text=; StatusBar1-Panels-Items1-Text=;Edi

38、t8-Text=ShowNowTime();Label21-Font-Color=clNavy;Form1-Update(); ifstream fin,fin1; ofstream fout; vector frequent(256,0); vector lchild(512,-1); vector rchild(512,-1); vector pair hfmCode(256); int newNodeCode=255; int inputFileByte; int wantFileByte=0; int wantFileIndexByte=0; int wantFileContentBi

39、t=0; int wantFileContentByte; int buffer; int buffersize; int inputFileRestSize; int inputFileMega=0; char *inputFileName=new charEdit1-Text.Length()+1; strcpy(inputFileName,Edit1-Text.c_str(); char *wantFileName=new charEdit4-Text.Length()+1; strcpy(wantFileName,Edit4-Text.c_str(); int handle=open(

40、inputFileName,O_RDONLY); inputFileByte=filelength(handle); close(handle); int step; fin.open(inputFileName,ios:binary);/下面統(tǒng)計(jì)該文件的編碼頻率分布Edit9-Text=ShowNowTime(); Label21-Font-Color=clOlive;Label22-Font-Color=clNavy;Form1-Update(); while(1) fin.read(inputFileBuffer,1048576); if (fin.eof() break; for(in

41、t i=0;i1048576;i+) int t=inputFileBufferi; if (tPosition=inputFileMega*1048576/double(inputFileByte)*100; inputFileRestSize=fin.gcount();Label6-Caption=原文件共+AnsiString(inputFileByte)+byte;Form1-Update(); for(int i=0;iinputFileRestSize;i+) int t=inputFileBufferi; if (tPosition=100;/下面構(gòu)建哈夫曼樹Edit10-Tex

42、t=ShowNowTime();Label22-Font-Color=clOlive;Label24-Font-Color=clNavy;Form1-Update(); set pair nodes; for (int i=0;i1) set pair :iterator a,b; a=nodes.begin(); if (a-first=0) nodes.erase(a); continue; b=+nodes.begin(); newNodeCode+; lchildnewNodeCode=a-second; rchildnewNodeCode=b-second; nodes.insert

43、(make_pair(a-first+b-first,newNodeCode); nodes.erase(a); nodes.erase(b); /下面調(diào)用haffman遞歸函數(shù)，對haffman樹各葉子進(jìn)行編碼 Haffman(newNodeCode,0,0,hfmCode,lchild,rchild);Label20-Caption=開始描繪哈夫曼樹圖;Form1-Update();try int t=1;search(newNodeCode,t,lchild,rchild);Form3-Image1-Canvas-Brush-Color=clWhite;Form3-Image1-Canv

44、as-Rectangle(0,0,6000,1500);Form3-Image1-Canvas-Brush-Color=clYellow;Form3-Image1-Canvas-MoveTo(XnewNodeCode*10,40);searchdraw(newNodeCode,1,lchild,rchild);Form3-Show();Form3-Update();catch(.)Label20-Caption=哈夫曼樹圖描繪失敗,請使用win2000;Form1-Update();goto BEGININDEX; Label20-Caption=完成哈夫曼樹圖;Form1-Update();

45、BEGININDEX:/索引準(zhǔn)備工作Edit11-Text=ShowNowTime(); Label24-Font-Color=clOlive;Label23-Font-Color=clNavy;Form1-Update(); vector index; vectorcode; indexSearch(newNodeCode,lchild,rchild,index,code);/下面估計(jì)壓縮后文件長度 wantFileIndexByte+=4; wantFileIndexByte+=1; wantFileIndexByte+=code.size(); int u=newNodeCode-255

46、+code.size(); if(u%8) wantFileIndexByte+=u/8+1; else wantFileIndexByte+=u/8;Label2-Caption=索引長度為+AnsiString(wantFileIndexByte)+byte; for(int i=0;iCaption=AnsiString(wantFileByte*100.0/inputFileByte)+%;/下面開始寫入索引信息 fout.open(wantFileName,ios:binary);/寫入文件長度 fout.put(inputFileByte/16777216); fout.put(i

47、nputFileByte%16777216/65536); fout.put(inputFileByte%65536/256); fout.put(inputFileByte%256);/寫入根節(jié)點(diǎn)號碼 fout.put(newNodeCode-256); for(int i=0;icode.size();i+) fout.put(codei); int indexbuffer=0; int indexbuffersize=0; for(int i=0;iindex.size();i+) indexbuffer=indexbuffer1; indexbuffer+=indexi; indexb

48、uffersize+; if (indexbuffersize=8) fout.put(indexbuffer); indexbuffersize=0; indexbuffer=0; if (indexbuffersize!=0) indexbuffer=indexbufferText=ShowNowTime(); Label23-Font-Color=clOlive;Label25-Font-Color=clNavy;Form1-Update(); step=0; for(int i=1;i=inputFileMega;i+) fin1.read(inputFileBuffer,104857

49、6); for(int j=0;j1048576;j+) int t=inputFileBufferj; if (t0) t+=256; int a=hfmCodet.second; buffer+=a=8) int temp=buffer24; wantFileBufferwantFileBufferSize+=temp; buffersize-=8; buffer=buffer=step) ProgressBar1-StepIt(); StatusBar1-Panels-Items0-Text=已完成+AnsiString(step)+%; StatusBar1-Panels-Items1

50、-Text=AnsiString(CompressedByte)+字節(jié); Form1-Update(); step+; if (wantFileBufferSize=1048576) fout.write(wantFileBuffer,1048576); wantFileBufferSize=0; /寫入外層緩沖區(qū)最后的部分字節(jié) fin1.read(inputFileBuffer,inputFileRestSize); for(int i=0;iinputFileRestSize;i+) int t=inputFileBufferi; if (t0) t+=256; int a=hfmCode

51、t.second; buffer+=a=8) int temp=buffer24; wantFileBufferwantFileBufferSize+=temp; buffersize-=8; buffer=buffer=step) ProgressBar1-StepIt(); StatusBar1-Panels-Items0-Text=已完成+AnsiString(step)+%; StatusBar1-Panels-Items1-Text=AnsiString(CompressedByte)+字節(jié); Form1-Update(); step+; ProgressBar1-Position=

52、100; fout.write(wantFileBuffer,wantFileBufferSize);/寫入內(nèi)層緩沖區(qū)殘余的bit if (buffersize) fout.put(buffer24); fout.close(); fin1.close();Label3-Caption=內(nèi)容長度為+AnsiString(wantFileContentByte)+byte;Label4-Caption=壓縮后文件長度為+AnsiString(wantFileByte)+byte;Edit13-Text=ShowNowTime();Label25-Font-Color=clOlive;Label2

53、6-Font-Color=clNavy; StatusBar1-Panels-Items0-Text=已完成100%; StatusBar1-Panels-Items1-Text=AnsiString(inputFileByte)+字節(jié); Label1-Caption=ok;/void _fastcall TForm1:UnCompress(TObject *Sender) Edit7-Text=; Edit14-Text=; Label7-Font-Color=clOlive; Label8-Font-Color=clOlive; Label18-Caption=; StatusBar2-P

54、anels-Items0-Text=; StatusBar2-Panels-Items1-Text=; StatusBar2-Panels-Items2-Text=; if (!FileExists(Edit2-Text) ShowMessage(Edit2-Text+ 文件不存在!); return; Label7-Font-Color=clNavy;Edit7-Text=ShowNowTime();Form1-Update(); ifstream fin; ofstream fout; int wantFileByte=0; vector lchild(512,-1); vector rc

55、hild(512,-1); fin.open(Edit2-Text.c_str(),ios:binary); fout.open(Edit3-Text.c_str(),ios:binary); for (int i=1;i=4;i+) int t=fin.get(); if (tPanels-Items0-Text=原文件長+AnsiString(wantFileByte)+字節(jié);/讀入索引 int newNodeCode=256; int leaf=fin.get(); if (leaf0) leaf+=256; leaf+=2; listcode; for(int i=0;ileaf;i+

56、) int t=fin.get(); if (t0) t+=256; code.push_back(t); int indexSize=leaf*2-1; int indexByteSize; if(indexSize%8) indexByteSize=indexSize/8+1; else indexByteSize=indexSize/8; vector index; for(int i=1;i=indexByteSize;i+) int t=fin.get(); if (t0) t+=256; for(int j=1;j=8;j+) if(t&128) index.push_back(1

57、); else index.push_back(0); if(index.size()=indexSize) goto end1; t=t1; end1:; int indexNum=1; int nodeCode=256; int tt=257; makeIndex(nodeCode,tt,index,indexNum,code,lchild,rchild); int step=1; int haveByte=0; int searchNumber=newNodeCode; int wantFileBufferSize=0; while(1) fin.read(inputFileBuffer

58、,1048576); if (fin.eof() break; for(int i=0;i1048576;i+) int buffer=inputFileBufferi; int buffersize=8; while(buffersize) if (buffer&128) searchNumber=rchildsearchNumber; else searchNumber=lchildsearchNumber; if (searchNumber=step) StatusBar2-Panels-Items1-Text=已解壓+AnsiString(step)+%;StatusBar2-Pane

59、ls-Items2-Text=AnsiString(haveByte)+字節(jié);Form1-Update(); ProgressBar2-StepIt(); step+; if (haveByte=wantFileByte) goto end; searchNumber=newNodeCode; buffer=buffer1; buffersize-=1; for(int i=0;ifin.gcount();i+) int buffer=inputFileBufferi; int buffersize=8; while(buffersize) if (buffer&128) searchNumb

60、er=rchildsearchNumber; else searchNumber=lchildsearchNumber; if (searchNumber=step) StatusBar2-Panels-Items1-Text=已解壓+AnsiString(step)+%; StatusBar2-Panels-Items2-Text=AnsiString(haveByte)+字節(jié);Form1-Update(); ProgressBar2-StepIt(); step+; if (haveByte=wantFileByte) goto end; searchNumber=newNodeCode;