Python描述数据结构学习之哈夫曼树篇
前言
本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。
1.基本概念
哈夫曼树
其中,
带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘积。有关带权结点、路径长度的概念请参阅这篇博客。
对于含有
2.构造过程及实现
给定
比如
代码实现:
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.weight3.哈夫曼编码
在数据通信时,假如我们要发送
“ A B C D E F G ”“ABCDEFG”“ABCDEFG”这一串信息,我们并不会直接以这种形式进行发送,而是将其编码成计算机能够识别的二进制形式。根据编码类型可将其分为固定长度编码和可变长度编码,顾名思义,固定长度编码就是编码后的字符长度都相同,可变长度编码就是编码后的字符长度不相同。这两种类型有什么区别呢?我们来举例说明一下:
AA BB CC DD EE FF GG 固定长度编码 000000 001001 010010 011011 100100 101101 110110 可变长度编码 00 11 0101 1010 1111 101101 110110
“ A B C D E F G ”“ABCDEFG”“ABCDEFG”这条信息使用固定长度编码后的长度为21,使用可变长度编码后的长度为14,报文变短,报文的传输效率会相应的提高。但如果传送的字符为 “ B D ”“BD”“BD”,按可变长度编码后的报文为 “ 111 ”“111”“111”,但是在译码是就会出现 “ B B B ” , “ B D ” , “ D B ”“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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。