前言:
眼前看官们对“c语言实现哈夫曼编码”大约比较注意,各位老铁们都需要知道一些“c语言实现哈夫曼编码”的相关资讯。那么小编同时在网络上网罗了一些关于“c语言实现哈夫曼编码””的相关文章,希望同学们能喜欢,各位老铁们快快来了解一下吧!#头条创作挑战赛#
哈夫曼编码树使用不定长编码方式,对于常用信息使用较短的编码,不常用信息使用较长的编码,从而整体提高信息传送效率。比如我们要传送A、B、C、D、E、F、G、H8个字母,定长编码就会使用3位表示,从000到111,使用哈夫曼编码的话可以用0表示A、用1表示B、用10表示C、用11表示D……。那怎么解读收到的信息呢?011011,可以解读为ABCD也可以解读为ADAD,所以必须要求任何字符编码都不能是其他编码的前缀,从而保证译码的唯一性。当然你可以加入分隔符,不过为了尽可能快地传递信息,我们并不会采用。
哈夫曼编码通过构造哈夫曼编码树来完成。假设现在有词和词频信息如下:A:25,B:13,C:12,D:9,E:8,F:6,G:3,H:1,我们可以采用自上而下的方式构建,如图所示,但是你会发现为了避免前缀编码,我们需要反复修改树。以下第一幅图A是B和C的前缀编码,修改为第二幅图B又变成了C的前缀编码,还需要继续修改。
哈夫曼编码使用贪心算法采用自下而上的构建方式,能找出当前看起来最好的选择,结果不是唯一的。虽然贪心算法很可能得出局部最佳而不是全局最优解,不过在数学上可以证明哈夫曼编码的最优性。构建编码树首先要找出所有字符频率最低的两个合并,接着删除这两个原值,添加合并结果,继续比较剩下所有字符的频率,找出最小的两个再次合并,直到所有的频率都合并完成,编码树也就构建好了,过程如图所示。
构建哈夫曼树以后,我们把相应的字母填入树中,从根节点出发依次访问叶子结点,走左分支加0,走右分支加1,最终完成变长的哈夫曼编码如下所示。
class HuffmanNode: #建立哈夫曼结点类,参数data表示字符,weight是出现次数 def __init__(self,data,weight): self.data=data self.weight=weight self.parent=None self.lc=None self.rc=None#parent、lc、rc分别表示父亲、左子树、右子树,初始时均为空。
class HuffmanTree: #构建哈夫曼编码树的类,参数data表示字符和出现次数的集合 def __init__(self,data): #data是编码字符与出现次数的集合,('A',25) nodes=[HuffmanNode(d,w) for d,w in data] self.index={} while len(nodes)>1: nodes=sorted(nodes,key=lambda x:x.weight) s=HuffmanNode(None,nodes[0].weight+nodes[1].weight) s.lc=nodes[0] s.rc=nodes[1] nodes[0].parent=nodes[1].parent=s nodes=nodes[2:] nodes.append(s) self.root=nodes[0] self.calIndex(self.root,'') #递归计算每个字符的哈夫曼编码并保存#主程序 data=[('A',25),('B',13),('C',12),('D',9),('E',8),('F',6),('G',3),('H',1)]t=HuffmanTree(data)
主程序把待编码的字符和相应出现的次数放在一个列表中,调用哈夫曼树的类,参数就是该列表。代码第三行从类的参数data读入数据,nodes列表把读入的数据均存为哈夫曼结点类型,每个结点的data属性中存放待编码字符,变量w存放其出现的次数。
第五行读取列表nodes中的元素,依次执行以下①到④步,直到列表中只有一个元素为止,结束循环。
①第6行按每个结点中weight的大小对列表nodes排序,也就保证最前面的元素一定是出现次数最少的。②第7行生成一个新的哈夫曼结点s,data值为空,weight值是列表中前两个元素出现次数之和。③第8行到第10行,建立s和nodes[0]、nodes[1]之间的联系,把nodes[0]设为s的左子树lc,nodes[1]设为右子树rc,这两个元素的父亲parent设为s。④第11行从列表nodes中删除前两个元素,加入新生成的s。至此一轮循环结束,回到第五行判断条件是否满足,如果满足重复执行以上①到④步。以上过程对应文章中第三个动图。
结束循环时nodes列表中只剩下一个结点,第13行代码设该结点为哈夫曼编码树的根节点,到此一棵哈夫曼编码树构建完成。接着利用递归计算读取每个字符的哈夫曼编码。
def calIndex(self,root,str): #读取计算每个字符的哈夫曼编码 if root.data is not None: #保存字符的编码 self.index[root.data]=str else: self.calIndex(root.lc,str+'0') self.calIndex(root.rc,str+'1')
计算哈夫曼编码使用的是深度优先搜索,从根结点出发先沿着左边一直访问,到达叶结点时停止,(因为所有的字符都存放在叶结点上,在中间结点不能实现前缀编码),把得到的编码赋值给相应的字符,接着返回上一级父结点再沿着右边访问直到叶结点,直到完成所有结点的遍历,得到每个字符的编码。
具体代码解释如下,第2行代码判断根节点的data属性是否为空,这里是空的所以跳转到第6行代码递归调用自己 的左子树(访问左子树str+0),得到data为空weight为30的点,因为它的data也为空,所以继续调用它的左子树(访问左子树str+0),这里的左子树是data为B,weight位13的点。data不为空跳转到第4行代码,得到index[B]=00,本次递归结束,返回上次中断的位置第六行代码,继续执行第7行代码。
这里的root也就是B的父结点,判断它的右结点(访问右子树str+1),得到data为空weight为17的点,data再次为空继续调用左子树(访问左子树str+0),找到data为E,weight值为8的点,这时data不为空执行第4行代码,把一路访问生成的值010赋给index[E]。本次递归结束,返回其父亲结点执行第7行代码访问父亲的右子树(访问右子树str+1)得到data为D,weight是9的点,data不为空执行第4句index[D]=011。
def queryHuffmanCode(self,d): if d not in self.index: raise Exception("未编码字符") return self.index[d]#主程序for d,w in data: print('字符%s的哈夫曼编码为:%s'%(d,t.queryHuffmanCode(d)))
主程序调用查询哈夫曼编码函数,查询每一个字符的编码并输出,通过查询字典index里面有没有相应的字符编码,有的话就输出,没有的话返回提示“未编码字符”。整个程序到此结束。
哈夫曼编码树共创建两个类,哈夫曼结点和哈夫曼树,哈夫曼树又定义了3个方法,分别是:完成哈夫曼树构建的、计算字符编码的和查询编码的方法,以上为了讲述方便把代码拆开了,下面给出完整代码,以供大家调试运行。
class HuffmanNode: def __init__(self,data,weight): self.data=data self.weight=weight self.parent=None self.lc=None self.rc=Noneclass HuffmanTree: def __init__(self,data): #data是编码字符与出现次数的集合,('A',25) nodes=[HuffmanNode(d,w) for d,w in data] self.index={} while len(nodes)>1: nodes=sorted(nodes,key=lambda x:x.weight) s=HuffmanNode(None,nodes[0].weight+nodes[1].weight) s.lc=nodes[0] s.rc=nodes[1] nodes[0].parent=nodes[1].parent=s nodes=nodes[2:] nodes.append(s) self.root=nodes[0] self.calIndex(self.root,'') #递归计算每个字符的哈夫曼编码并保存 def calIndex(self,root,str): if root.data is not None: #保存字符的编码 self.index[root.data]=str else: self.calIndex(root.lc,str+'0') self.calIndex(root.rc,str+'1') def queryHuffmanCode(self,d): if d not in self.index: raise Exception("未编码字符") return self.index[d]data=[('A',25),('B',13),('C',12),('D',9),('E',8),('F',6),('G',3),('H',1)]t=HuffmanTree(data)for d,w in data: print('字符%s的哈夫曼编码为:%s'%(d,t.queryHuffmanCode(d)))
标签: #c语言实现哈夫曼编码