赫夫曼樹（Huffman）的構建和應用（編碼、解碼）

赫夫曼樹的概念

要了解赫夫曼樹，我們要首先從擴充二叉樹說起

二叉樹結點的度

結點的度指的是二叉樹結點的分支數目， 如果某個結點沒有孩子結點，即沒有分支，那麼它的度是0；如果有一個孩子結點， 那麼它的度數是1；如果既有左孩子也有右孩子， 那麼這個結點的度是2.

擴充二叉樹

對於一顆已有的二叉樹， 如果我們為它添加一系列新結點， 使得它原有的所有結點的度都為2，那麼我們就得到了一顆擴充二叉樹， 如下圖所示：

其中原有的結點叫做內結點（非葉子結點）， 新增的結點叫做外結點（葉子結點）

我們可以得出： 外結點數 = 內結點數 + 1

並進一步得出： 總結點數 = 2 × 外結點數 -1

擴充二叉樹，構成了赫夫曼樹的基本形態，而上面的公式，也是我們構建赫夫曼樹的依據之一

赫夫曼樹的外結點和內結點

赫夫曼樹的外結點和內結點的性質區別：外節點是攜帶了關鍵數據的結點， 而內部結點沒有攜帶這種數據， 只作為導向最終的外結點所走的路徑而使用

正因如此，我們的關注點最後是落在赫夫曼樹的外結點上， 而不是內結點。

帶權路徑長度WPL

讓我們思考一下： 在一顆在外結點上存儲了數據的擴充二叉樹中進行查找時，數據結點怎麼分布才能儘可能減少查找的開銷呢？ 這裡我們再加上一個前提：不同的數據結點搜索的頻率（或機率）是不一致的。

顯然， 我們大致的思路是： 如果一個數據結點搜索頻率越高，就讓它分布在離根結點越近的地方，也即從根結點走到該結點經過的路徑長度越短。 這樣就能從整體上優化整顆樹的性能。

頻率是個細化的量，這裡我們用一個更加標準的一個詞描述它——「權值」。

綜上， 我們為擴充二叉樹的外結點（葉子結點）定義兩條屬性： 權值（w）和路徑長度(l)。同時規定帶權路徑長度（WPL）為擴充二叉樹的外結點的權值和路徑長度乘積之和：

（注意只是外結點！）

赫夫曼樹（最優二叉樹）

由n個權值構造一顆有n個葉子結點的二叉樹， 則其中帶權路徑長度WPL最小的二叉樹， 就是赫夫曼樹，或者叫做最優二叉樹。

例如下圖中對a, b, c

對a: WPL = 7×2 + 5×2 + 2×2 + 4×2 = 36；

對b: WPL = 7×3 + 5×3 + 2×1 + 4×2 = 46;

對c: WPL = 7×1 + 5×2 + 2×3 + 4×3 = 35;

c中WPL最小， 可以驗證， 它就是赫夫曼樹， 而a和b都不是赫夫曼樹

對於同一組權值的葉結點， 構成的赫夫曼樹可以有多種形態， 但是最小WPL值是唯一的。

赫夫曼樹的構建

構建過程分四步：

1. 根據給定的n個權值{w1, w2, w3 ... wn }構成n棵二叉樹的集合， 每棵二叉樹都只包含一個結點

2. 在上面的二叉樹中選出兩顆根結點權值最小的樹， 同時另外取一個新的結點作為這兩顆樹的根結點， 設新節點的權值為兩顆權值最小的樹的權值和， 將得到的這顆樹也加入到樹的集合中

3. 在2操作後， 從集合中刪除權值最小的那兩顆樹

4. 重複2和3，直到集合中的樹只剩下一棵為止， 剩下的這顆樹就是我們要求得的赫夫曼樹。

如下圖所示：

（注意a和b的分界線在4和7中間，圖中畫的不是很清晰）

