重學資料結構之哈夫曼樹

一、哈夫曼樹

1.帶權擴充二叉樹的外部路徑長度

　　擴充二叉樹的外部路徑長度，即根到其葉子節點的路徑長度之和，

　　例如下面這兩種帶權擴充二叉樹：

　　左邊的二叉樹的外部路徑長度為：(2 + 3 + 6 + 9) * 2 = 38，

　　右邊的二叉樹的外部路徑長度為：9 + 6 * 2 + (2 + 3) * 3 = 36，

2.哈夫曼樹

　　哈夫曼樹（Huffman Tree）是一種重要的二叉樹，在資訊領域有重要的理論和實際價值，

　　設有實數集 W = {W₀ ，W₁ ，···，W_m-1 }，T 是一顆擴充二叉樹，其 m 個外部節點分別以 W_i (i = 1, 2, n - 1) 為權，而且 T 的帶權外部路徑長度在所有這樣的擴充二叉樹中達到最小，則稱 T 為資料集 W 的最優二叉樹或者哈夫曼樹，

二、哈夫曼演算法

1.基本概念

　　哈夫曼（D.A.Huffman）提出了一個演算法，它能從任意的實數集合構造出與之對應的哈夫曼樹，這個構造演算法描述如下：

• 演算法的輸入為實數集合 W = {W₀ ，W₁ ，···，W_m-1 }，
• 在構造中維護一個包含 k 個二叉樹集合的集合 F，開始時k = m 且 F = {T₀ ，T₁ ，···，T_m-1 }，其中每個 T_i 是一顆只包含權為 W_i 的根節點的二叉樹，

　　該演算法的構造程序中會重復執行以下兩個步驟，直到集合 F 中只剩下一棵樹為止：

1. 構造一顆二叉樹，其左右子樹是從集合 F 中選取的兩顆權值最小的二叉樹，其根節點的權值設定為這兩顆子樹的根節點的權值之和，
2. 將所選取的兩顆二叉樹從集合 F 中洗掉，把新構造的二叉樹加入到集合 F 中，　

　　注意：給定集合 W 上的哈夫曼樹并不唯一！

2.示例

　　對于實數集合 W = {2, 1, 3, 7, 8, 4, 5}，下面的圖1到圖7表示了從這個實數集合開始，構造一個哈夫曼樹的程序：

　　圖1：

 　　圖2：

 　　圖3：

　　圖4： 　　

　　圖5： 

　　圖6： 

　　圖7： 

三、哈夫曼演算法的實作

1.實作思路

　　要實作哈夫曼演算法，需要維護一組二叉樹，而且要知道每顆二叉樹的根節點的權值 ，這個可以使用前面定義的二叉樹的節點來構造哈夫曼樹，只需要在根節點處記錄該樹的權值，而在執行演算法時

　　在演算法開始時，需要根據傳入的實數集和來創建一組單節點的二叉樹，并以權值作為其優先級存入一個優先級佇列之中，在之后的程序中反復執行以下兩步，直至佇列中只有一顆二叉樹：

　　1）從該優先級佇列中取出兩顆權值最小的二叉樹；

　　2）創建一顆新的二叉樹，其權值為選出的兩棵樹的權值之和，其左右子樹分別為選出的兩顆樹，并將創建好的二叉樹加入到優先級佇列中，

　　當整個優先級佇列中只剩下一顆二叉樹的時候，就得到我們需要的哈夫曼樹了，

2.實作代碼

　　首先是要對哈夫曼樹的節點進行定義，主要是增加一個權值，定義哈夫曼樹節點的代碼如下：

