原以為哈夫曼樹、哈夫曼編碼很難，結(jié)果……
哈夫曼樹介紹
大家好，我是bigsai。原以為哈夫曼樹、哈夫曼編碼很難，結(jié)果它很簡(jiǎn)單啊老鐵們!
哈夫曼樹、哈夫曼編碼很多人可能聽過，但是可能并沒有認(rèn)真學(xué)習(xí)了解，今天這篇就比較詳細(xì)的講一下哈夫曼樹。
首先哈夫曼樹是什么?
哈夫曼樹的定義：給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)，哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹。權(quán)值較大的結(jié)點(diǎn)離根較近。
那這個(gè)樹長(zhǎng)啥樣子呢?例如開始2，3，6，8，9權(quán)值節(jié)點(diǎn)構(gòu)成的哈夫曼樹是這樣的：
從定義和圖上你也可以發(fā)現(xiàn)下面的規(guī)律：
- 初始節(jié)點(diǎn)都在樹的葉子節(jié)點(diǎn)上
- 權(quán)值大的節(jié)點(diǎn)離根更近
- 每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)孩子(因?yàn)槲覀冏韵孪蛏蠘?gòu)造，兩個(gè)孩子構(gòu)成一個(gè)新樹的根節(jié)點(diǎn))
你可能會(huì)好奇這么一個(gè)哈夫曼樹是怎么構(gòu)造的，其實(shí)它是按照一個(gè)貪心思想和規(guī)則構(gòu)造，而構(gòu)造出來的這個(gè)樹的權(quán)值最小。這個(gè)規(guī)則下面會(huì)具體講解。
哈夫曼樹非常重要的一點(diǎn)：WPL(樹的所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和)。至于為什么按照哈夫曼樹方法構(gòu)造得到的權(quán)重最小,這里不進(jìn)行證明,但是你從局部來看(三個(gè)節(jié)點(diǎn))也要權(quán)值大的在上一層WPL才更低。
WPL計(jì)算方法: WPL=求和(Wi * Li)其中Wi是第i個(gè)節(jié)點(diǎn)的權(quán)值(value)。Li是第i個(gè)節(jié)點(diǎn)的長(zhǎng)(深)度.
例如上面 2，3，6，8，9權(quán)值節(jié)點(diǎn)構(gòu)成的哈夫曼樹的WPL計(jì)算為(設(shè)根為第0層)：
比如上述哈夫曼樹的WPL為：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61.
既然了解了哈夫曼樹的一些概念和WPL的計(jì)算方式，下面看看哈夫曼樹的具體構(gòu)造方式吧!
哈夫曼樹構(gòu)造
初始給一個(gè)森林有n個(gè)節(jié)點(diǎn)。我們主要使用貪心的思想來完成哈夫曼樹的構(gòu)造：
- 在n個(gè)節(jié)點(diǎn)找到兩個(gè)最小權(quán)值節(jié)點(diǎn)(根)，兩個(gè)為葉子結(jié)構(gòu)構(gòu)建一棵新樹(根節(jié)點(diǎn)權(quán)值為左右孩子權(quán)值和)
- 先刪掉兩個(gè)最小節(jié)點(diǎn)(n-2)個(gè)，然后加入構(gòu)建的新節(jié)點(diǎn)(n-1)個(gè)
- 重復(fù)上面操作，一直到所有節(jié)點(diǎn)都被處理
在具體實(shí)現(xiàn)上，找到最小兩個(gè)節(jié)點(diǎn)需要排序操作，我們來看看2，6，8，9，3權(quán)值節(jié)點(diǎn)構(gòu)成哈夫曼樹的過程。
初始時(shí)候各個(gè)節(jié)點(diǎn)獨(dú)立，先將其排序(這里使用優(yōu)先隊(duì)列)，然后選兩個(gè)最小節(jié)點(diǎn)(拋出)生成一個(gè)新的節(jié)點(diǎn)，再將其加入優(yōu)先隊(duì)列中，此次操作完成后優(yōu)先隊(duì)列中有5，6，8，9節(jié)點(diǎn)
重復(fù)上面操作，這次結(jié)束 隊(duì)列中有11，8，9節(jié)點(diǎn)(排序后8，9，11)
圖片如果隊(duì)列為空，那么返回節(jié)點(diǎn)，并且這個(gè)節(jié)點(diǎn)為整個(gè)哈夫曼樹根節(jié)點(diǎn)root。
否則繼續(xù)加入隊(duì)列進(jìn)行排序。重復(fù)上述操作，直到隊(duì)列為空。
在計(jì)算帶權(quán)路徑長(zhǎng)度WPL的時(shí)候，需要重新計(jì)算高度(從下往上)，因?yàn)楣蚵鼧涫菑南峦蠘?gòu)造的，并沒有以常量維護(hù)高度，可以構(gòu)造好然后計(jì)算高度。
具體代碼實(shí)現(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é)點(diǎn)
- 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
哈夫曼編碼
除了哈夫曼樹你聽過，哈夫曼編碼你可能也聽過，但是不一定了解它是個(gè)什么玩意兒，哈夫曼編碼其實(shí)就是哈夫曼樹的一個(gè)非常重要的應(yīng)用，在這里就簡(jiǎn)單介紹原理并不詳細(xì)實(shí)現(xiàn)了。
哈夫曼編碼定義：哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫做Huffman編碼(有時(shí)也稱為霍夫曼編碼)。
哈夫曼編碼的目的是為了減少存儲(chǔ)體積，以一個(gè)連續(xù)的字符串為例，拋開編程語(yǔ)言中實(shí)際存儲(chǔ)，就拿
aaaaaaaaaabbbbbcccdde
這個(gè)字符串來說，在計(jì)算機(jī)中如果每個(gè)字符都是定長(zhǎng)存儲(chǔ)(假設(shè)長(zhǎng)為4的二進(jìn)制存儲(chǔ))，計(jì)算機(jī)只知道0和1的二進(jìn)制，假設(shè)
- a:0001
- b:0010
- c:0011
- d:0100
- e:0101
那么上面字符串可以用二進(jìn)制存儲(chǔ)是這樣的
000100010001000100010001……0101
如果每個(gè)字符編碼等長(zhǎng)，那么就沒有存儲(chǔ)空間優(yōu)化可言，都是單個(gè)字符長(zhǎng)度 * 字符個(gè)數(shù)。但是如果每個(gè)字符編碼不等長(zhǎng)，那么設(shè)計(jì)的開放性就很強(qiáng)了。
比如一個(gè)字符串a(chǎn)aaaabb
如果設(shè)計(jì)a為01，b設(shè)計(jì)為1。那么二進(jìn)制就為：010101010111
如果設(shè)計(jì)a為1，b設(shè)計(jì)為01。那么二進(jìn)制就為：111110101
如果設(shè)計(jì)a為1，b設(shè)計(jì)為0。那么二進(jìn)制就為：1111100
你看，在計(jì)算機(jī)的01二進(jìn)制世界中，明顯第二種比第一種優(yōu)先，第三種又比第二種優(yōu)先。所以，設(shè)計(jì)編碼要考慮讓出現(xiàn)多的盡量更短，出現(xiàn)少的稍微長(zhǎng)點(diǎn)沒關(guān)系。
但是，你需要考慮的一個(gè)問題是，二進(jìn)制開始0，1，01，10，11這個(gè)順序 ，如果來了001它到底是0，0，1還是0，01呢?所以編碼不等長(zhǎng)的時(shí)候你要考慮到這個(gè)編碼要有唯一性不能出現(xiàn)歧義。這個(gè)怎么搞呢?
簡(jiǎn)單啊，計(jì)算機(jī)只知道01二進(jìn)制，而二叉樹剛好有左右兩個(gè)節(jié)點(diǎn)，至于一個(gè)字符它如果是對(duì)應(yīng)葉子節(jié)點(diǎn)，那么就可以直接確定，也就是這個(gè)數(shù)值如果映射成一個(gè)二叉樹字符不能存在非葉子節(jié)點(diǎn)上。
所以，哈夫曼編碼具體流程就很清晰了，先統(tǒng)計(jì)字符出現(xiàn)的次數(shù)，然后將這個(gè)次數(shù)當(dāng)成權(quán)值按照上面介紹的方法構(gòu)造一棵哈夫曼樹，然后樹的根不存，往左為0往右為1每個(gè)葉子節(jié)點(diǎn)得到的二進(jìn)制數(shù)字就是它的編碼，這樣頻率高的字符在上面更短在整個(gè)二進(jìn)制存儲(chǔ)中也更節(jié)省空間。
結(jié)語(yǔ)
哈夫曼樹還是比較容易理解，主要構(gòu)造利用貪心算法的思想去從下往上構(gòu)建，哈夫曼編碼相信看了你也有所收獲，有興趣可以自己實(shí)現(xiàn)一下哈夫曼編碼的代碼(編碼、解碼)。本人水平有限，如果有錯(cuò)誤還希望大佬指正!
