對於我們的日常操作壓縮文件來說,通常都是將文件中的字符轉換成壓縮后的格式,但為什麼能夠解壓回來,那是因為壓縮后的數據形式總是和原字符唯一對應的。因為計算機總是以0/1保存文件,那編碼過程中也是將文件轉化成更小的0/1序列,起到壓縮的作用。比如:

對於一個字符a來說,計算機是用8bit來保存字符的,如果我們可以唯一用一個bit的0來表示這個a,那這一個字符就為計算機節省了7bit的空間。

哈夫曼樹唯一標識字符

在給定一些字符的時候,我們需要用二進制編碼f(x)表示字符x,且在識別的過程中不會產生衝突,那很容易理解的一點是對於任意f(a)來說絕對不會出現一個f(b)使得f(a)可以作為f(b)的前綴。

example:
a: 110表示
b: 1100表示
那麼對於一個壓縮后的編碼1101100來說當識別到110的時候,無法判斷這個是否已經是a了還是否繼續識別,因為是存在b的可能性的,這就是所謂的編碼衝突。

將這個放到樹上來理解,從根節點出發0表示向左子樹走,1表示向右子樹走,最後走到最低端的恭弘=叶 恭弘子節點就是對這個恭弘=叶 恭弘子節點字符對應的編碼。
按照上述,那麼在這個樹上一定不可能出現在朝一個恭弘=叶 恭弘子上的字符往下走的過程中遇到其他編碼的字符,因為這樣的結果一定會產生前綴。
所以這是哈夫曼樹的一個重要特性。

哈夫曼樹的基本原理

哈夫曼樹上每一個點都對應一個權值,這個權值希望的是最後編碼出來的結果盡可能用到的0/1數目少。那麼我們在這裏也就把權值理解成對於一個編碼字符串的每一個字符出現的個數,簡單理解就是出現越多的字符希望編碼結果盡可能短,那麼它總的結果就會盡可能短。

那麼根據哈夫曼樹的定義就是:
一棵二叉樹要使其WPL值最小,必須使權值越大的恭弘=叶 恭弘子結點越靠近根結點,而權值越小的恭弘=叶 恭弘子結點越遠離根結點。

哈夫曼根據這一點提出了一種構造最優二叉樹的方法,基本思想如下:

  • 根據給定的n個權值{w1 , w2 , w3 , … , wn},構造n棵只有根節點的二叉樹,令其權值為wi。
  • 在森林中選取兩棵根節點權值最小的樹作為左右子樹,構造一棵新的二叉樹,置新的二叉樹的權值為左右子樹的權值和。
  • 在森林中刪去這兩棵已被合併的樹,將新得到的二叉樹加入到森林中。
  • 重複以上兩步,直到最後森林中只含有一棵樹,那麼這棵樹就是哈夫曼樹。

下面用huffman算法構造一棵樹的過程實例:


Huffman算法

哈夫曼樹在編碼中的應用

在電文傳輸中,需要將電文中出現的每個字符進行二進制編碼。在設計編碼時需要遵守兩個原則:
(1)發送方傳輸的二進制編碼,到接收方解碼后必須具有唯一性,即解碼結果與發送方發送的電文完全一樣;
(2)發送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。

  1. 等長編碼
    這種編碼方式的特點是每個字符的編碼長度相同(編碼長度就是每個編碼所含的二進制位數)。假設字符集只含有4個字符A,B,C,D,用二進制兩位表示的編碼分別為00,01,10,11。若現在有一段電文為:ABACCDA,則應發送二進制序列:00010010101100,總長度為14位。當接收方接收到這段電文後,將按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性,但編碼長度並不是最短的。

  2. 不等長編碼
    在傳送電文時,為了使其二進制位數盡可能地少,可以將每個字符的編碼設計為不等長的,使用頻度較高的字符分配一個相對比較短的編碼,使用頻度較低的字符分配一個比較長的編碼。例如,可以為A,B,C,D四個字符分別分配0,00,1,01,並可將上述電文用二進制序列:000011010發送,其長度只有9個二進制位,但隨之帶來了一個問題,接收方接到這段電文後無法進行譯碼,因為無法斷定前面4個0是4個A,1個B、2個A,還是2個B,即譯碼不唯一,因此這種編碼方法不可使用。

因此,為了設計長短不等的編碼,以便減少電文的總長,還必須考慮編碼的唯一性,即在建立不等長編碼時必須使任何一個字符的編碼都不是另一個字符的前綴,這宗編碼稱為前綴編碼(prefix code)

(1)利用字符集中每個字符的使用頻率作為權值構造一個哈夫曼樹;
(2)從根結點開始,為到每個恭弘=叶 恭弘子結點路徑上的左分支賦予0,右分支賦予1,並從根到恭弘=叶 恭弘子方向形成該恭弘=叶 恭弘子結點的編碼

哈夫曼編碼的實現

下方的Java代碼實現當中用到了對自定義的HuffmanNode為了做到有序排列放到了HashSet容器中保存,要注意的一點是不能放到LinkedHashSet中,這個對象是根據存儲順序保存的。
因為這個順序和hash值有關,所以要自定義對象的hash值獲取函數,這下方的兩個函數都是定義在對象當中的。

不用到這個的話可以根據我內容中寫到的用普通的vector容器進行保存,當然vector的效率比set會慢很多。

//下方兩個函數是自定義對象保存在有序容器中所必須的
        public boolean equals(Object other){
            HuffmanNode obj = (HuffmanNode)other;
            if(obj.value != this.value || obj.left != this.left ||
                    obj.right != this.right || obj.ch != this.ch)
                return false;
            return true;
        }
