王　軍

（銅仁學(xué)院 信息工程學(xué)院，貴州 銅仁 554300 ）

動(dòng)態(tài)文本的解壓縮算法設(shè)計(jì)與實(shí)現(xiàn)

王軍

（銅仁學(xué)院 信息工程學(xué)院，貴州 銅仁 554300 ）

針對(duì)在文本解壓縮過程中對(duì)動(dòng)態(tài)數(shù)據(jù)進(jìn)行權(quán)重統(tǒng)計(jì)較為困難這一問題，提出了一種采用三叉鏈表的解壓縮算法。首先采用鏈表對(duì)動(dòng)態(tài)文本中的不同字符進(jìn)行統(tǒng)計(jì)，得到相應(yīng)字符的權(quán)重；在此基礎(chǔ)上，再利用三叉鏈表構(gòu)造赫夫曼樹并對(duì)其進(jìn)行赫夫曼編碼；最后采用位運(yùn)算對(duì)赫夫曼編碼進(jìn)行無損的數(shù)據(jù)壓縮和解壓。實(shí)驗(yàn)表明，該算法運(yùn)行效率高，實(shí)現(xiàn)簡單，具有較高的應(yīng)用價(jià)值。

文本；動(dòng)態(tài)數(shù)據(jù)；三叉樹；解壓縮

1.引言

作為一種可變字長編碼方式，赫夫曼編碼可對(duì)文本數(shù)據(jù)進(jìn)行壓縮和解壓。然而構(gòu)造赫夫曼樹的權(quán)重是已知的，如何對(duì)動(dòng)態(tài)數(shù)據(jù)進(jìn)行權(quán)重的統(tǒng)計(jì)是解決文本壓縮和解壓的關(guān)鍵問題。眾所周知，赫夫曼編碼是最優(yōu)的無損編碼。對(duì)此，文獻(xiàn)［1］介紹了動(dòng)態(tài)字符權(quán)重的統(tǒng)計(jì)方法并且證明了赫夫曼編碼的帶權(quán)路徑長度是最短的，利用它對(duì)數(shù)據(jù)進(jìn)行壓縮的效率是很高的。但該方法并未提出如何統(tǒng)計(jì)漢字的權(quán)重。因?yàn)橐粋€(gè)漢字在內(nèi)存中占兩個(gè)字符，對(duì)漢字的統(tǒng)計(jì)比較困難。文獻(xiàn)［2-4］中赫夫曼樹的邏輯結(jié)構(gòu)是用三叉鏈表來實(shí)現(xiàn)，而赫夫曼樹的存儲(chǔ)結(jié)構(gòu)又是用順序結(jié)構(gòu)來實(shí)現(xiàn)的。為便于理解，在本文中我們采用單鏈表實(shí)現(xiàn)權(quán)重的統(tǒng)計(jì)，用三叉鏈表作為赫夫曼樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。在上述基礎(chǔ)上，根據(jù)文獻(xiàn)［2-4］的分析，我們進(jìn)一步實(shí)現(xiàn)了針對(duì)動(dòng)態(tài)文本（包括漢字）的赫夫曼編碼，最終達(dá)到了實(shí)現(xiàn)無損解壓縮的目的。

2.解縮算法的設(shè)計(jì)思路

2.1.采用單鏈表實(shí)現(xiàn)對(duì)文本中的字符進(jìn)行統(tǒng)計(jì)

（1）設(shè)計(jì)單鏈表：如圖1所示。

圖1　統(tǒng)計(jì)字符權(quán)值

在圖1中，h指針指向的結(jié)點(diǎn)為頭結(jié)點(diǎn)，當(dāng)沒有數(shù)據(jù)進(jìn)行統(tǒng)計(jì)時(shí)，h-＞next域?yàn)榭铡＿@就是單鏈表的初始狀態(tài)。結(jié)點(diǎn)中的n數(shù)據(jù)域是用來統(tǒng)計(jì)data域中字符的個(gè)數(shù)，data域用來存放字符，不同結(jié)點(diǎn)的data域的字符是不同的。Next域是用來存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址。文本串中的每一個(gè)字符從上到下與單鏈表中的data域中的字符進(jìn)行比較，若與某個(gè)結(jié)點(diǎn)的data域的字符相同，則該結(jié)點(diǎn)的n域加1，該字符統(tǒng)計(jì)完成，接著統(tǒng)計(jì)文本串中的下一個(gè)字符。若單鏈表中的所有結(jié)點(diǎn)的data域中都不與正在統(tǒng)計(jì)的字符相同，則在最后一個(gè)結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)，新結(jié)點(diǎn)的data域就是該字符，next域?yàn)榭眨琻域?yàn)?。重復(fù)上述操作，直到文本串中的所有字符統(tǒng)計(jì)完成為止。

