前言

本篇章主要介紹哈夫曼樹及哈夫曼編碼，包括哈夫曼樹的一些基本概念、構(gòu)造、代碼實(shí)現(xiàn)以及哈夫曼編碼，并用Python實(shí)現(xiàn)。

1. 基本概念

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

其中，$$nnn為樹中葉子結(jié)點(diǎn)的數(shù)目，$$wkw_kwk​為第$$kkk個(gè)葉子結(jié)點(diǎn)的權(quán)值，$$lkl_klk​為第$$kkk個(gè)葉子結(jié)點(diǎn)與根結(jié)點(diǎn)的路徑長(zhǎng)度。

帶權(quán)路徑長(zhǎng)度是帶權(quán)結(jié)點(diǎn)和根結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)值的乘積。有關(guān)帶權(quán)結(jié)點(diǎn)、路徑長(zhǎng)度的概念請(qǐng)參閱這篇博客。

對(duì)于含有$$nnn個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其共有$$2n−12n-12n−1個(gè)結(jié)點(diǎn)。因?yàn)樵跇?gòu)造哈夫曼樹的過程中，每次都是以兩顆二叉樹為子樹創(chuàng)建一棵新的二叉樹，因此哈夫曼樹中不存在度為1的結(jié)點(diǎn)，即$$n1=0n_1=0n1​=0，由二叉樹的性質(zhì)可知，葉子結(jié)點(diǎn)數(shù)目$$n0=n2+1n_0=n_2+1n0​=n2​+1，所以$$n2=n0−1n_2=n_0-1n2​=n0​−1，總結(jié)點(diǎn)數(shù)目為$$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. 構(gòu)造過程及實(shí)現(xiàn)

給定$$nnn棵僅含根結(jié)點(diǎn)的二叉樹$$T1,T2,…,TnT_1,T_2,\dots,T_nT1​,T2​,…,Tn​，它們的權(quán)值分別為$$w1,w2,…,wnw_1,w_2,\dots,w_nw1​,w2​,…,wn​，將它們放入到一個(gè)集合$$FFF中，即$$F={T1,T2,…,Tn}F=\{T_1,T_2,\dots,T_n\}F={T1​,T2​,…,Tn​}；然后在集合$$FFF中選取兩棵權(quán)值最小的根結(jié)點(diǎn)構(gòu)造一棵新的二叉樹，使新二叉樹的根結(jié)點(diǎn)的權(quán)值等于其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；再然后將選中的那兩個(gè)結(jié)點(diǎn)從集合$$FFF中刪除，將新的二叉樹添加到$$FFF中；繼續(xù)重復(fù)上述操作，直至集合$$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)}，它構(gòu)造出來的哈夫曼樹就是下面這棵二叉樹：

代碼實(shí)現(xiàn)：

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 = []
 # 按權(quán)重從大到小進(jìn)行排列
 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, 這個(gè)相當(dāng)于深拷貝, TreeNode變化不影響nodes
 # TreeNode = self.nodes 指針TreeNode與nodes共享一個(gè)地址, 相當(dāng)于淺拷貝, TreeNode變化會(huì)影響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. 哈夫曼編碼

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

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

報(bào)文最短可以引申到二叉樹路徑最短，即構(gòu)造前綴編碼的實(shí)質(zhì)就是構(gòu)造一棵哈夫曼樹，通過這種形式獲得的二進(jìn)制編碼稱為哈夫曼編碼。這里的權(quán)值就是報(bào)文中字符出現(xiàn)的概率，出現(xiàn)概率越高的字符我們用越短的字符表示。

以下表中的字符及其出現(xiàn)的概率為例來實(shí)現(xiàn)哈夫曼編碼：

代碼實(shí)現(xiàn)就是在哈夫曼樹的基礎(chǔ)上加一個(gè)編碼的函數(shù)：

 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

測(cè)試結(jié)果如下：

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]))

總結(jié)

到此這篇關(guān)于Python描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之哈夫曼樹篇的文章就介紹到這了,更多相關(guān)Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論