我們上面提到過WPL相同的情況下， 赫夫曼樹不止一種，在我們介紹的算法中，人為要求某個內結點的左兒子的權值要比右兒子大， 這樣一來， 就將我們算法中的赫夫曼樹變為唯一一種了。

構建赫夫曼樹的的方法有多種，但基於實際應用的考慮（赫夫曼編碼和解碼）， 下面我給出基於數組存儲實現的赫夫曼樹：

Node類的設計

我們首先需要一個編寫一個結點類， 結點類里有5種實例變量： weight表示權值， data表示外結點存儲的字符，data屬性在下面的編碼/解碼中會用到。 而同樣因為赫夫曼編碼，解碼的需求，這裡我們使用三叉鏈實現二叉樹，，即在left和right屬性的基礎上，為結點增加了parent屬性，目的是能夠從葉子結點上溯到根結點，從而實現赫夫曼編碼。

/**
 * @Author: HuWan Peng
 * @Date Created in 23:21 2018/1/14
 */
public class Node {
 char data; // 數據
 int weight; // 權值
 int left, right, parent; // 三條連結
 public Node (char data, int weight) {
 this.data = data;
 this.weight = weight;
 }
 public Node (int weight) {
 this.weight = weight;
 }
}

buildTree方法的設計

輸入參數和返回值

輸入參數： 一個由外結點對象組成的Node數組， 假設其為nodes

返回值： 一個由內、外結點共同組成，且建立了連結關係的Node數組, 假設其為HT（HuffmanTree）

具體操作

首先要做的事情是： 獲取輸入的nodes數組的長度 n , 創建一個長度為 2n - 1的數組——HT，在數組HT中, 前n個元素用來存放外結點， 後n個元素用來存放內結點， 如下圖所示：

圖A

圖B

接下來要做的是：

1. 初始化HT中的結點對象，此時各個結點對象的weight都被置為0

2. 將輸入的nodes數組中的各結點對象的權值賦給HT[0]~ HT[n-1]， 如上圖所示

3.通過循環， 依次計算各個內結點的權值，同時建立該內結點和作為它左右孩子的兩個外結點的連結關係。

易知：當最後一個內結點的權值也計算完畢後， 整顆赫夫曼樹也就構建完畢了。

如圖 （方框內數字表示結點對象的權值）

注意要點

要注意的是： 我們為Node設置的連結變量left/right/parent是整型的， 它指向的是某個結點對象在HT中的下標， 而不是結點對象本身！ 這種實現方式和一般的樹是有區別的

具體代碼

下面是buildTre方法的代碼：

（select方法尚未給出）

 /**
 * @description: 構建赫夫曼樹
 */
 public Node[] buildTree (Node [] nodes) {
 int s1, s2,p;
 int n = nodes.length; // 外結點的數量
 int m = 2*n - 1; // 內結點 + 外結點的總數量
 Node [] HT = new Node [m]; // 存儲結點對象的HT數組
 for (int i=0;i for (int i=0;i HT[i].data = nodes[i].data;
 HT[i].weight = nodes[i].weight; //將給定的權值列表賦給外結點對象
 }
 for (int i=n;i s1 = select(HT,i,0); // 取得HT數組中權值最小的結點對象的下標
 s2 = select(HT,i,1); // 取得HT數組中權值次小的結點對象的下標
 HT[i].left = s1; // 建立連結
 HT[i].right = s2;
 HT[s1].parent = i;
 HT[s2].parent = i;
 HT[i].weight = HT[s1].weight + HT[s2].weight;// 計算當前外結點的權值
 selectStart+=2; // 這個變量表示之前「被刪除」的最小結點的數量和
 }
 return HT; // 將處理後的HT數組返回
 }

buildTree方法的用例：

 /**
 * @description: buildTree方法的用例
 */
 public static void main (String [] args) {
 Node [] nodes = new Node[4];
 nodes[0] = new Node('a',7);
 nodes[1] = new Node('b',5);
 nodes[2] = new Node('c',2);
 nodes[3] = new Node('d',4);
 HuffmanTree ht = new HuffmanTree();
 Node [] n = ht.buildTree(nodes); // n是構建完畢的赫夫曼樹
 }
}

