動態文本的解壓縮算法設計與實現

王　軍

（銅仁學院 信息工程學院，貴州 銅仁 554300 ）

動態文本的解壓縮算法設計與實現

王軍

（銅仁學院 信息工程學院，貴州 銅仁 554300 ）

針對在文本解壓縮過程中對動態數據進行權重統計較為困難這一問題，提出了一種采用三叉鏈表的解壓縮算法。首先采用鏈表對動態文本中的不同字符進行統計，得到相應字符的權重；在此基礎上，再利用三叉鏈表構造赫夫曼樹并對其進行赫夫曼編碼；最后采用位運算對赫夫曼編碼進行無損的數據壓縮和解壓。實驗表明，該算法運行效率高，實現簡單，具有較高的應用價值。

文本；動態數據；三叉樹；解壓縮

1.引言

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

2.解縮算法的設計思路

2.1.采用單鏈表實現對文本中的字符進行統計

（1）設計單鏈表：如圖1所示。

圖1　統計字符權值

在圖1中，h指針指向的結點為頭結點，當沒有數據進行統計時，h-＞next域為空。這就是單鏈表的初始狀態。結點中的n數據域是用來統計data域中字符的個數，data域用來存放字符，不同結點的data域的字符是不同的。Next域是用來存儲下一個結點的地址。文本串中的每一個字符從上到下與單鏈表中的data域中的字符進行比較，若與某個結點的data域的字符相同，則該結點的n域加1，該字符統計完成，接著統計文本串中的下一個字符。若單鏈表中的所有結點的data域中都不與正在統計的字符相同，則在最后一個結點的后面插入一個新結點，新結點的data域就是該字符，next域為空，n域為1。重復上述操作，直到文本串中的所有字符統計完成為止。

（2）字符的統計：關鍵是結點中data域的設計，data域的結構設計為圖2所示。

圖2　data域的結構

圖2中ch0，ch1，ch2都是字符型變量，在讀取文本數據時必須按字節讀取。若正在統計的數據的ASCII值大于0，說明該字符是英文字符，則字符存入在data域的ch0中；若正在統計的數據的ASCII小于0，說明所統計的字符為漢字或者是中文的標點符號，這時連續讀兩次，第一次讀的字節存入在data 的ch1中，第二次讀的字節存入data的ch2中，由ch1、ch2兩個字節存放一個漢字。同樣在進行數據統計時，若正在統計的數據的 ASCII大于 0，則與data域中的ch0比較，反之則與data域中的ch1，ch2比較。這是統計漢字的關鍵因素，也是文本壓縮統計權重的核心問題。

（3）收集每個數據的權重：從頭結點的下一個結點開始，分別從每一個結點中的data域和n域讀取相應的數據，n域的值就是相應結點的data域中的數據的權重，直到單鏈表中的所有結點收集完成為止。這樣文本中的所有不同字符的權重都統計完成。

2.2.三叉鏈表的生成

（1）將統計的字符有權重生成一個帶頭結點的單鏈表，如圖3所示，其中D域用來存放統計的字符，W 域用來存放對應字符的權重，指針域又包含四個指針，一個指針指向后繼，一個指針雙親，一個指針指向左孩子，一個指針指向右孩子。

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

圖3　三叉鏈表

2.3.赫夫曼編碼和壓縮

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

2.4.解壓縮方法的設計

解壓算法可通過對上述位運算進行逆操作實現。從壓縮文件中順序讀取二進制位，按規定的順序從根到葉子進行搜索，搜索過程中左孩子或右孩子為空時的結點的D域的字符就是解壓后需要的字符，再輸出該字符。反復從根到葉子進行搜索，直到把壓縮文件的每一個二進制位譯碼完成為止，從而完成了解壓操作。

3.數據結構的設計

4.算法的實現流程

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

此外，各函數的原型如下：

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

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

（3）void Huffman：：CountCharNum（）//創建動態鏈表來統計字符的權重

（4）void Huffman：：CreateTree（）//利用單鏈表創建三叉鏈表

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

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

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

本文方法已在VC6.0中編譯運行（源代碼見附件），經過實際運行，可實現對動態文本的無損解壓縮操作。

圖4　算法的N-S流程圖

5.總結

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

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

［2］嚴蔚敏.數據結構［M］.北京：清華大學出版社，2010.

［3］陳寶平.數據結構［M］.北京：清華大學出版社，2012.

［4］鄧又明.數據結構［M］.北京：地質出版社，2007.

［5］譚浩強.C程序設計（第三版）［M］.北京：清華大學出版社，2014.

［6］鄭麗.C++語言程序設計（第四版）［M］.北京：清華大學出版社，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

（責任編輯 毛志）（責任校對 徐松金）（英文編輯 田興斌）

2015-06-05

本文系貴州省教育廳教學質量與教學改革工程項目（黔高教發［2013］446-9號）研究成果。

王軍（1967-），男，貴州德江人，副教授，研究方向：算法與計算機應用技術。