Python描述數據結構學習之哈夫曼樹篇

更新時間：2020年09月07日 10:38:46 作者：夏悠然然

這篇文章主要給大家介紹了關于Python描述數據結構學習之哈夫曼樹篇的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

前言

本篇章主要介紹哈夫曼樹及哈夫曼編碼，包括哈夫曼樹的一些基本概念、構造、代碼實現以及哈夫曼編碼，并用Python實現。

1. 基本概念

哈夫曼樹(Huffman(Huffman(Huffman Tree)Tree)Tree)，又稱為最優(yōu)二叉樹，指的是帶權路徑長度最小的二叉樹。樹的帶權路徑常記作：

其中，nnn為樹中葉子結點的數目，wkw_kwk為第kkk個葉子結點的權值，lkl_klk為第kkk個葉子結點與根結點的路徑長度。

帶權路徑長度是帶權結點和根結點之間的路徑長度與該結點的權值的乘積。有關帶權結點、路徑長度的概念請參閱這篇博客。

對于含有nnn個葉子結點的哈夫曼樹，其共有2n−12n-12n−1個結點。因為在構造哈夫曼樹的過程中，每次都是以兩顆二叉樹為子樹創(chuàng)建一棵新的二叉樹，因此哈夫曼樹中不存在度為1的結點，即n1=0n_1=0n1=0，由二叉樹的性質可知，葉子結點數目n0=n2+1n_0=n_2+1n0=n2+1，所以n2=n0−1n_2=n_0-1n2=n0−1，總結點數目為n=n0+n1+n2=n+n−1=2n−1n=n_0+n_1+n_2=n+n-1=2n-1n=n0+n1+n2=n+n−1=2n−1。

2. 構造過程及實現

給定nnn棵僅含根結點的二叉樹T1,T2,…,TnT_1,T_2,\dots,T_nT1,T2,…,Tn，它們的權值分別為w1,w2,…,wnw_1,w_2,\dots,w_nw1,w2,…,wn，將它們放入到一個集合FFF中，即F={T1,T2,…,Tn}F=\{T_1,T_2,\dots,T_n\}F={T1,T2,…,Tn}；然后在集合FFF中選取兩棵權值最小的根結點構造一棵新的二叉樹，使新二叉樹的根結點的權值等于其左、右子樹根結點的權值之和；再然后將選中的那兩個結點從集合FFF中刪除，將新的二叉樹添加到FFF中；繼續(xù)重復上述操作，直至集合FFF中只剩一棵二叉樹為止。

比如F={(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)}F=\{(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)\}F={(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)}，它構造出來的哈夫曼樹就是下面這棵二叉樹：

代碼實現：

class HuffmanTreeNode(object):
 def __init__(self):
 self.data = '#'
 self.weight = -1
 self.parent = None
 self.lchild = None
 self.rchild = None


class HuffmanTree(object):
 def __init__(self, data_list):
 self.nodes = []
 # 按權重從大到小進行排列
 for val in data_list:
  newnode = HuffmanTreeNode()
  newnode.data = val[0]
  newnode.weight = val[1]
  self.nodes.append(newnode)
 self.nodes = sorted(self.nodes, key=lambda node: node.weight, reverse=True)
 print([(node.data, node.weight) for node in self.nodes])

 def CreateHuffmanTree(self):
 # 這里注意區(qū)分
 # TreeNode = self.nodes[:] 變量TreeNode, 這個相當于深拷貝, TreeNode變化不影響nodes
 # TreeNode = self.nodes 指針TreeNode與nodes共享一個地址, 相當于淺拷貝, TreeNode變化會影響nodes
 TreeNode = self.nodes[:]
 if len(TreeNode) > 0:
  while len(TreeNode) > 1:
  letfTreeNode = TreeNode.pop()
  rightTreeNode = TreeNode.pop()
  newNode = HuffmanTreeNode()
  newNode.lchild = letfTreeNode
  newNode.rchild = rightTreeNode
  newNode.weight = letfTreeNode.weight + rightTreeNode.weight
  letfTreeNode.parent = newNode
  rightTreeNode.parent = newNode
  self.InsertTreeNode(TreeNode, newNode)
  return TreeNode[0]

 def InsertTreeNode(self, TreeNode, newNode):
 length = len(TreeNode)
 if length > 0:
  temp = length - 1
  while temp >= 0:
  if newNode.weight < TreeNode[temp].weight:
   TreeNode.insert(temp+1, newNode)
   return True
  temp -= 1
 TreeNode.insert(0, newNode)

3. 哈夫曼編碼

在數據通信時，假如我們要發(fā)送“ABCDEFG”“ABCDEFG”“ABCDEFG”這一串信息，我們并不會直接以這種形式進行發(fā)送，而是將其編碼成計算機能夠識別的二進制形式。根據編碼類型可將其分為固定長度編碼和可變長度編碼，顧名思義，固定長度編碼就是編碼后的字符長度都相同，可變長度編碼就是編碼后的字符長度不相同。這兩種類型有什么區(qū)別呢？我們來舉例說明一下：

	A	B	C	D	E	F	G
固定長度編碼	000	001	010	011	100	101	110
可變長度編碼	0	1	01	10	11	101	110

“ABCDEFG”“ABCDEFG”“ABCDEFG”這條信息使用固定長度編碼后的長度為21，使用可變長度編碼后的長度為14，報文變短，報文的傳輸效率會相應的提高。但如果傳送的字符為“BD”“BD”“BD”，按可變長度編碼后的報文為“111”“111”“111”，但是在譯碼是就會出現“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”多種結果，因此采用可變長度編碼時需要注意任一字符不能是其他字符的前綴，符合這樣的可變長度編碼稱為前綴編碼。

報文最短可以引申到二叉樹路徑最短，即構造前綴編碼的實質就是構造一棵哈夫曼樹，通過這種形式獲得的二進制編碼稱為哈夫曼編碼。這里的權值就是報文中字符出現的概率，出現概率越高的字符我們用越短的字符表示。

以下表中的字符及其出現的概率為例來實現哈夫曼編碼：

字符	A	B	C	D	E	F	G	H
出現概率	0.01	0.43	0.15	0.02	0.03	0.21	0.07	0.08
哈夫曼編碼	101010	0	110	101011	10100	111	1011	100

代碼實現就是在哈夫曼樹的基礎上加一個編碼的函數：

 def HuffmanEncode(self, Root):
  TreeNode = self.nodes[:]
  code_result = []
  for index in range(len(TreeNode)):
   temp = TreeNode[index]
   code_leaf = [temp.data]
   code = ''
   while temp is not Root:
    if temp.parent.lchild is temp:
     # 左分支
     code = '0' + code
    else:
     # 右分支
     code = '1' + code
    temp = temp.parent
   code_leaf.append(code)
   code_result.append(code_leaf)
  return code_result

測試結果如下：

if __name__ == '__main__':
 tree_obj = HuffmanTree([('A', 0.01), ('B', 0.43), ('C', 0.15), ('D', 0.02), ('E', 0.03), ('F', 0.21), ('G', 0.07), ('H', 0.08)])
 huf_tree = tree_obj.CreateHuffmanTree()
 huf_code = tree_obj.HuffmanEncode(huf_tree)
 for index in range(len(huf_code)):
  print('{0}: {1}'.format(huf_code[index][0], huf_code[index][1]))