select方法的設計

buildTree方法的實現依賴於select方法：

private int select (Node[] HT,int range, int rank)

上面代碼中調用select的部分為：

s1 = select(HT,i,0); // 取得HT數組中權值最小的結點對象的下標
s2 = select(HT,i,1); // 取得HT數組中權值次小的結點對象的下標

思考3個問題：

1. 求給定權值排名的結點，可以先對數組進行從小到大的快速排序， 然後就可以取得給定排名的結點對象了， 但是如果直接對輸入的HT數組進行排序的話， 會改變HT數組元素的排列順序， 這將不利於我們下面要介紹的赫夫曼編碼的方法的實現。 所以這裡我們先將HT數組拷貝到一個輔助數組copyNodes中， 對copyNodes進行快排，並取得給定權值排名的結點對象。然後通過遍歷HT數組，比較得到該結點對象在HT中的下標

2. 在上面我們提到過， 在構建一顆新二叉樹後， 要把原來的兩顆權值最小的樹從集合中 」刪除「，這裡我們通過類內的selectStart實例變量實現， selectStart初始值為0， 每次構建一棵新二叉樹後都通過 selectStart+=2; 增加它的值。（見上文buildTree代碼） 這樣， 在select方法中就可以通過copyNodes[selectStart + rank]，去取得 "刪除" 後權值排名為rank的結點對象了。

3. 引入range這一參數是為了排除那些weight仍為0，即尚未使用到的內結點， 防止排序後取到它們。注意， 隨著循環中 i 的增長， range也是不斷增長的：

具體代碼

（QuickSort的代碼文末將給出）

 /**
 * @description: 返回權值排名為rank的結點對象在HT中的下標（按權值從小到大排）
 */
 private int select (Node[] HT,int range, int rank) {
 Node [] copyNodes = Arrays.copyOf(HT, range);// 將HT[0]~HT[range]拷貝到copyNodes中
 QuickSort.sort(copyNodes); // 對copyNodes進行從小到大的快速排序
 Node target = copyNodes[rank + selectStart]; // 取得「刪除」後權值排名為rank的結點對象
 for (int j=0;j if (target == HT[j]) return j; // 返回該結點對象在數組HT中的下標
 }
 return -1;
 }

過程圖解

這樣，通過調用buildTree方法， 我們的赫夫曼樹就構造好了。

赫夫曼樹的應用

赫夫曼樹可以用於優化編碼， 在這之前， 先讓我們了解下什麼是等長編碼和不等長編碼。

等長編碼和不等長編碼

等長編碼

例如一段電文為 'A B A C C D A', 它只有4種字符，只需要兩個字符的串就可以分辨， 所以我們可以按等長編碼的設計原則， 將A，B，C，D表示為00、01、10、11, 'A B A C C D A'就被編碼為『00010010101100』， 共14位。 它的優點是： 因為間隔相同， 解碼時不存在二義性的問題。 但缺點在於， 有些字符本可以被設計為更短的編碼， 也就是說，設計為等長編碼， 我們實際上浪費了一部分編碼的空間（長度）

不等長編碼

同上， 如果採用不等長編碼， 可以把A，B，C，D表示為0、00、1、01, 那麼 'A B A C C D A'就可以被編碼為『000011010』， 總長只要9就夠了！ 比起等長編碼我們節約了5位的長度。 但問題是： 由於長度間隔不一致， 解碼時可能存在二義性，這導致無法翻譯，例如 『00『，到底是看成'00'還是』0『 + 』0『呢？ 前者被翻譯為B，而後者被翻譯為A。

前綴編碼

所以，要設計長短不等的編碼， 則必須保證： 任意一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼就叫做前綴編碼

赫夫曼編碼的作用