1 # 哈夫曼樹節點
2 class HNode(Node):
3     def __init__(self, value=https://www.cnblogs.com/TM0831/p/None, left=None, right=None, weight=None):
4         super(HNode, self).__init__()
5         self.value =https://www.cnblogs.com/TM0831/p/ value
6         self.left = left
7         self.right = right
8         self.weight = weight

　　然后還需要一個優先級的佇列，在我前面寫過的一篇佇列的博客中有提到，只不過那篇博客里的優先級佇列用的是一個最大堆，而在這里需要用最小堆，這樣每次才能取出權值最小的樹，

　　最后，下面就是實作哈夫曼演算法的主要代碼了：

 1 def create(weights: list):
 2     """
 3     根據傳入的權值串列創建一個哈夫曼樹
 4     :param weights: 實數集合
 5     """
 6     queue = PriorityQueue()
 7     # 將節點添加到優先級佇列中
 8     for weight in weights:
 9         node = HNode(weight=weight)
10         queue.enqueue(node, weight)
11     while queue.size() > 1:
12         node1 = queue.dequeue()
13         node2 = queue.dequeue()
14         new_node = HNode(left=node1, right=node2, weight=node1.weight + node2.weight)
15         queue.enqueue(new_node, new_node.weight)
16     return queue.dequeue()

四、哈夫曼編碼問題

1.問題描述 

　　最優編碼問題，給定兩個集合 C 和 W，C 為基本資料集合，W 為 C 中各個字符在實際資訊傳遞中使用的頻率，要求設定一套編碼規則，要求： 1）使用這種編碼規則的開銷最小； 2）對任意一對不同字符 Ci 和 Cj，要求 Ci 的編碼不是 Cj 編碼的前綴，

2.問題分析

　　使用哈夫曼演算法構建一顆哈夫曼樹，這棵樹的葉子節點的數量和字符數量一致，葉子節點的值就是字符的值，葉子節點的權值就是該字符對應的使用頻率，然后從根節點開始遍歷，往左子樹遍歷時標記為0，往右子樹遍歷時標記為1，這樣就能保證走到葉子節點時所標記的路徑結果是不一樣的了，最后將每個葉子節點的值和對應的標記結果回傳，就是題目所求的最優編碼，

　　例如輸入的資料為：{"A": 2, "b": 3, "c": 5, "d": 6, "e": 9} ，

　　則構造出來的哈夫曼樹如下圖：

　　最后得到的編碼為：{"A": "000", "b": "001", "c": "01", "d": "10", "e": "11"} 

3.代碼實作

　　下面就是使用哈夫曼演算法來求解編碼問題的主要代碼了：

 1 from Tree.tree import Node
 2 from Queue.queue import PriorityQueue
 3 
 4 
 5 # 哈夫曼樹節點
 6 class HNode(Node):
 7     def __init__(self, value=https://www.cnblogs.com/TM0831/p/None, left=None, right=None, weight=None):
 8         super(HNode, self).__init__()
 9         self.value =https://www.cnblogs.com/TM0831/p/ value
10         self.left = left
11         self.right = right
12         self.weight = weight
13 
14 
15 # 自定義哈夫曼樹
16 class HuffmanTree:
17     def __init__(self):
18         self.root = HNode()
19         self.code = {}
20 
21     def get_leaves(self, node: HNode, code: str):
22         """
23         獲取所有葉節點，對樹中的分支節點向左子節點的路徑標記為0，向右子節點的路徑標記為1
24         :param node: 哈夫曼樹的節點
25         :param code: 字符使用的編碼
26         :return:
27         """
28         if not node:
29             return
30         code_ = code  # 因為要分別向左向右探索路徑，所以需要復制一份
31         if node.left:
32             code += "0"
33             self.get_leaves(node.left, code)
34         if node.right:
35             code_ += "1"
36             self.get_leaves(node.right, code_)
37         # 沒有左右子節點，表明是葉子節點
38         if not node.left and not node.right:
39             self.code[node.value] = code
40 
41     def create(self, char_data: dict):
42         """
43         根據傳入的權值串列創建一個哈夫曼樹
44         :param char_data: 字符和其對應頻率的字典
45         """
46         queue = PriorityQueue()
47         # 將節點添加到優先級佇列中
48         for char, weight in char_data.items():
49             node = HNode(value=https://www.cnblogs.com/TM0831/p/char, weight=weight)
50             queue.enqueue(node, weight)
51         while queue.size() > 1:
52             node1 = queue.dequeue()
53             node2 = queue.dequeue()
54             new_node = HNode(left=node1, right=node2, weight=node1.weight + node2.weight)
55             queue.enqueue(new_node, new_node.weight)
56         self.root = queue.dequeue()
57 
58 
59 def solution(char_data: dict):
60     """
61     解決哈夫曼編碼問題
62     :param char_data: 字符和其對應頻率的字典
63     :return:
64     """
65     tree = HuffmanTree()
66     tree.create(char_data)
67     tree.get_leaves(tree.root, "")
68     return tree.code

標籤：其他

上一篇：VoIP新手入門級培訓資料下載

下一篇：有沒有大佬能幫忙看看這怎么弄，為啥PC1就ping不通PC2