哈夫曼樹原理

秉著能不寫就不寫的理念，關(guān)于哈夫曼樹的原理及其構(gòu)建，還是貼一篇博客吧。

https://www.jb51.net/article/97396.htm

其大概流程

哈夫曼編碼代碼

            
# 樹節(jié)點類構(gòu)建
class TreeNode(object):
  def __init__(self, data):
    self.val = data[0]
    self.priority = data[1]
    self.leftChild = None
    self.rightChild = None
    self.code = ""
# 創(chuàng)建樹節(jié)點隊列函數(shù)
def creatnodeQ(codes):
  q = []
  for code in codes:
    q.append(TreeNode(code))
  return q
# 為隊列添加節(jié)點元素，并保證優(yōu)先度從大到小排列
def addQ(queue, nodeNew):
  if len(queue) == 0:
    return [nodeNew]
  for i in range(len(queue)):
    if queue[i].priority >= nodeNew.priority:
      return queue[:i] + [nodeNew] + queue[i:]
  return queue + [nodeNew]
# 節(jié)點隊列類定義
class nodeQeuen(object):

  def __init__(self, code):
    self.que = creatnodeQ(code)
    self.size = len(self.que)

  def addNode(self,node):
    self.que = addQ(self.que, node)
    self.size += 1

  def popNode(self):
    self.size -= 1
    return self.que.pop(0)
# 各個字符在字符串中出現(xiàn)的次數(shù)，即計算優(yōu)先度
def freChar(string):
  d ={}
  for c in string:
    if not c in d:
      d[c] = 1
    else:
      d[c] += 1
  return sorted(d.items(),key=lambda x:x[1])
# 創(chuàng)建哈夫曼樹
def creatHuffmanTree(nodeQ):
  while nodeQ.size != 1:
    node1 = nodeQ.popNode()
    node2 = nodeQ.popNode()
    r = TreeNode([None, node1.priority+node2.priority])
    r.leftChild = node1
    r.rightChild = node2
    nodeQ.addNode(r)
  return nodeQ.popNode()

codeDic1 = {}
codeDic2 = {}
# 由哈夫曼樹得到哈夫曼編碼表
def HuffmanCodeDic(head, x):
  global codeDic, codeList
  if head:
    HuffmanCodeDic(head.leftChild, x+'0')
    head.code += x
    if head.val:
      codeDic2[head.code] = head.val
      codeDic1[head.val] = head.code
    HuffmanCodeDic(head.rightChild, x+'1')
# 字符串編碼
def TransEncode(string):
  global codeDic1
  transcode = ""
  for c in string:
    transcode += codeDic1[c]
  return transcode
# 字符串解碼
def TransDecode(StringCode):
  global codeDic2
  code = ""
  ans = ""
  for ch in StringCode:
    code += ch
    if code in codeDic2:
      ans += codeDic2[code]
      code = ""
  return ans
# 舉例
string = "AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA"
t = nodeQeuen(freChar(string))
tree = creatHuffmanTree(t)
HuffmanCodeDic(tree, '')
print(codeDic1,codeDic2)
a = TransEncode(string)
print(a)
aa = TransDecode(a)
print(aa)
print(string == aa)
          

接下來就是一段一段分析代碼

1.樹結(jié)點類的構(gòu)建：

共有5個屬性：結(jié)點的值，結(jié)點的優(yōu)先度，結(jié)點的左子結(jié)點，結(jié)點的右子結(jié)點，結(jié)點值的編碼（這個沒有什么好說的，這些屬性都是被需要的）

2.創(chuàng)建樹結(jié)點隊列函數(shù)：

對于所有的字母結(jié)點，我們將其組成一個隊列，這里使用list列表來完成隊列的功能。將所有樹節(jié)點夠放進列表中，當(dāng)然傳進來的是按優(yōu)先度從小到大已排序的元素列表

3.為隊列添加節(jié)點元素，并保證優(yōu)先度從大到小排列：

當(dāng)有新生成的結(jié)點時，需將其插入列表，并放在合適位置，使隊列依然時按優(yōu)先度從小打到排列的。

4.結(jié)點隊列類定義：

創(chuàng)建類初始化時需要傳進去的是一個列表，列表中的每個元素是由字母與優(yōu)先度組成的元組。元組第一個元素是字母，第二個元素是優(yōu)先度（即在文本中出現(xiàn)的次數(shù)）

類初始化化時，調(diào)用“創(chuàng)建樹結(jié)點隊列函數(shù)”，隊列中的每個元素都是一個樹結(jié)點。

類中還包含一個隊列規(guī)模屬性以及另外兩個操作函數(shù)：添加結(jié)點函數(shù)和彈出結(jié)點函數(shù)。

添加結(jié)點函數(shù)直接調(diào)用之前定義的函數(shù)即可，輸入的參數(shù)為隊列和新結(jié)點，并且隊列規(guī)模加一

彈出第一個元素則直接調(diào)用列表的pop(0)函數(shù)，同時隊列規(guī)模減一

5.計算文本中個字母的優(yōu)先度，即出現(xiàn)的次數(shù)：

定義一個字典，遍歷文本中的每一個字母，若字母不在字典里說明是第一次出現(xiàn)，則定義該字母為鍵，另鍵值為1，若在字典里有，則只需將相應(yīng)的鍵值加一。 遍歷后就得到了每個字母出現(xiàn)的次數(shù)。

6.由哈夫曼樹得到編碼表：

這里定義了兩個全局字典，用于存放字母編碼，一個字典用于編碼，另一個字典用于解碼，這樣程序操作起來比較方便。

這里主要就是遍歷，運用的是二叉樹的中序遍歷。如果明白中序遍歷的化，就能看懂這里的代碼，每遞歸到深一層的時候，就在后面多加一個‘0'（左子樹）或‘1'（右子樹）。

中序遍歷我在上一篇博客中講的還算可以吧，不懂的可以參考一下，否則就可以略過這一段。

這一段是哈夫曼編碼的關(guān)鍵，也是難點，希望能夠好好理解一下，也是對遞歸的一個理解。這一點沒問題的話，我覺得哈夫曼樹真的挺簡單的！！！

7.字符串編碼，字符串解碼：

這兩段我就不詳細說了，應(yīng)為已經(jīng)有編碼與解碼的字典了，所以對應(yīng)每一個字母直接在字典里找就好了，而且字典的尋找速度還是相當(dāng)快的。

差不多了，例子就不舉了，確實哈夫曼樹比之前的什么八皇后問題還有KMP問題簡單多了。

最后向Huffman大神致敬，祝各位學(xué)有所成。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。