赫夫曼編碼就是一種前綴編碼， 它能解決不等長編碼時的解碼問題， 通過它，我們既能儘可能減少編碼的長度， 同時還能夠避免二義性， 實現正確解碼。

赫夫曼編碼是如何實現前綴編碼的 ？

假設有一棵如下圖所示的二叉樹， 其4個葉結點分別表示A，B，C，D這4個字符，且約定左分支表示字符'0', 右分支代表字符'1', 則可以從根結點到葉子結點的路徑上的各分支字符組成的字符串作為該葉子結點字符的編碼。 從而得到A，B，C，D的二進位編碼分別為0， 10， 110， 111。

具體如下圖所示：

赫夫曼編碼和解碼都要調用上文講述的buildTree方法

實現赫夫曼編碼(encode)

根據給定的字符和權值， 輸出字符和對應的赫夫曼編碼

注意要點

1. 我們編寫一個HuffmanCode內部類用於存放字符（data實例變量）和它對應的二進位字符串（bit實例變量）

2. 要求所有字符對應的編碼時，如果採用從根結點下行到葉結點的思路處理，邏輯會相對複雜一些， 所以我們用逆向的方式獲取： 按照從葉子結點到根結點的路徑累加二進位字符串

3. 因為 2 的原因， 累加二進位字符串的時候也必須反向累加，例如寫成bit= "0" + bit; 而不是寫成bit= bit+ "0";

4. 上溯時候要做的工作是： 判斷當前經過的是 0 還是 1， 判斷的方法如下圖所示：

假設P是X的父節點：

• 如果P.left==X在HT中的下標，則說明X是P的左分支，說明經過的是 0
• 如果P.right==X在HT中的下標，則說明X是P的右分支，說明經過的是 1

代碼如下：

import java.util.Arrays;
/**
 * @Author: HuWan Peng
 * @Date Created in 22:54 2018/1/14
 */
public class HuffmanTree {
 private class HuffmanCode {
 char data; // 存放字符，例如 'C'
 String bit; // 存放編碼後的字符串, 例如"111"
 public HuffmanCode (char data, String bit) {
 this.data = data;
 this.bit = bit;
 }
 }
 
 /**
 * @description: 構建赫夫曼樹
 */
 public Node[] buildTree (Node [] nodes) {
 // 具體代碼見上文
 }
 
 /**
 * @description: 進行赫夫曼編碼
 */
 public HuffmanCode [] encode(Node [] nodes) {
 Node [] HT = buildTree(nodes); // 根據輸入的nodes數組構造赫夫曼樹
 int n = nodes.length;
 HuffmanCode [] HC = new HuffmanCode [n];
 String bit;
 for (int i=0;i bit = "";
 for (int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { // 從葉子結點上溯到根結點
 if(HT[f].left == c) bit= "0" + bit; // 反向編碼
 else bit= "1" + bit;
 }
 HC[i] = new HuffmanCode(HT[i].data,bit); // 將字符和對應的編碼存儲起來
 }
 return HC;
 }
 
 /**
 * @description: encode方法的用例
 */
 public static void main (String [] args) {
 Node [] nodes = new Node[4];
 nodes[0] = new Node('A',7);
 nodes[1] = new Node('B',5);
 nodes[2] = new Node('C',2);
 nodes[3] = new Node('D',4);
 HuffmanTree ht = new HuffmanTree();
 HuffmanCode[] hc = ht.encode(nodes);
 // 對A，B，C，D進行編碼
 for (int i=0;i System.out.println(hc[i].data + ":" +hc[i].bit);
 }
 }
}

輸出結果：

A:0
B:10
C:110
D:111

赫夫曼解碼(decode)

根據給定的字符和權值， 將輸入的赫夫曼編碼翻譯回原字符串

解碼的時候，從根結點HT[HT.length -1] 開始, 向下行走， 通過charAt方法取得字符串當前的字符， 如果為 '0'則向左走， 為'1'則向右走， 當下行到葉子結點時候，取得葉子結點包含的字符， 添加到當前的解碼字符串中，同時有回到根結點，繼續循環。

代碼如下：

import java.util.Arrays;

/**
 * @Author: HuWan Peng
 * @Date Created in 22:54 2018/1/14
 */
public class HuffmanTree {
 int selectStart = 0;
 private class HuffmanCode {
 char data; // 存放字符，例如 'C'
 String bit; // 存放編碼後的字符串, 例如"111"
 public HuffmanCode (char data, String bit) {
 this.data = data;
 this.bit = bit;
 }
 }
 
