java實(shí)現(xiàn)的哈夫曼編碼與解碼

　　摘要：哈夫曼編碼作為一種編碼方式，已經(jīng)在生活中得到了實(shí)際的運(yùn)用，下面我們以java實(shí)現(xiàn)的哈夫曼編碼與解碼為核心來講述它的編碼方式及程序等。

　　哈夫曼編碼定義

　　哈夫曼編碼（Huffman Coding），又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼（VLC）的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

　　哈夫曼編碼原理

　　設(shè)某信源產(chǎn)生有五種符號u1、u2、u3、u4和u5，對應(yīng)概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，將符號按照概率由大到小排隊，如圖所示。編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1。這里，我們選上支路為0，下支路為1。再將已編碼的兩支路的概率合并，并重新排隊。多次重復(fù)使用上述方法直至合并概率歸一時為止。從圖（a）和（b）可以看出，兩者雖平均碼長相等，但同一符號可以有不同的碼長，即編碼方法并不唯一，其原因是兩支路概率合并后重新排隊時，可能出現(xiàn)幾個支路概率相等，造成排隊方法不唯一。一般，若將新合并后的支路排到等概率的最上支路，將有利于縮短碼長方差，且編出的碼更接近于等長碼。這里圖（a）的編碼比（b）好。

　　赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。

　　實(shí)際應(yīng)用中，除采用定時清洗以消除誤差擴(kuò)散和采用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統(tǒng)計匹配，例如黑（1）、白（0）傳真信源的統(tǒng)計匹配，采用0和1不同長度游程組成擴(kuò)大的符號集合信源。游程，指相同碼元的長度（如二進(jìn)碼中連續(xù)的一串0或一串1的長度或個數(shù)）。按照CCITT標(biāo)準(zhǔn)，需要統(tǒng)計2×1728種游程（長度），這樣，實(shí)現(xiàn)時的存儲量太大。事實(shí)上長游程的概率很小，故CCITT還規(guī)定：若l表示游程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小于64的游程長度由主碼和基碼組成。而當(dāng)l為64的整數(shù)倍時，只用主碼的代碼，已不存在基碼的代碼。

　　長游程的主碼和基碼均用赫夫曼規(guī)則進(jìn)行編碼，這稱為修正赫夫曼碼，其結(jié)果有表可查。該方法已廣泛應(yīng)用于文件傳真機(jī)中。

　　Java實(shí)現(xiàn)哈夫曼編碼和解碼

　　將一個字符串進(jìn)行哈夫曼編碼；編碼過程中，會得到每個字符的編碼，通過已知的每個字符的編碼對之前的編碼進(jìn)行解碼。

　　分析：首先是哈夫曼編碼算法，引用李澤年寫的《多媒體技術(shù)教程》中對哈夫曼編碼算法的描述：

　　?Initialization： Put all symbols on a list sorted according to their frequency counts.

　　?Repeat until the list has only one symbol left：

　　–From the list pick two symbols with the lowest frequency counts. Form a Huffman subtree that has these two symbols as child nodes and create a parent node.

　　–Assign the sum of the children‘s frequency counts to the parent and insert it into the list such that the order is maintained.

　　–Delete the children from the list.

　　?Assign a code word for each leaf based on the path from the root.

　　我的代碼是基于這段算法描述實(shí)現(xiàn)的。實(shí)際上，我看的是中文版，但是沒有找到該書的中文電子版，只好把英文版粘過來了。不過，好在英文版的也不復(fù)雜。

　　接下來是解碼。雖然解碼過程很簡單，但是卻是本文存在的理由。我在網(wǎng)上看了一些文章，都忽略一個問題：編碼和解碼過程中都有的東西是什么？也就是，依靠什么東西來解碼？本文的答案是“每個字符的編碼”，它在編碼的過程中生成，和字符串編碼一起傳到解碼端用于解碼。你也可以說是“每個字符出現(xiàn)的次數(shù)”或者“哈夫曼樹”，不管是“每個字符出現(xiàn)的次數(shù)”還是“哈夫曼樹”，你都需要通過他們得到“每個字符的編碼”之后才能進(jìn)行解碼。

