Huffman編碼 是一種編碼方式,常用於無損壓縮。本文只介紹用Java語言來實現該編碼方式的算法和數據結構。
Huffman編碼的核心在於構建一顆最優化的二叉樹,首先要得到一個原數據編碼中的【編碼:頻率】的列表,然後根據列表構建二叉樹,最後對二叉樹編碼。
C++使用優先隊列來構建huffman樹[哈夫曼樹] http://www.linuxidc.com/Linux/2012-01/52790.htm
Huffman編碼實現(詳細實現) http://www.linuxidc.com/Linux/2012-01/51730.htm
Huffman編碼與解碼的實現 http://www.linuxidc.com/Linux/2014-08/105644.htm
第一步: 計算出每個詞(編碼)出現的頻次,並輸出到一個列表
例如字符串:"this is an example of a huffman tree", 它的二進制編碼是11101001101000110100111100111000001101001111001110000011000011101110100000110010111110001100001110110111100001101100110010110000011011111100110100000110000110000011010001110101110011011001101101101110000111011101000001110100111001011001011100101
英文字母的表示只需要一個byte, 所以我們每次取二進制中的一個byte,放入HashMap<Byte,Node<Byte,Integer>>, 其中Byte作為HashMap的key,它的Value是一個Node<Byte, Integer> 。Node保存了byte值和出現的頻次,將來用於構建Huffman樹。遍歷二進制編碼,最後輸出List<Node<Byte,Integer>> 。
代碼如下:
nodes包含每個字母出現的頻次:[o:1, l:1, u:1, r:1, p:1, x:1, n:2, m:2, h:2, i:2, t:2, s:2, f:3, e:4, a:4, :7]
第二步:構建最優二叉樹
根據優先隊列算法我們總是取隊列中weight(頻次)最小的兩個節點,把它們的weight相加得到一個新的節點放入隊列中,它們本身則作為新節點的左右子節點,構建結束時列表中剩余的唯一節點就是Huffman樹的root。
HuffmanTree<Byte, Integer> huffmanTree = new HuffmanTree<>(nodes.get(0));
第三步:給Huffman樹編碼
在第二步中構造完成了一顆尚未編碼的樹,編碼其實就是給每一個節點一個唯一的編碼,而且這個編碼不可能是其他節點編碼的前綴,根據Huffman編碼的算法要做到這樣很簡單: 初始root的編碼為空(長度為0),從root開始遍歷,左子節點編碼=父節點編碼+0,右子節點編碼=父節點編碼+1 。
遍歷輸出結果:[e:4:000,a:4:001,n:2:0100,m:2:0101,h:2:0110,i:2:0111,t:2:1000,s:2:1001,o:1:10100,l:1:10101,u:1:10110,r:1:10111,p:1:11000,x:1:11001,f:3:1101, :7:111]
完畢, 全部代碼下載:
------------------------------------------分割線------------------------------------------
免費下載地址在 http://linux.linuxidc.com/
用戶名與密碼都是www.linuxidc.com
具體下載目錄在 /2014年資料/8月/18日/Huffman編碼——Java實現
下載方法見 http://www.linuxidc.com/Linux/2013-07/87684.htm
------------------------------------------分割線------------------------------------------