【正文】 基于赫夫曼編碼的文本壓縮程序 一、目的及意義 通過課程設(shè)計(jì)的綜合訓(xùn)練，旨在幫助學(xué)生進(jìn)一步系統(tǒng)的掌握數(shù)據(jù)結(jié)構(gòu)這門課的主要內(nèi)容，并進(jìn)一步培養(yǎng)學(xué)生分析問題和解決問題的能力，主要體現(xiàn)在能夠讓學(xué)生針對(duì)實(shí)際問題有效地組織數(shù)據(jù)，選擇合適的數(shù)據(jù)結(jié)構(gòu)，并進(jìn)行正確和高效地算法設(shè)計(jì)，并用程序?qū)崿F(xiàn)算法。該課的課程設(shè)計(jì)是一個(gè)良好的程序設(shè)計(jì)技能訓(xùn)練的過程使學(xué)生能夠： ，具備初步的獨(dú)立分析和設(shè)計(jì)能力。 、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本技能和方法。 。 ，培養(yǎng)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生所具備的科學(xué)的工作方法和作風(fēng)。 二、程序功能描述 程序?qū)崿F(xiàn)的功能：對(duì)文本文件進(jìn)行壓縮以及對(duì)壓縮的文本文件進(jìn)行解壓縮。程序的實(shí)現(xiàn)的理論依據(jù)是赫夫曼編碼。赫夫曼編碼是一種無損的壓縮算法，一般用來壓縮文本和程序文件。赫夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào) (例如，文本文件中的字符 )用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些 很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。 程序由三個(gè)文件組成：頭文件 、函數(shù)實(shí)現(xiàn)文件、測(cè)試文件 。在 中聲明數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及程序所需要的處理函數(shù)； 文件實(shí)現(xiàn)在 中聲明的函數(shù)； 負(fù)責(zé)對(duì)所實(shí)現(xiàn)的函數(shù)進(jìn)行調(diào)用測(cè)試，確定是否滿足程序設(shè)計(jì)要求。 利用赫夫曼編碼實(shí)現(xiàn)對(duì)文本的壓縮的過程大致為：打開要壓縮的文本文件，讀取文件中的字符，統(tǒng)計(jì)文件中不同字符出現(xiàn)的頻率 ，建立赫夫曼樹，通過赫夫曼樹對(duì)出現(xiàn)的互不相同的字符進(jìn)行編碼，建立編碼表，接著將將赫夫曼樹 (即解碼表 )寫入壓縮文件中。再次重新讀取文件中的字符，對(duì)每個(gè)字符通過查閱編碼表確定對(duì)應(yīng)的編碼，將該字符的赫夫曼編碼寫入壓縮文件。對(duì)壓縮文件的解壓過程為：打開壓縮文件，讀取壓縮文件解碼表部分，讀取壓縮文件的編碼數(shù)據(jù)，將壓縮數(shù)據(jù)通過解碼表進(jìn)行解碼，將解碼出的字符寫入解碼文件中。 程序執(zhí)行后，用戶按照程序的提示選擇相應(yīng)的功能選項(xiàng)。當(dāng)用戶選擇壓縮功能，此時(shí)程序要求用戶輸入要壓縮的文本文件的路徑，用戶輸入完成后。程序檢查文件是否能 夠建立。檢查完成后，程序?qū)⑽募挠脖P讀入內(nèi)存。接著程序?qū)⒔y(tǒng)計(jì)不同字符出現(xiàn)的頻率以及建立編碼表的初步結(jié)構(gòu)。例如當(dāng)文件中存有如下表所示字符。 表 1文件字符屬性表 字符第一字節(jié)機(jī)內(nèi)碼 /ASCII 第二字節(jié)機(jī)內(nèi)碼權(quán)重 的 18119620 a9709 把 17620914 表 1772375 班 1762241 補(bǔ) 1781852 百 17621417 防 18319212 飛 1832021 博 17816913 包 1762522 才 1781976 方 1831898 拜 1762213 A6503 份 1832215 必 1772165 英文字符在計(jì)算機(jī)中是以標(biāo)準(zhǔn) ASCII 碼進(jìn)行表示，一個(gè)英文字符占一個(gè)字節(jié)空間，編碼范圍為 0~127；漢字在計(jì)算機(jī)中是以 GB2312 編碼進(jìn)行表示。每個(gè)漢字占兩個(gè)字節(jié)存儲(chǔ)空間，漢字的存儲(chǔ)使用機(jī)內(nèi)碼，各字節(jié)的機(jī)內(nèi)碼編碼范圍為 160~254?，F(xiàn)在需要考慮使用怎樣的數(shù)據(jù)結(jié)構(gòu)來存放這些字符，如果采用如下簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)存放： typedef struct { char data[3]； //存放字符 int internal_code1； //存放第一字節(jié)的機(jī)內(nèi)碼 /ASCII 碼 int internal_code2； //存放第 二字節(jié)的機(jī)內(nèi)碼，英文默認(rèn)為 0 int weight； //存放字符的權(quán)重 char*code； //字符的赫夫曼編碼 }CodeList,*CodePList； 分析所要處理的字符數(shù)據(jù)會(huì)發(fā)現(xiàn)：許多的字符的第一字節(jié)的機(jī)內(nèi)碼相同，如 防 、 飛 、 方 、 份 ，第一字節(jié)機(jī)內(nèi)碼都是 這是因?yàn)闈h字是通過劃分區(qū)號(hào)和位號(hào)來表示的，所有漢字被劃分成了 94 個(gè)區(qū)， 94個(gè)位，所以當(dāng)漢字屬于同一個(gè)區(qū)，那么它的第一字節(jié)機(jī)內(nèi)碼就會(huì)相同。如果采用如上的數(shù)據(jù)結(jié)構(gòu)建立的線性表來存放處理字符，就會(huì)存在大量數(shù)據(jù)冗余。 在這種情況下，就有必 要為特定的數(shù)據(jù)設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)。通過分析，采用如下數(shù)據(jù)結(jié)構(gòu)： typedef struct { char internal_code； //存放第二字節(jié)機(jī)內(nèi)碼 char*code； //存放字符的赫夫曼編碼 }InternalCode； typedef struct { int count； //已編碼字符數(shù) char internal_code； //存放第一字節(jié)機(jī)內(nèi)碼 InternalCode*internal_code_address； //第二字節(jié)機(jī)內(nèi)碼及字符的 }HuffmanCode,*HuffmanPCode； //赫夫曼編碼的地址 該結(jié)構(gòu)的優(yōu)點(diǎn)：當(dāng)漢字的第一字節(jié)機(jī)內(nèi)碼相同，則該第一字節(jié)機(jī)內(nèi)碼只會(huì)被存儲(chǔ)一次，從而消除漢字第一字節(jié)機(jī)內(nèi)碼存儲(chǔ)的冗余，而且可以方便的使用折半查找快速檢索編碼表來確定字符的赫夫曼編碼。采用該數(shù)據(jù)結(jié)構(gòu)對(duì)表 1 數(shù)據(jù)進(jìn)行表示如圖 1。 圖 1編碼表 HC 的存儲(chǔ)結(jié)構(gòu) 這種數(shù)據(jù)結(jié)構(gòu)形式上類似于圖的鄰接表結(jié)構(gòu)，功能上類似于哈希表的鏈地址法。但鄰接表的表結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)，而圖 1的表結(jié)點(diǎn)和頭結(jié)點(diǎn)都采用線性表儲(chǔ)存。圖 1中編碼表 HC 的內(nèi)碼 1是縱向非遞減排列，內(nèi)碼 2 是橫向非遞減排列。 HC[i].count– HC[i– 1].count 等于 HC[i]實(shí)際存儲(chǔ)的字符數(shù)量。例如 ,HC[3]中字符數(shù)為 7， HC[2]中字符數(shù)為 2，則 HC[3]存放了 5 個(gè)字符，這 5個(gè)字符擁有相同的第一字節(jié)機(jī)內(nèi)碼 176。 程序執(zhí)行壓縮操作詳細(xì)過程：當(dāng)程序從文件中讀取一個(gè)字符后，通過字符的編碼范圍分析該字符是屬于 ASCII還是 GB2312,若是 ASCII 編碼，增加編碼表 HC 縱向表長(zhǎng)，將該字符的 ASCII 碼按非遞減次序插入到內(nèi)碼 1處，并將當(dāng)前位置的字符數(shù)加 1，并置內(nèi)碼 2 默認(rèn)為 0；如果是漢字，首先通過折半查找算法縱向查找編碼表 HC 的內(nèi)碼 1成員，若當(dāng)前漢字第一字節(jié)機(jī)內(nèi)碼已經(jīng)出現(xiàn)過，則折半查找返回該機(jī)內(nèi)碼 1 在 HC 表中的位置，增加當(dāng)前位置的橫向表長(zhǎng)，將漢字的第二字節(jié)機(jī)內(nèi)碼按非遞減次序插入當(dāng)前位置的內(nèi)碼 2處。否則將漢字的第一字節(jié)機(jī)內(nèi)碼按非遞減次序插入 HC 表的內(nèi)碼 1 區(qū)域，第二字節(jié)機(jī)內(nèi)碼直接插入內(nèi)碼 2處。在讀取文件的同時(shí)記錄文件中各 字符出現(xiàn)的頻率，當(dāng)編碼表 HC表構(gòu)建完成，此時(shí) w={3,9,14,3,1,2,17,5,5,13,2,6,20,9,8,5,12}。依次從 w中選擇權(quán)重最小并且雙親為 0的兩個(gè)結(jié)點(diǎn)，根據(jù)這兩個(gè)結(jié)點(diǎn)生成新的結(jié)點(diǎn)，新結(jié)點(diǎn)的權(quán)重為這兩個(gè)最小結(jié)點(diǎn)的和，新結(jié)點(diǎn)的左右子樹為這兩個(gè)結(jié)點(diǎn)在 w中的位置。根據(jù)表 1數(shù)據(jù)構(gòu)建赫夫曼