　　下面是Java代碼：

　?。踛ava］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　/**

　　* 哈夫曼樹的節(jié)點(diǎn)

　　* @author yuncong

　　*

　　*/

　　public class Node implements Comparable《Node》{

　　private Node leftChild = null;

　　private Data data = null;

　　private Node rightChild = null;

　　public Node getLeftChild（） {

　　return leftChild;

　　}

　　public void setLeftChild（Node leftChild） {

　　this.leftChild = leftChild;

　　}

　　public Data getData（） {

　　return data;

　　}

　　public void setData（Data data） {

　　this.data = data;

　　}

　　public Node getRightChild（） {

　　return rightChild;

　　}

　　public void setRightChild（Node rightChild） {

　　this.rightChild = rightChild;

　　}

　　@Override

　　public String toString（） {

　　return “Node ［leftChild=” + leftChild + “， data=” + data

　　+ “， rightChild=” + rightChild + “］”;

　　}

　　@Override

　　public int compareTo（Node o） {

　　return this.data.compareTo（o.getData（））;

　　}

　　}

　?。踛ava］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　/**

　　* Data用于存儲一個字符及其出現(xiàn)的次數(shù)

　　* @author yuncong

　　*

　　*/

　　public class Data implements Comparable《Data》{

　　// 字符

　　private char c = 0;

　　// 字符出現(xiàn)的次數(shù)

　　private int frequency = 0;

　　public char getC（） {

　　return c;

　　}

　　public void setC（char c） {

　　this.c = c;

　　}

　　public int getFrequency（） {

　　return frequency;

　　}

　　public void setFrequency（int frequency） {

　　this.frequency = frequency;

　　}

　　@Override

　　public String toString（） {

　　return “Data ［c=” + c + “， frequency=” + frequency + “］”;

　　}

　　@Override

　　public int compareTo（Data o） {

　　if （this.frequency 《 o.getFrequency（）） {

　　return -1;

　　} else if （this.frequency 》 o.getFrequency（）） {

　　return 1;

　　} else {

　　return 0;

　　}

　　}

　　}

　?。踛ava］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　import java.util.Map;

　　/**

　　* 對字符串編碼后的結(jié)果：包括編碼后的字符串和字符/編碼對

　　* @author yuncong

　　*

　　*/

　　public class EncodeResult {

　　// 字符串編碼后的結(jié)果

　　private String encode;

　　// 字符編碼對

　　private Map《Character， String》 letterCode;

　　public EncodeResult（String encode， Map《Character， String》 letterCode） {

　　super（）;

　　this.encode = encode;

　　this.letterCode = letterCode;

　　}

　　public String getEncode（） {

　　return encode;

　　}

　　public Map《Character， String》 getLetterCode（） {

　　return letterCode;

　　}

　　}

　?。踛ava］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　public interface HuffmanAlgorithm {

　　/**

　　* 編碼字符串。

　　* @param str 指定的需要編碼的字符串

　　* @return 編碼結(jié)果

　　*/

　　public EncodeResult encode（String str）;

　　/**

　　* 根據(jù)編碼結(jié)果返回原來的字符串。

　　* @param decodeResult 原來字符串的編碼結(jié)果。

　　* @return 解碼出來的字符串。

　　*/

　　public String decode（EncodeResult encodeResult）;

　　}

　?。踛ava］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　import java.util.ArrayList;

　　import java.util.HashMap;

　　import java.util.Map;

　　import java.util.Set;

　　import com.liyuncong.application.commontools.FileTools;

