基于Ｈｕｆｆｍａｎ編碼的壓縮技術的Ｊａｖａ實現

摘要：當前，廣泛采用的無損壓縮技術主要有2種，一種是短語式壓縮，另一種是編碼式壓縮。本文介紹采用java編程語言利用Huffman算法實現文件的壓縮功能，是實現的編碼式壓縮技術。

關鍵詞：壓縮技術；霍夫曼編碼；java

中圖分類號：TP393.09文獻標識碼：A文章編號：1009-3044(2008)11-20349-02

在某一個特定的文件系統中，某些字符可能會累計重復出現多次。編碼壓縮技術采用的原理就是統計這些字符出現的頻率，并根據頻率的高低對該字符進行編碼。這樣，處理全部信息的總碼長一定小于實際信息的符號長度，從而達到壓縮的目的。

本文用java實現的Huffman編碼壓縮技術是實現的編碼式壓縮技術。

1 Huffman編碼原理

霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統計編碼。屬于無損壓縮編碼。 霍夫曼編碼的碼長是變化的，對于出現頻率高的信息，編碼的長度較短；而對于出現頻率低的信息，編碼長度較長。

構造Huffman編碼的可以先將原始數據構造成一棵帶權值的Huffman樹。步驟如下：

（1）將信號源的符號按照出現概率遞減的順序排列。

（2）將兩個最小出現概率進行合并相加，得到的結果作為新符號的出現概率。

（3）重復進行步驟1和2直到概率相加的結果等于1為止。

（4）在合并運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。

（5）記錄下概率為1處到當前信號源符號之間的0，l序列，從而得到每個符號的編碼。

例如電文“ABACCDA”，有4種字符。可以用兩位二進制代碼：00，01，10，11分別表示A，B，C，D。譯碼為”00010010101100”。這樣的二進制串長度為16位。比原始的字符串長度8*8=64遠小。若采用Huffman編碼，則得：A:1; B: 000 C:01；D:001。譯碼字符串為：1000101010011。長度為13位，比16又小。對于應用文檔來說，一般會有大量詞匯重復出現，這樣兩者之間的差距也隨著文件的大小與詞匯重復出現的頻率而越來越高。

2 用java實現huffman壓縮算法的程序流程

3 程序實現

根據上面的流程以及huffman算法的原理，有如下的程序類組織結構：

3.1 程序相關類

Frame類：框架類，用于實現程序的界面，其中還包括文件的讀入，統計字符的頻率，各字符按頻率排序等函數

HuffmanNode類：利用Huffman算法的特點，進行Huffman數據結構定義，如圖2。

BuildHuffman類：初始化Huffman樹，并得到編碼。其中包括生成Huffman樹結構的函數（具體實現參看附程序），編碼函數，寫二進制文件函數，解碼函數等，結構參看圖3。

3.1.1 在Frame類中，可能會遇到的問題

在圖1的步驟1中（也就是在統計字符串頻率時），對于簡單的英文字母與數字字符來說，沒有什么難度。而對于統計中文字符或其他一些由2個字節構成的字符時，可能會遇到某些問題。因為在對文件進行遍歷統計頻率時，需要對讀入字符的步長加以控制。如果是單字節的字母，則步長為1，而如果是2個字節的字符，步長就需要相應的改為2。這樣，就存在一個步長控制問題了。根據目前國際通用的Unicode代碼表示的漢字存儲區位，位于4E00~9FFF的為中日韓文字，其他雙字節字符也有相應固定的區位。有這樣的unicode編碼條件，問題就可能解決了：在讀入字符時，只需要判斷讀入的字符是否是位于雙字節字符的存儲區中。而對于java1.5以上的版本中，character類中提供了isHighSurrogate函數。該函數能判斷能判斷所讀入的字符是否是雙字節字符的前半部分。這樣就能有效解決讀入字符步長控制問題。從而正確統計各種類型的字符出現頻率（代碼可以見附表）。

3.1.2 構造HuffmanNode類

HuffmanNode是一個定義的典型的Huffman型的數據結構。具體形式如圖2。

圖2就是即將構造的Huffman結構。接下來需要將按頻率已經排好序的各字符初始化成該類的實例（具體方法參見上述1中的原理與附錄中的程序片段），構造一棵帶有各字符符號及出現頻率的Huffman樹。這樣，從樹根開始遍歷各個葉子結點。按照每經歷一次左孩子取0，經歷一次右孩子取1的方法，得到各個葉子接點的Huffman編碼。并將該編碼存入該類實例的變量：bh中，以備解碼時或其他需要（編碼函數見附錄的Encode函數）。

3.1.3 BuildHuffman類

上面生成Huffman樹對于本程序來說是關鍵的一步。現在假設已經獲得各字符的Huffman編碼，并將待壓縮文件所有字符都化為了“01”類型的Huffman編碼并存入變量之中了。接下來的工作就是將寫編碼了。需要注意的是在寫入文件的編碼時，需要寫入二進制代碼。比如某個字符“A”對應的編碼是“001”。如果直接寫入字符類型的“001”，這不但沒有起到壓縮的效果，反而比原字符所占內存增加了2倍。所以必須寫入二進制類型的“001”。此時，問題出現了。大家知道，1.6及以下的java版本并不能直接將“001”轉化成簡單的“001”二進制序列。那么，采取什么樣有效的措施才能達到壓縮的效果呢。其實，java中DataOutputStream類中的write函數，可以寫入byte類型的數據。這樣，解決問題的方法就在于將字符型的“01”序列轉化為Byte型的數據了。有了這個思想，我們可以將帶壓縮的編碼以8位為步長，將其對應轉化為byte型的數據，存入一個byte的數組中去。這樣，每位8字節的“01”序列就壓縮成為了最多8位的長度了，從而間接實現了壓縮的目的。這樣做，在解壓的時候，需要重新將這些byte數還原成01序列，然后再將01序列去與對應的Huffman樹去匹配，還原得到相應的字符。

4 壓縮效率分析

在程序運行過程中，對系統資源的大量占用主要在讀/寫文本以及程序中其他一些不超過2層的循環語句的使用。系統執行時間在程序結構上應小于為O(N2) 其中N是待壓縮文件中字符的個數，但實際上，寫文件的時間耗費較大。經過壓縮的文件，在重復量不同的情況下，平均水平超過50%。對于文件中重復字符較多的文件，壓縮效率明顯較好。據多次統計：文件所占空間為原文件的25%左右。而對于重復量較小的文件，壓縮效果不太明顯，但也能達到原文件的60%左右。

5 部分java源程序

6 結束語

壓縮技術作為當前網絡傳輸與存儲的一種必要的數據處理技術現在已經比較成熟，而本文所采用的Huffman算法實現的編碼壓縮技術也是部分壓縮工具所采用的算法。本文從java編程實際出發，提出了一些可能遇到的問題與解決方案。其實，如果做進一步拓展，我們還可以將出現頻率較高的部分詞匯進行編碼，這樣壓縮的效率將進一步提高。但可以肯定的是，程序運行的時間復雜度和空間復雜度也會相應提高。

參考文獻：

[1] Thomas H.Cormen ，INTRODUCTOIN TO ALGORITHMS[M]，北京:高等教育出版，2006.

[2] 鄭麗，王言行，馬素霞. Java語言程序設計[M]，北京：清華大學出版社 ，2006.

[3] 嚴蔚敏 吳偉民，數據結構（C語言版），人民郵電出版社 2000.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文