原以為哈夫曼樹、哈夫曼編碼很難，結(jié)果……

taotao_2016 2021-08-27

展開全文

來自公眾號：bigsai

哈夫曼樹介紹

大家好，我是bigsai。原以為哈夫曼樹、哈夫曼編碼很難，結(jié)果它很簡單啊老鐵們！

哈夫曼樹、哈夫曼編碼很多人可能聽過，但是可能并沒有認(rèn)真學(xué)習(xí)了解，今天這篇就比較詳細(xì)的講一下哈夫曼樹。

首先哈夫曼樹是什么？

哈夫曼樹的定義：給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)，哈夫曼樹是帶權(quán)路徑長度最短的樹。權(quán)值較大的結(jié)點離根較近。

那這個樹長啥樣子呢？例如開始2，3，6，8，9權(quán)值節(jié)點構(gòu)成的哈夫曼樹是這樣的：

從定義和圖上你也可以發(fā)現(xiàn)下面的規(guī)律：

初始節(jié)點都在樹的葉子節(jié)點上
權(quán)值大的節(jié)點離根更近
每個非葉子節(jié)點都有兩個孩子(因為我們自下向上構(gòu)造，兩個孩子構(gòu)成一個新樹的根節(jié)點)

你可能會好奇這么一個哈夫曼樹是怎么構(gòu)造的，其實它是按照一個貪心思想和規(guī)則構(gòu)造，而構(gòu)造出來的這個樹的權(quán)值最小。這個規(guī)則下面會具體講解。

哈夫曼樹非常重要的一點：WPL(樹的所有葉結(jié)點的帶權(quán)路徑長度之和)。至于為什么按照哈夫曼樹方法構(gòu)造得到的權(quán)重最小,這里不進(jìn)行證明,但是你從局部來看(三個節(jié)點)也要權(quán)值大的在上一層WPL才更低。

WPL計算方法: WPL=求和(Wi * Li)其中Wi是第i個節(jié)點的權(quán)值(value)。Li是第i個節(jié)點的長(深)度.

例如上面 2，3，6，8，9權(quán)值節(jié)點構(gòu)成的哈夫曼樹的WPL計算為(設(shè)根為第0層)：

比如上述哈夫曼樹的WPL為：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61.

既然了解了哈夫曼樹的一些概念和WPL的計算方式，下面看看哈夫曼樹的具體構(gòu)造方式吧！

哈夫曼樹構(gòu)造

初始給一個森林有n個節(jié)點。我們主要使用貪心的思想來完成哈夫曼樹的構(gòu)造：

在n個節(jié)點找到兩個最小權(quán)值節(jié)點(根)，兩個為葉子結(jié)構(gòu)構(gòu)建一棵新樹(根節(jié)點權(quán)值為左右孩子權(quán)值和)
先刪掉兩個最小節(jié)點(n-2)個，然后加入構(gòu)建的新節(jié)點(n-1)個
重復(fù)上面操作，一直到所有節(jié)點都被處理

在具體實現(xiàn)上，找到最小兩個節(jié)點需要排序操作，我們來看看2，6，8，9，3權(quán)值節(jié)點構(gòu)成哈夫曼樹的過程。

初始時候各個節(jié)點獨立，先將其排序(這里使用優(yōu)先隊列)，然后選兩個最小節(jié)點(拋出)生成一個新的節(jié)點，再將其加入優(yōu)先隊列中，此次操作完成后優(yōu)先隊列中有5，6，8，9節(jié)點

重復(fù)上面操作，這次結(jié)束隊列中有11，8，9節(jié)點(排序后8，9，11)

否則繼續(xù)加入隊列進(jìn)行排序。重復(fù)上述操作，直到隊列為空。

在計算帶權(quán)路徑長度WPL的時候，需要重新計算高度(從下往上)，因為哈夫曼樹是從下往上構(gòu)造的，并沒有以常量維護(hù)高度，可以構(gòu)造好然后計算高度。