　　public abstract class HuffmanAlgorithmAbstract implements HuffmanAlgorithm {

　　@Override

　　public EncodeResult encode（String str） {

　　ArrayList《Node》 letterList = toList（str）;

　　Node rootNode = createTree（letterList）;

　　Map《Character， String》 letterCode = getLetterCode（rootNode）;

　　EncodeResult result = encode（letterCode， str）;

　　return result;

　　}

　　/**

　　* 把一個字符串轉(zhuǎn)化為節(jié)點(diǎn)列表

　　* @param letters

　　* @return

　　*/

　　private ArrayList《Node》 toList（String letters） {

　　ArrayList《Node》 letterList = new ArrayList《Node》（）;

　　Map《Character， Integer》 ci = new HashMap《Character， Integer》（）;

　　for （int i = 0; i 《 letters.length（）; i++） {

　　Character character = letters.charAt（i）;

　　if （！ci.keySet（）.contains（character）） {

　　ci.put（character， 1）;

　　} else {

　　Integer oldValue = ci.get（character）;

　　ci.put（character， oldValue + 1）;

　　}

　　}

　　Set《Character》 keys = ci.keySet（）;

　　for （Character key ： keys） {

　　Node node = new Node（）;

　　Data data = new Data（）;

　　data.setC（key）;

　　data.setFrequency（ci.get（key））;

　　node.setData（data）;

　　letterList.add（node）;

　　}

　　return letterList;

　　}

　　protected abstract Node createTree（ArrayList《Node》 letterList）;

　　/**

　　* 編碼字符串。

　　* @param letterCode 字符/編碼對集合。

　　* @param letters 指定的需要編碼的字符串。

　　* @return 編碼結(jié)果

　　*/

　　private EncodeResult encode（Map《Character， String》 letterCode， String letters） {

　　StringBuilder encode = new StringBuilder（）;

　　for （int i = 0， length = letters.length（）; i 《 length; i++） {

　　Character character = letters.charAt（i）;

　　encode.append（letterCode.get（character））;

　　}

　　EncodeResult result = new EncodeResult（encode.toString（）， letterCode）;

　　return result;

　　}

　　/**

　　* 獲得所有字符編碼對

　　*

　　* @param rootNode哈夫曼樹的根節(jié)點(diǎn)

　　* @return 所有字符編碼對

　　*/

　　private Map《Character， String》 getLetterCode（Node rootNode） {

　　Map《Character， String》 letterCode = new HashMap《Character， String》（）;

　　// 處理只有一個節(jié)點(diǎn)的情況

　　if （rootNode.getLeftChild（） == null && rootNode.getRightChild（） == null） {

　　letterCode.put（rootNode.getData（）.getC（）， “1”）;

　　return letterCode;

　　}

　　getLetterCode（rootNode， “”， letterCode）;

　　return letterCode;

　　}

　　/**

　　* 先序遍歷哈夫曼樹，獲得所有字符編碼對。

　　*

　　* @param rooNode 哈夫曼樹根結(jié)點(diǎn)

　　* @param suffix 編碼前綴，也就是編碼這個字符時，之前路徑上的所有編碼

　　* @param letterCode 用于保存字符編碼結(jié)果

　　*/

　　private void getLetterCode（Node rooNode， String suffix，

　　Map《Character， String》 letterCode） {

　　if （rooNode ！= null） {

　　if （rooNode.getLeftChild（） == null

　　&& rooNode.getRightChild（） == null） {

　　Character character = rooNode.getData（）.getC（）;

　　letterCode.put（character， suffix）;

　　}

　　getLetterCode（rooNode.getLeftChild（）， suffix + “0”， letterCode）;

　　getLetterCode（rooNode.getRightChild（）， suffix + “1”， letterCode）;

　　}

　　}

　　public String decode（EncodeResult decodeResult） {

　　// 解碼得到的字符串

　　StringBuffer decodeStr = new StringBuffer（）;

　　// 獲得解碼器

　　Map《String， Character》 decodeMap = getDecoder（decodeResult

　　.getLetterCode（））;

　　// 解碼器鍵集合

　　Set《String》 keys = decodeMap.keySet（）;

　　// 待解碼的（被編碼的）字符串

　　String encode = decodeResult.getEncode（）;

　　// 從最短的開始匹配之所以能夠成功，是因?yàn)楣蚵幋a的唯一前綴性質(zhì)

　　// 臨時的可能的鍵值

　　String temp = “”;

　　// 改變temp值大小的游標(biāo)

　　int i = 1;

　　while （encode.length（） 》 0） {

　　temp = encode.substring（0， i）;

　　if （keys.contains（temp）） {

　　Character character = decodeMap.get（temp）;

　　decodeStr.append（character）;

　　encode = encode.substring（i）;

　　i = 1;

　　} else {

　　i++;

　　}

　　}

　　return decodeStr.toString（）;

　　}

　　/**

　　* 獲得解碼器，也就是通過字母/編碼對得到編碼/字符對。

　　*

　　* @param letterCode

　　* @return

　　*/

　　private Map《String， Character》 getDecoder（Map《Character， String》 letterCode） {

　　Map《String， Character》 decodeMap = new HashMap《String， Character》（）;

　　Set《Character》 keys = letterCode.keySet（）;

　　for （Character key ： keys） {

　　String value = letterCode.get（key）;

　　decodeMap.put（value， key）;

　　}

　　return decodeMap;

　　}

　　}

