哈弗曼樹與哈夫曼編碼
- 2019 年 10 月 3 日
- 筆記
更新、更全的《數據結構與演算法》的更新網站,更有python、go、人工智慧教學等著你:https://www.cnblogs.com/nickchen121/p/11407287.html
一、什麼是哈夫曼樹(Huffman Tree)
如果我們將百分制的考試成績轉換成五分制的成績,我們可以使用如下所示的程式:
/* c語言實現 */ if( score < 60 ) grade =1; else if( score < 70 ) grade =2; else if( score < 80 ) grade =3; else if( score < 90 ) grade =4; else grade =5;
通過上述的程式碼,我們可以構造出如下圖所示的判定樹:
如果在上述五分制的成績中,我們考慮學生成績的分布的概率,如下圖所示:
通過學生成績分布的概率和上述的判定樹,我們可以得到學生成績的查找效率為:
[ 0.05× 1+0.15 ×2+0.4× 3+0.3 ×4+0.1× 4 = 3.15 ]
從學生成績分布的概率中,可以看出70-79和80-89分布中的學生較多,然而他們的查找效率確是較低的,因此我們可以按照如下方式修改程式碼和判定樹:
/* c語言實現 */ if( score < 80 ) { if( score < 70 ); if( score < 60 ) { grade =1; } else grade = 2; else grad=3; } else if( score < 90 ) grade =4; else grade =5;
通過此次修改,學生成績的查找效率為:
[ 0.05× 3+0.15 ×3+0.4× 2+0.3 ×2+0.1× 2 = 2.2 ]
通過上述的例子,我們可以思考一個問題:如何根據結點不同的查找頻率構造更有效的搜索樹?
1.1 哈夫曼樹的定義
帶權路徑長度(WPL):設二叉樹有n個葉子結點,每個葉子結點帶有權值(w_k),從根節點到每個葉子結點的長度為(l_k),則每個葉子結點的帶權路徑長度之和就是:(WPL = sum_{k=1}^nw_kl_k)
最優二叉樹或哈夫曼樹:WPL最小的二叉樹
例:有五個葉子結點,它們的權值為 {1, 2, 3, 4, 5} ,用此權值序列可以構造出形狀不同的多個二叉樹。
二、哈夫曼樹的構造
每次把權值最小的兩顆二叉樹合併
/* c語言實現 */ typedef struct TreeNode *HuffmanTree; struct TreeNode{ int Weight; HuffmanTree Left, Right; } HuffmanTree Huffman( MinHeap H ) { // 假設H->Size個權值已經存在H->Elements[]->Weight里 int i; HuffmanTree T; BuildMinHeap(H); // 將H->Elements[]按權值調整為最小堆 for (i = 1; i < H->Size; i++) { // 做H->Size-1次合併 T = malloc(sizeof(struct TreeNode)); // 建立新結點 T->Left = DeleteMin(H); // 從最小堆中刪除一個結點,作為新T的左子結點 T->Right = DeleteMin(H); // 從最小堆中刪除一個結點,作為新T的右子結點 T->Weight = T->Left->Weight+T->Right->Weight; // 計算新權值 Insert(H, T); // 將新T插入最小堆 } T = DeleteMin(H); return T; }
# python語言實現 # 節點類 class Node(object): def __init__(self, name=None, value=None): self._name = name self._value = value self._left = None self._right = None # 哈夫曼樹類 class HuffmanTree(object): # 根據Huffman樹的思想:以葉子節點為基礎,反向建立Huffman樹 def __init__(self, char_weights): self.a = [Node(part[0], part[1]) for part in char_weights] # 根據輸入的字元及其頻數生成葉子節點 while len(self.a) != 1: self.a.sort(key=lambda node: node._value, reverse=True) c = Node(value=(self.a[-1]._value + self.a[-2]._value)) c._left = self.a.pop(-1) c._right = self.a.pop(-1) self.a.append(c) self.root = self.a[0] self.b = list(range(10)) # self.b用於保存每個葉子節點的Haffuman編碼,range的值只需要不小於樹的深度就行 # 用遞歸的思想生成編碼 def pre(self, tree, length): node = tree if (not node): return elif node._name: print(node._name + '的編碼為:') for i in range(length): print(self.b[i]) print() return self.b[length] = 0 self.pre(node._left, length + 1) self.b[length] = 1 self.pre(node._right, length + 1) # 生成哈夫曼編碼 def get_code(self): self.pre(self.root, 0) if __name__ == '__main__': # 輸入的是字元及其頻數 char_weights = [('a', 5), ('b', 4), ('c', 10), ('d', 8), ('f', 15), ('g', 2)] tree = HuffmanTree(char_weights) tree.get_code()
上述過程的時間複雜度為:O(N logN)
2.1 哈夫曼樹的特點
- 沒有度為1的結點;
- n個葉子結點的哈夫曼樹共有2n-1個結點
- 哈夫曼樹的任意非葉結點的左右子樹交換後仍是哈夫曼樹;
- 對同一組權值 ({W_1, W_2, cdots, W_n}),是否存在不同構的兩顆哈夫曼樹呢?
- 對一組權值 {1, 2, 3, 3},可以有如下圖所示的不同構的兩顆哈夫曼樹:
三、哈夫曼編碼
給定一段字元串,如何對字元進行編碼,可以使得該字元串的編碼存儲空間最少?
例:假設有一段文本,包含58個字元,並由以下7個字元構成:a,e,i,s,t,空格(sp),換行(nl)。這7個字元出現的次數不同。如何對這7個字元進行編碼,使得總編碼空間最少?
分析:
- 用等長ASCCII編碼:58*8 = 464位;
- 用等長3位編碼:58*3 = 174位;
- 不等長編碼:出現頻率高的字元用的編碼短些,出現頻率低的字元可以編碼長些?
對於上述問題,我們如果使用下圖所示方式進行不等長編碼:
很明顯,可以發現上圖所示的不等長編碼具有二義性,因此我們可以使用前綴碼的方式解決二義性問題。
前綴碼(prefix code):任何字元的編碼都不是另一字元編碼的前綴。
3.1 使用二叉樹編碼
使用二叉樹編碼,我們需要注意以下兩個問題:
- 左右分支:0、1
- 字元只在葉結點上
假設四個字元的頻率為:a:4,u:1,x:2,z:1;那麼我們可以使用最普通的二叉樹對這四個字元進行編碼,如下圖所示:
通過上圖可以發現,我們使用最偷懶的方式,把四個字元放在上述二叉樹的四個葉子結點上,因此我們可以考慮使用如下所示的方法,降低二叉樹的編碼代價:
綜上:哈夫曼編碼需要解決的一個問題為——如何構造一顆編碼代價最小的二叉樹。
3.2 使用哈夫曼樹編碼
對於我們提出來的7個字元的例子,如果我們得知這7個字元的分布概率為如下圖所示:
我們可以使用構造哈夫曼樹的方式,進行哈夫曼編碼,編碼流程如下:
最終結果如下圖所示: