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

2023-07-17 03:04:03 277

前言

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

1.基本概念

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

其中，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)}，它构造出来的哈夫曼树就是下面这棵二叉树：

代码实现：

classHuffmanTreeNode(object):
def__init__(self):
self.data='#'
self.weight=-1
self.parent=None
self.lchild=None
self.rchild=None


classHuffmanTree(object):
def__init__(self,data_list):
self.nodes=[]
#按权重从大到小进行排列
forvalindata_list:
newnode=HuffmanTreeNode()
newnode.data=val[0]
newnode.weight=val[1]
self.nodes.append(newnode)
self.nodes=sorted(self.nodes,key=lambdanode:node.weight,reverse=True)
print([(node.data,node.weight)fornodeinself.nodes])

defCreateHuffmanTree(self):
#这里注意区分
#TreeNode=self.nodes[:]变量TreeNode,这个相当于深拷贝,TreeNode变化不影响nodes
#TreeNode=self.nodes指针TreeNode与nodes共享一个地址,相当于浅拷贝,TreeNode变化会影响nodes
TreeNode=self.nodes[:]
iflen(TreeNode)>0:
whilelen(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)
returnTreeNode[0]

defInsertTreeNode(self,TreeNode,newNode):
length=len(TreeNode)
iflength>0:
temp=length-1
whiletemp>=0:
ifnewNode.weight
3.哈夫曼编码
在数据通信时，假如我们要发送“ABCDEFG”“ABCDEFG”“ABCDEFG”这一串信息，我们并不会直接以这种形式进行发送，而是将其编码成计算机能够识别的二进制形式。根据编码类型可将其分为固定长度编码和可变长度编码，顾名思义，固定长度编码就是编码后的字符长度都相同，可变长度编码就是编码后的字符长度不相同。这两种类型有什么区别呢？我们来举例说明一下：



 
AA
BB
CC
DD
EE
FF
GG




固定长度编码
000000
001001
010010
011011
100100
101101
110110


可变长度编码
00
11
0101
1010
1111
101101
110110



“ABCDEFG”“ABCDEFG”“ABCDEFG”这条信息使用固定长度编码后的长度为21，使用可变长度编码后的长度为14，报文变短，报文的传输效率会相应的提高。但如果传送的字符为“BD”“BD”“BD”，按可变长度编码后的报文为“111”“111”“111”，但是在译码是就会出现“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”“BBB”,“BD”,“DB”多种结果，因此采用可变长度编码时需要注意任一字符不能是其他字符的前缀，符合这样的可变长度编码称为前缀编码。
报文最短可以引申到二叉树路径最短，即构造前缀编码的实质就是构造一棵哈夫曼树，通过这种形式获得的二进制编码称为哈夫曼编码。这里的权值就是报文中字符出现的概率，出现概率越高的字符我们用越短的字符表示。
以下表中的字符及其出现的概率为例来实现哈夫曼编码：



字符
AA
BB
CC
DD
EE
FF
GG
HH




出现概率
0.010.01
0.430.43
0.150.15
0.020.02
0.030.03
0.210.21
0.070.07
0.08


哈夫曼编码
101010101010
00
110110
101011101011
1010010100
111111
10111011
100





 
代码实现就是在哈夫曼树的基础上加一个编码的函数：
defHuffmanEncode(self,Root):
TreeNode=self.nodes[:]
code_result=[]
forindexinrange(len(TreeNode)):
temp=TreeNode[index]
code_leaf=[temp.data]
code=''
whiletempisnotRoot:
iftemp.parent.lchildistemp:
#左分支
code='0'+code
else:
#右分支
code='1'+code
temp=temp.parent
code_leaf.append(code)
code_result.append(code_leaf)
returncode_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)
forindexinrange(len(huf_code)):
print('{0}:{1}'.format(huf_code[index][0],huf_code[index][1]))


总结
到此这篇关于Python描述数据结构学习之哈夫曼树篇的文章就介绍到这了,更多相关Python数据结构之哈夫曼树内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

	AA	BB	CC	DD	EE	FF	GG
固定长度编码	000000	001001	010010	011011	100100	101101	110110
可变长度编码	00	11	0101	1010	1111	101101	110110

字符	AA	BB	CC	DD	EE	FF	GG	HH
出现概率	0.010.01	0.430.43	0.150.15	0.020.02	0.030.03	0.210.21	0.070.07	0.08
哈夫曼编码	101010101010	00	110110	101011101011	1010010100	111111	10111011	100

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

热门推荐

随机推荐