 /**
 * @description: 構建赫夫曼樹
 */
 public Node[] buildTree (Node [] nodes) {
 // 代碼見上文
 }
 
 /**
 * @description: 進行赫夫曼解碼
 */
 public String decode (Node [] nodes, String code) {
 String str="";
 Node [] HT = buildTree(nodes);
 int n =HT.length -1;
 for (int i=0;i char c = code.charAt(i);
 if(c == '1') {
 n = HT[n].right;
 }
 else {
 n = HT[n].left;
 }
 if(HT[n].left == 0) {
 str+= HT[n].data;
 n =HT.length -1;
 }
 }
 return str;
 }
 /**
 * @description: decode方法的用例
 */
 public static void main (String [] args) {
 Node [] nodes = new Node[4];
 nodes[0] = new Node('A',7);
 nodes[1] = new Node('B',5);
 nodes[2] = new Node('C',2);
 nodes[3] = new Node('D',4);
 HuffmanTree ht = new HuffmanTree();
 // 對 010110111 進行解碼
 System.out.println(ht.decode(nodes,"010110111"));
 }
}

輸出：

ABCD

全部代碼：

代碼共三份：

1.HuffmanTree.java

2.Node.java

3.QuickSort.java

Node.java

/**
 * @Author: HuWan Peng
 * @Date Created in 23:21 2018/1/14
 */
public class Node {
 char data;
 int weight;
 int left, right, parent;
 public Node (char data, int weight) {
 this.data = data;
 this.weight = weight;
 }
 public Node (int weight) {
 this.weight = weight;
 }
}

HuffmanTree.java

import java.util.Arrays;
/**
 * @Author: HuWan Peng
 * @Date Created in 22:54 2018/1/14
 */
public class HuffmanTree {
 int selectStart = 0;
 private class HuffmanCode {
 char data; // 存放字符，例如 'C'
 String bit; // 存放編碼後的字符串, 例如"111"
 public HuffmanCode (char data, String bit) {
 this.data = data;
 this.bit = bit;
 }
 }
 /**
 * @description: 返回權值排名為rank的結點對象在nodes中的下標（按權值從小到大排）
 */
 private int select (Node[] HT,int range, int rank) {
 Node [] copyNodes = Arrays.copyOf(HT, range);// 將HT[0]~HT[range]拷貝到copyNodes中
 QuickSort.sort(copyNodes); // 對copyNodes進行從小到大的快速排序
 Node target = copyNodes[rank + selectStart]; // 取得「刪除」後權值排名為rank的結點對象
 for (int j=0;j if (target == HT[j]) return j; // 返回該結點對象在數組HT中的下標
 }
 return -1;
 }
 