具體代碼實現(xiàn)(僅供參考)

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class HuffmanTree {    
    public static class node
    {
        int value;
        node left;
        node right;
        int deep;//記錄深度
        public node(int value) {
            this.value=value;
            this.deep=0;
        }
        public node(node n1, node n2, int value) {
            this.left=n1;
            this.right=n2;
            this.value=value;
        }
    }
    private node root;//最后生成的根節(jié)點
    List<node>nodes;
    public HuffmanTree() {
        this.nodes=null;
    }
    public HuffmanTree(List<node>nodes)
    {
        this.nodes=nodes;
    }
    public void createTree() {
       Queue<node>q1=new PriorityQueue<node>(new Comparator<node>() {
      public int compare(node o1, node o2) {
        return o1.value-o2.value;
      }});
       q1.addAll(nodes);
       while(!q1.isEmpty()){
           node n1=q1.poll();
           node n2=q1.poll();
          node parent=new node(n1,n2,n1.value+n2.value);
          if(q1.isEmpty()){
              root=parent;return;
          }
          q1.add(parent);
       }
    }
    public int getweight() {
        Queue<node>q1=new ArrayDeque<node>();
        q1.add(root);
        int weight=0;
        while (!q1.isEmpty()) {
            node va=q1.poll();
            if(va.left!=null){
                va.left.deep=va.deep+1;va.right.deep=va.deep+1;
                q1.add(va.left);q1.add(va.right);
            }
            else {
                weight+=va.deep*va.value;
            }
        }
        return weight;
    }
    public static void main(String[] args) {
        List<node>list=new ArrayList<node>();
        list.add(new node(2));
        list.add(new node(3));
        list.add(new node(6));
        list.add(new node(8));list.add(new node(9));
        HuffmanTree tree=new HuffmanTree();
        tree.nodes=list;
        tree.createTree();
        System.out.println(tree.getweight());
    }
}

輸出結(jié)果:

61

哈夫曼編碼

除了哈夫曼樹你聽過，哈夫曼編碼你可能也聽過，但是不一定了解它是個什么玩意兒，哈夫曼編碼其實就是哈夫曼樹的一個非常重要的應(yīng)用，在這里就簡單介紹原理并不詳細(xì)實現(xiàn)了。

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

哈夫曼編碼的目的是為了減少存儲體積，以一個連續(xù)的字符串為例，拋開編程語言中實際存儲，就拿

aaaaaaaaaabbbbbcccdde

這個字符串來說，在計算機(jī)中如果每個字符都是定長存儲(假設(shè)長為4的二進(jìn)制存儲)，計算機(jī)只知道0和1的二進(jìn)制，假設(shè)

a:0001
b:0010
c:0011
d:0100
e:0101

那么上面字符串可以用二進(jìn)制存儲是這樣的

000100010001000100010001……0101

如果每個字符編碼等長，那么就沒有存儲空間優(yōu)化可言，都是單個字符長度 * 字符個數(shù)。但是如果每個字符編碼不等長，那么設(shè)計的開放性就很強(qiáng)了。

比如一個字符串aaaaabb

如果設(shè)計a為01，b設(shè)計為1。那么二進(jìn)制就為：010101010111

如果設(shè)計a為1，b設(shè)計為01。那么二進(jìn)制就為：111110101

如果設(shè)計a為1，b設(shè)計為0。那么二進(jìn)制就為：1111100

你看，在計算機(jī)的01二進(jìn)制世界中，明顯第二種比第一種優(yōu)先，第三種又比第二種優(yōu)先。所以，設(shè)計編碼要考慮讓出現(xiàn)多的盡量更短，出現(xiàn)少的稍微長點沒關(guān)系。

但是，你需要考慮的一個問題是，二進(jìn)制開始0，1，01，10，11這個順序，如果來了001它到底是0，0，1還是0，01呢？所以編碼不等長的時候你要考慮到這個編碼要有唯一性不能出現(xiàn)歧義。這個怎么搞呢？

簡單啊，計算機(jī)只知道01二進(jìn)制，而二叉樹剛好有左右兩個節(jié)點，至于一個字符它如果是對應(yīng)葉子節(jié)點，那么就可以直接確定，也就是這個數(shù)值如果映射成一個二叉樹字符不能存在非葉子節(jié)點上。

所以，哈夫曼編碼具體流程就很清晰了，先統(tǒng)計字符出現(xiàn)的次數(shù)，然后將這個次數(shù)當(dāng)成權(quán)值按照上面介紹的方法構(gòu)造一棵哈夫曼樹，然后樹的根不存，往左為0往右為1每個葉子節(jié)點得到的二進(jìn)制數(shù)字就是它的編碼，這樣頻率高的字符在上面更短在整個二進(jìn)制存儲中也更節(jié)省空間。