　?。踛ava］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　import java.util.ArrayList;

　　import java.util.HashMap;

　　import java.util.Map;

　　import java.util.Set;

　　/**

　　* 算法實(shí)現(xiàn)參考《多媒體技術(shù)教程》

　　* @author yuncong

　　*

　　*/

　　public class HuffmanAlgorithmImpl1 extends HuffmanAlgorithmAbstract {

　　/*

　　* 創(chuàng)建哈夫曼樹； 丟失了letterList中的數(shù)據(jù)，深拷貝letterList是需要完善的地方

　　*/

　　@Override

　　protected Node createTree（ArrayList《Node》 letterList） {

　　init（letterList）;

　　while （letterList.size（） ！= 1） {

　　int size = letterList.size（）;

　　// 小的節(jié)點(diǎn)放在右邊（眼睛看到的左邊）

　　Node nodeLeft = letterList.get（size - 1）;

　　Node nodeRight = letterList.get（size - 2）;

　　Node nodeParent = new Node（）;

　　nodeParent.setLeftChild（nodeLeft）;

　　nodeParent.setRightChild（nodeRight）;

　　Data data = new Data（）;

　　data.setFrequency（nodeRight.getData（）.getFrequency（）

　　+ nodeLeft.getData（）.getFrequency（））;

　　nodeParent.setData（data）;

　　letterList.set（size - 2， nodeParent）;

　　letterList.remove（size - 1）;

　　sort（letterList）;

　　}

　　Node rootNode = letterList.get（0）;

　　return rootNode;

　　}

　　/**

　　* 初始化 讓節(jié)點(diǎn)列表有序

　　*/

　　private void init（ArrayList《Node》 letterList） {

　　sort（letterList）;

　　}

　　/**

　　* 冒泡排序，把小的放在最后

　　*/

　　private void sort（ArrayList《Node》 letterList） {

　　int size = letterList.size（）;

　　// 處理只有一個元素的情況，也就是說，不需要排序

　　if （size == 1） {

　　return;

　　}

　　for （int i = 0; i 《 size; i++） {

　　for （int j = 0; j 《 size - 1 - i; j++） {

　　if （letterList.get（j）.getData（）.getFrequency（） 《 letterList

　　.get（j + 1）.getData（）.getFrequency（）） {

　　Node tempNode = letterList.get（j）;

　　letterList.set（j， letterList.get（j + 1））;

　　letterList.set（j + 1， tempNode）;

　　}

　　}

　　}

　　}

　　}

　　［java］ view plain copypackage com.liyuncong.algorithms.algorithms_huffman;

　　import static org.junit.Assert.*;

　　import org.junit.Test;

　　public class HuffmanAlgorithmImpl1Test {

　　@Test

　　public void testEncodeString（） {

　　HuffmanAlgorithmImpl1 huffmanImpl1 = new HuffmanAlgorithmImpl1（）;

　　EncodeResult result = huffmanImpl1.encode（“abcdda”）;

　　System.out.println（result.getEncode（））;

　　}

　　@Test

　　public void testDecode（） {

　　HuffmanAlgorithmImpl1 huffmanImpl1 = new HuffmanAlgorithmImpl1（）;

　　EncodeResult result = huffmanImpl1.encode（“abcdda”）;

　　String decode = huffmanImpl1.decode（result）;

　　System.out.println（decode）;

　　}

　　}