（2）字符的統(tǒng)計(jì)：關(guān)鍵是結(jié)點(diǎn)中data域的設(shè)計(jì)，data域的結(jié)構(gòu)設(shè)計(jì)為圖2所示。

圖2　data域的結(jié)構(gòu)

圖2中ch0，ch1，ch2都是字符型變量，在讀取文本數(shù)據(jù)時(shí)必須按字節(jié)讀取。若正在統(tǒng)計(jì)的數(shù)據(jù)的ASCII值大于0，說明該字符是英文字符，則字符存入在data域的ch0中；若正在統(tǒng)計(jì)的數(shù)據(jù)的ASCII小于0，說明所統(tǒng)計(jì)的字符為漢字或者是中文的標(biāo)點(diǎn)符號(hào)，這時(shí)連續(xù)讀兩次，第一次讀的字節(jié)存入在data 的ch1中，第二次讀的字節(jié)存入data的ch2中，由ch1、ch2兩個(gè)字節(jié)存放一個(gè)漢字。同樣在進(jìn)行數(shù)據(jù)統(tǒng)計(jì)時(shí)，若正在統(tǒng)計(jì)的數(shù)據(jù)的 ASCII大于 0，則與data域中的ch0比較，反之則與data域中的ch1，ch2比較。這是統(tǒng)計(jì)漢字的關(guān)鍵因素，也是文本壓縮統(tǒng)計(jì)權(quán)重的核心問題。

（3）收集每個(gè)數(shù)據(jù)的權(quán)重：從頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始，分別從每一個(gè)結(jié)點(diǎn)中的data域和n域讀取相應(yīng)的數(shù)據(jù)，n域的值就是相應(yīng)結(jié)點(diǎn)的data域中的數(shù)據(jù)的權(quán)重，直到單鏈表中的所有結(jié)點(diǎn)收集完成為止。這樣文本中的所有不同字符的權(quán)重都統(tǒng)計(jì)完成。

2.2.三叉鏈表的生成

（1）將統(tǒng)計(jì)的字符有權(quán)重生成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，如圖3所示，其中D域用來存放統(tǒng)計(jì)的字符，W 域用來存放對(duì)應(yīng)字符的權(quán)重，指針域又包含四個(gè)指針，一個(gè)指針指向后繼，一個(gè)指針雙親，一個(gè)指針指向左孩子，一個(gè)指針指向右孩子。

（2）按照赫夫曼樹的構(gòu)造方法［2］，在H單鏈表中查找當(dāng)前權(quán)重最小的兩個(gè)結(jié)點(diǎn)，將這兩個(gè)結(jié)點(diǎn)作為一個(gè)新結(jié)點(diǎn)的左、右孩子，新結(jié)點(diǎn)的權(quán)重為這兩個(gè)結(jié)點(diǎn)的權(quán)重的和。這兩個(gè)結(jié)點(diǎn)的雙親指針分別指向新結(jié)點(diǎn)，從單鏈表中刪除這兩結(jié)點(diǎn)，把新結(jié)點(diǎn)插入到H鏈表的表頭后面，重復(fù)上述操作，直到H鏈表為單鏈表只有一個(gè)結(jié)點(diǎn)為止。此時(shí)，H鏈表中的第一個(gè)結(jié)點(diǎn)就是三叉鏈表的根結(jié)點(diǎn)。

圖3　三叉鏈表

2.3.赫夫曼編碼和壓縮

為了能快速找到三叉鏈表中的每一個(gè)結(jié)點(diǎn)，用一個(gè)向量來存放三叉鏈表的葉子結(jié)點(diǎn)的地址。在2.2中的單鏈表生成時(shí)把每個(gè)結(jié)點(diǎn)的地址存放在一維向量中，從一維向量中分別取出每個(gè)葉子結(jié)點(diǎn)的地址，從葉子到根進(jìn)行遍歷，按規(guī)定的順序得到相應(yīng)的赫夫曼編碼，再設(shè)計(jì)位運(yùn)算算法把每個(gè)編碼按位壓縮，直到文本中的所有字符都按位壓縮得到一個(gè)新的文件，從而完成了數(shù)據(jù)壓縮過程。

2.4.解壓縮方法的設(shè)計(jì)

