Python描述数据结构学习之哈夫曼树篇_Python

前言

本篇章主要介绍哈夫曼树及哈夫曼编码，包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码，并用Python实现。

1. 基本概念

哈夫曼树(Huffman(Huffman(Huffman Tree)Tree)Tree)，又称为最优二叉树，指的是带权路径长度最小的二叉树。树的带权路径常记作：

Python描述数据结构学习之哈夫曼树篇

其中，nnn为树中叶子结点的数目，wkw_kwk为第kkk个叶子结点的权值，lkl_klk为第kkk个叶子结点与根结点的路径长度。

带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘积。有关带权结点、路径长度的概念请参阅这篇博客。

对于含有nnn个叶子结点的哈夫曼树，其共有2n−12n-12n−1个结点。因为在构造哈夫曼树的过程中，每次都是以两颗二叉树为子树创建一棵新的二叉树，因此哈夫曼树中不存在度为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中；继续重复上述操作，直至集合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)}，它构造出来的哈夫曼树就是下面这棵二叉树：

Python描述数据结构学习之哈夫曼树篇

代码实现：

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

									 # 这里注意区分

									 # 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. 哈夫曼编码

在数据通信时，假如我们要发送“ABCDEFG”“ABCDEFG”“ABCDEFG”这一串信息，我们并不会直接以这种形式进行发送，而是将其编码成计算机能够识别的二进制形式。根据编码类型可将其分为固定长度编码和可变长度编码，顾名思义，固定长度编码就是编码后的字符长度都相同，可变长度编码就是编码后的字符长度不相同。这两种类型有什么区别呢？我们来举例说明一下：

	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

Python描述数据结构学习之哈夫曼树篇

代码实现就是在哈夫曼树的基础上加一个编码的函数：

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