 /**
 * @description: 構建赫夫曼樹
 */
 public Node[] buildTree (Node [] nodes) {
 int s1, s2,p;
 int n = nodes.length; // 外結點的數量
 int m = 2*n - 1; // 內結點 + 外結點的總數量
 Node [] HT = new Node [m]; // 存儲結點對象的HT數組
 for (int i=0;i for (int i=0;i HT[i].data = nodes[i].data;
 HT[i].weight = nodes[i].weight; //將給定的權值列表賦給外結點對象
 }
 for (int i=n;i s1 = select(HT,i,0); // 取得HT數組中權值最小的結點對象的下標
 s2 = select(HT,i,1); // 取得HT數組中權值次小的結點對象的下標
 HT[i].left = s1; // 建立連結
 HT[i].right = s2;
 HT[s1].parent = i;
 HT[s2].parent = i;
 HT[i].weight = HT[s1].weight + HT[s2].weight;// 計算當前外結點的權值
 selectStart+=2; // 這個變量表示之前「被刪除」的最小結點的數量和
 }
 return HT; // 將處理後的HT數組返回
 }
 
 /**
 * @description: 進行赫夫曼編碼
 */
 public HuffmanCode [] encode(Node [] nodes) {
 Node [] HT = buildTree(nodes); // 根據輸入的nodes數組構造赫夫曼樹
 int n = nodes.length;
 HuffmanCode [] HC = new HuffmanCode [n];
 String bit;
 for (int i=0;i bit = "";
 for (int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { // 從葉子結點上溯到根結點
 if(HT[f].left == c) bit= "0" + bit; // 反向編碼
 else bit= "1" + bit;
 }
 HC[i] = new HuffmanCode(HT[i].data,bit); // 將字符和對應的編碼存儲起來
 }
 return HC;
 }
 
 /**
 * @description: 進行赫夫曼解碼
 */
 public String decode (Node [] nodes, String code) {
 String str="";
 Node [] HT = buildTree(nodes);
 int n =HT.length -1;
 for (int i=0;i char c = code.charAt(i);
 if(c == '1') {
 n = HT[n].right;
 }
 else {
 n = HT[n].left;
 }
 if(HT[n].left == 0) {
 str+= HT[n].data;
 n =HT.length -1;
 }
 }
 return str;
 }
 /**
 * @description: buildTree方法的用例
 */
 public static void main (String [] args) {
 Node [] nodes = new Node[4];
 nodes[0] = new Node('A',7);
 nodes[1] = new Node('B',5);
 nodes[2] = new Node('C',2);
 nodes[3] = new Node('D',4);
 HuffmanTree ht = new HuffmanTree();
 System.out.println(ht.decode(nodes,"010110111"));
 }
}

QuickSort.java

/**
 * @Author: HuWan Peng
 * @Date Created in 22:56 2018/1/14
 */
public class QuickSort {
 /**
 * @description: 交換兩個數組元素
 */
 private static void exchange(Node [] a , int i, int j) {
 Node temp = a[i];
 a[i] = a[j];
 a[j] = temp;
 }
 
 /**
 * @description: 切分函數
 */
 private static int partition (Node [] a, int low, int high) {
 int i = low, j = high+1; // i, j為左右掃描指針
 int pivotkey = a[low].weight; // pivotkey 為選取的基準元素（頭元素）
 while(true) {
 while (a[--j].weight>pivotkey) { if(j == low) break; } // 右游標左移
 while(a[++i].weight if(i>=j) break; // 左右游標相遇時候停止， 所以跳出外部while循環
 else exchange(a,i, j) ; // 左右游標未相遇時停止, 交換各自所指元素，循環繼續
 }
 exchange(a, low, j); // 基準元素和游標相遇時所指元素交換，為最後一次交換
 return j; // 一趟排序完成， 返回基準元素位置
 }
 /**
 * @description: 根據給定的權值對數組進行排序
 */
 private static void sort (Node [] a, int low, int high) {
 if(high<= low) { return; } // 當high == low, 此時已是單元素子數組，自然有序， 故終止遞歸
 int j = partition(a, low, high); // 調用partition進行切分
 sort(a, low, j-1); // 對上一輪排序(切分)時，基準元素左邊的子數組進行遞歸
 sort(a, j+1, high); // 對上一輪排序(切分)時，基準元素右邊的子數組進行遞歸
 }
 
 public static void sort (Node [] a){ //sort函數重載， 只向外暴露一個數組參數
 sort(a, 0, a.length-1);
 }
}

參考資料

《算法（java）》 — — Robert Sedgewick， Kevin Wayne

《數據結構》 — — 嚴蔚敏