解壓算法可通過對(duì)上述位運(yùn)算進(jìn)行逆操作實(shí)現(xiàn)。從壓縮文件中順序讀取二進(jìn)制位，按規(guī)定的順序從根到葉子進(jìn)行搜索，搜索過程中左孩子或右孩子為空時(shí)的結(jié)點(diǎn)的D域的字符就是解壓后需要的字符，再輸出該字符。反復(fù)從根到葉子進(jìn)行搜索，直到把壓縮文件的每一個(gè)二進(jìn)制位譯碼完成為止，從而完成了解壓操作。

3.數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

4.算法的實(shí)現(xiàn)流程

本文算法的的N-S流程圖如圖4所示。在該圖中詳細(xì)描述了數(shù)據(jù)壓縮和解壓的過程。

此外，各函數(shù)的原型如下：

（1）void Huffman：：InputFile（）//向文件中輸入文本文件

（2）void Huffman：：OutputFile（）//輸出文件

（3）void Huffman：：CountCharNum（）//創(chuàng)建動(dòng)態(tài)鏈表來統(tǒng)計(jì)字符的權(quán)重

（4）void Huffman：：CreateTree（）//利用單鏈表創(chuàng)建三叉鏈表

（5）void Huffman：：code（）//利用三叉鏈表對(duì)各種字符進(jìn)行赫夫曼編碼

（6）void Huffman：：yasuo（）//壓縮編碼

（7）void Huffman：：jieya（）//解壓編碼

本文方法已在VC6.0中編譯運(yùn)行（源代碼見附件），經(jīng)過實(shí)際運(yùn)行，可實(shí)現(xiàn)對(duì)動(dòng)態(tài)文本的無損解壓縮操作。

圖4　算法的N-S流程圖

5.總結(jié)

本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)針對(duì)動(dòng)態(tài)文本的解壓縮算法。該算法具有如下特點(diǎn)：（1）利用文件指針對(duì)源文件和壓縮文件的讀寫［5］，避免了反復(fù)輸入數(shù)據(jù)；（2）算法中所使用的數(shù)據(jù)結(jié)構(gòu)全是鏈表或動(dòng)態(tài)數(shù)組，保證了文本文件的長度不受限制；（3）通過位運(yùn)算得到二進(jìn)制串的長度正好是赫夫曼編碼中的帶權(quán)路徑長度，而且該編碼長度是最短的，所需要的字節(jié)數(shù)最少，達(dá)到了高效壓縮的目的。本算法的不足之處在于，目前只能對(duì)文本進(jìn)行解壓縮，無法對(duì)圖形、圖片、視頻、聲音、動(dòng)畫等數(shù)據(jù)進(jìn)行處理，下一步擬對(duì)這個(gè)問題展開研究。

［1］王軍.基于赫夫曼編碼的數(shù)據(jù)壓縮［J］.中國教育教學(xué)雜志，2006，18（11）：16765-16767.

［2］嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社，2010.

［3］陳寶平.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社，2012.

［4］鄧又明.數(shù)據(jù)結(jié)構(gòu)［M］.北京：地質(zhì)出版社，2007.

［5］譚浩強(qiáng).C程序設(shè)計(jì)（第三版）［M］.北京：清華大學(xué)出版社，2014.

［6］鄭麗.C++語言程序設(shè)計(jì)（第四版）［M］.北京：清華大學(xué)出版社，2010.

The Design and Implementation of Compression and Decompression Method for Dynamic Text

WANG Jun
（School of Information Engineering，Tongren University，Tongren，Guizhou 554300，China ）

Due to the difficulty of weight statistic for dynamical data in the compression and decompression process，a compression and decompression method based on trifurcate chain table is proposed in this paper. First，in order to achieve the weight of each character，each different character in dynamical text file was accounted by employing chain table. Then the Huffman tree was constructed and Huffman coding was completed by using trifurcate chain table. Finally，the lossless compression and decompression for Huffman coding was completed by using bit- operation. Experience results reveal that the proposed method has a high application value for the advantages of high efficiency and realized easily in practice.

Text；dynamical data；ternary tree；compression and decompression

TP311.51

A

1673-9639 （2015） 04-0117-03

（責(zé)任編輯 毛志）（責(zé)任校對(duì) 徐松金）（英文編輯 田興斌）

2015-06-05

本文系貴州省教育廳教學(xué)質(zhì)量與教學(xué)改革工程項(xiàng)目（黔高教發(fā)［2013］446-9號(hào)）研究成果。

王軍（1967-），男，貴州德江人，副教授，研究方向：算法與計(jì)算機(jī)應(yīng)用技術(shù)。