//最後HashSet中是根據對象hashCode()得到的hash碼來排序
        public int hashCode(){
            return value;
        }
/**
 * Created by ganjun on 2017/5/26.
 */


import java.util.*;

public class Huffman {
    class HuffmanNode{
        public int value;
        public HuffmanNode left;
        public HuffmanNode right;
        char ch ;
        HuffmanNode(){
            this.value = 0;
            this.ch = '\0';
        }
        HuffmanNode(int value , char ch){
            this.value = value ;
            this.ch = ch ;
            left = null;
            right = null;
        }
        HuffmanNode(int value , HuffmanNode lf , HuffmanNode rg , char ch){
            this.value = value ;
            this.ch = ch ;
            left = lf;
            right = rg;
        }

        //下方兩個函數是自定義對象保存在有序容器中所必須的
        public boolean equals(Object other){
            HuffmanNode obj = (HuffmanNode)other;
            if(obj.value != this.value || obj.left != this.left ||
                    obj.right != this.right || obj.ch != this.ch)
                return false;
            return true;
        }
        //最後HashSet中是根據對象hashCode()得到的hash碼來排序
        public int hashCode(){
            return value;
        }
    }

    public int [] count = new int[256]; //計算每個字符出現的次數
    public String article;

    //用不同的容器保存節點,效果上一樣,用不同的方法計算,效率上會有差距
    public Vector<HuffmanNode> existConnectNodes = new Vector<HuffmanNode>(); //還未有父親連接的所有節點集合
    public Set<HuffmanNode> existConnectNodesSet = new HashSet<HuffmanNode>(); //還未有父親連接的所有節點集合

    public void calCharCounts(String str){
        for(int i=0 ; i<str.length() ; i++){
            count[str.charAt(i)] ++;
        }
        for(int i=0 ; i<256 ; i++){
            if(count[i]>0){
                existConnectNodes.add(new HuffmanNode(count[i] , (char)i));
                existConnectNodesSet.add(new HuffmanNode(count[i] , (char)i));
            }
        }
        System.out.println("當前字符出現對應的數量如下");
        Iterator<HuffmanNode> iter = existConnectNodesSet.iterator();
        while(iter.hasNext()){
            HuffmanNode obj = iter.next();
            System.out.println("字符"+obj.ch+"有"+obj.value+"個");
        }
    }

    //通過vector來保存哈夫曼樹的節點,返回哈夫曼樹的根節點
    public HuffmanNode generateTreeByVector(){
        while(existConnectNodes.size() > 1){
            //找到最小的前兩名的Huffman節點
            int minv = 0 , secMinv = 0;
            int minIndex = 0 , secMinIndex = 0;
            if(existConnectNodes.get(0).value > existConnectNodes.get(1).value){
                minv = existConnectNodes.get(1).value;
                secMinv = existConnectNodes.get(0).value;
                minIndex = 1 ;
                secMinIndex = 0;
            }
            else{
                minv = existConnectNodes.get(0).value;
                secMinv = existConnectNodes.get(1).value;
                minIndex = 0;
                secMinIndex = 1;
            }
            for (int i=2 ; i<existConnectNodes.size() ; i++){
                if(existConnectNodes.get(i).value < minv){
                    secMinv = minv;
                    secMinIndex = minIndex;
                    minv = existConnectNodes.get(i).value;
                    minIndex = i;
                }
                else if(existConnectNodes.get(i).value < secMinv){
                    secMinv = existConnectNodes.get(i).value;
                    secMinIndex = i;
                }
            }

            //形成新的節點
            HuffmanNode nodelf = existConnectNodes.get(minIndex);
            HuffmanNode noderg = existConnectNodes.get(secMinIndex);
            HuffmanNode unionNode = new HuffmanNode(
                    nodelf.value+noderg.value , nodelf , noderg , '\0');
            existConnectNodes.remove(nodelf);
            existConnectNodes.remove(noderg);
            existConnectNodes.add(unionNode);
        }
        //最後裏面就只剩下一個元素了
        return (HuffmanNode)(existConnectNodes.get(0));
    }

    //通過Set來保存哈夫曼樹的節點,返回哈夫曼樹的根節點
    public HuffmanNode generateTreeBySet(){
        while(existConnectNodesSet.size() > 1){
            //找到最小的前兩名的Huffman節點
            //形成新的節點
            Iterator<HuffmanNode> iter = existConnectNodesSet.iterator();
            HuffmanNode nodelf = iter.next();
            HuffmanNode noderg = iter.next();
            HuffmanNode unionNode = new HuffmanNode(
                    nodelf.value+noderg.value , nodelf , noderg , '\0');
            existConnectNodesSet.remove(nodelf);
            existConnectNodesSet.remove(noderg);
            existConnectNodesSet.add(unionNode);
        }
        //最後裏面就只剩下一個元素了
        Iterator<HuffmanNode> iter = existConnectNodesSet.iterator();
        return (HuffmanNode)(iter.next());
    }

    public void viewTree(HuffmanNode root , String code){
        if(root.ch != '\0'){
            System.out.println("字符"+root.ch+" --> "+code);
        }
        else{
            if(root.left != null)
                viewTree(root.left , code+"0");
            if(root.right != null)
                viewTree(root.right , code+"1");
        }
    }

    public static void main(String [] args){
        Huffman sol = new Huffman();
        sol.calCharCounts("512511344");
        HuffmanNode root = sol.generateTreeBySet();
        // HuffmanNode root = sol.generateTreeByVector(); //這種方法是通過Vector容器來保存的,原理都是一樣的
        System.out.println("最後編碼結果為");
        sol.viewTree(root , "");
    }
}
分享