每个字符的哈夫曼编码,字符集哈夫曼编码
霍夫曼编码是霍夫曼树的一个应用。霍夫曼编码应用广泛，如JPEG。首先介绍一下什么是霍夫曼树。哈夫曼树，又称最优二叉树，是一种加权路径长度最短的二叉树。树的加权路径长度是树中所有叶节点的权重乘以到根节点的路径长度(如果根节点是0层，则从叶节点到根节点的路径长度就是叶节点的个数)。树的加权路径长度是WPL=(W1*L1 W2*L2 W3*L3.Wn*Ln)，以及n个权重Wi(i=1，2，n)形成一棵有n个叶节点的二叉树，对应叶节点的路径长度为Li(i=1，2，n)。可以证明霍夫曼树的WPL是最小的。
它的压缩率通常在20%到90%之间。Huffman编码算法使用文件中出现的字符的频率表，用0，1字符串建立每个字符的最佳表示。一个包含100，000个字符的文件，每个字符的出现频率不同，如下表所示。
有许多方法可以表示文件中的信息。如果使用0，1代码来表示字符，即每个字符由唯一的0，1字符串表示。如果使用定长编码，需要三位数字代表一个字符，整个档案编码需要30万位数字；如果用变长编码来表示给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，整个文件编码需要(451133 123 163 94 54)1000=224000比特。可以看出，变长码优于定长码方案，总码长减少了25%左右。
前缀码：为每个字符指定一个0，1的字符串作为其代码，并要求任何字符的代码不是其他字符代码的前缀。这种代码称为前缀代码。编码的前缀性质可以使解码方法非常简单；比如001011101可以唯一分解成0，0，101，1101，所以解码为aabe。
解码过程需要方便地取出编码后的前缀，因此需要一个合适的数据结构来表示前缀码。为此，二叉树可以作为前缀码的数据结构：树叶代表给定的字符；从根到叶的路径作为字符的前缀码；代码中每个位的0或1充当“路标”,分别指示节点向左还是向右。
从上图可以看出，代表最优前缀码的二叉树始终是一棵完全二叉树，即树中的任意节点都有两个儿子。图A表明定长编码方案不是最优的，其编码的二叉树不是完全二叉树。一般来说，如果C是一个编码字符集，二叉树中只有C叶来指示它的最佳前缀码。每片叶子对应字符集中的一个字符，二叉树有C-1个内部节点。
给定编码字符集C和频率分布F，即C中的任意字符C以频率f(c)出现在数据文件中。C的前缀码编码方案对应于二叉树T。字符C在树T中的深度被记录为dT(c)。DT(c)也是字符c的前缀码长平均码长定义为：使平均码长达到最小的前缀码编码方案称为C的最优前缀码。
霍夫曼编码步骤：
1.对于给定的n个权重{W1，W2，W3，Wi，Wn}，n棵二叉树的初始集合F={T1，T2，T3，Ti，Tn}形成，其中每个二叉树ti只有一个权为wi的根节点，其左右子树为空。(为了便于在计算机上实现计算方法，一般要求将Ti的权重Wi按升序排列。)
2.选取F中根节点权重最小的两棵树作为新构造的二叉树的左右子树，新二叉树的根节点权重为其左右子树的根节点之和。
3.从F中删除这两棵树，并将这个新的二叉树也以升序添加到集合F中。
4.重复第二步和第三步，直到集合f中只剩下一棵二叉树。
简单的理解是，如果我有五个字符，A、B、C、D、E，出现的频率(即权重)分别为5、4、3、2、1，那么我们的第一步是取两个最小权重作为左右子树构造一棵新树，即取1和2组成一棵新树，其节点为1 ^ 2=3，如图：
虚线是新生成的节点。第二步，把新生成的权值为3的节点放入剩下的集合中，这样集合就变成{5，4，3，3}。按照第二步，取最小的两个权值组成新的树，如图：
然后依次建立霍夫曼树，如下图所示：
对应于每个权重替换的字符如下：
所以各字符对应的编码为：A-11、B-10、C-00、D-011、E-010
沉默的曲奇编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。
大蟒实现
#!/usr/唠叨的金鱼/env python# -*-编码：utf-8 -*- 设计算法，给一个字符串进行二进制编码，使得编码后字符串的长度最短订单()函数就是用来返回单个字符的美国信息交换标准码值(0-255)或者采用双字节对字符进行编码数值()chr()函数是输入一个整数【0,255】返回其对应的美国信息交换标准码符号 def CalFrequency(src，pw height):如果len(src)==0:返回范围内的I(len(src)):if order(src[I])不是none:pw height[ord(src[I])]=1 # print( origin pw height ，pw height)def GetCharFreqs(pw height，chars_frequs):对于范围内的j(len(pw height)):if pw eight[j]！=0: # print(字符：，chr(j)，- ASCII:，j，-频数，p weight[j])chars _ frequs。append(tuple((chr(j)，p weight[j]))print(字符出现频数：，chars _ frequs)return chars _ frequs # Tree-Node type class Node:def _ _ init _ _(self，freq):self。左=无自我。右=无我。父亲=无我。freq=freq def is left(self):返回自我。父亲。left==self #创建节点创建叶子节点def创建节点(频率):return[频率中频率的node(freq)#创建霍夫曼树创建哈夫曼（名字)树def CreateHuffmanTree(nodes):queue=nodes[:]而len(queue)1:queue。排序(key=lambda item:item。Node _ left=queue。pop(0)Node _ right=queue。pop(0)Node _ father=Node(Node _ left。频率节点_右。freq)Node _ father。left=Node _ left Node _ father。右=节点_右节点_左。父=节点_节点队列。追加(Node _ father)队列[0].父亲=无返回队列[0]#霍夫曼编码def HuffmanCoding(nodes，root):codes=[ ]* len(nodes)for I in range(len(nodes)):node _ tmp=nodes[I]while node _ tmp！=root:if node _ tmp。is left():codes[I]= 0 codes[I]else:codes[I]= 1 codes[I]node _ tmp=node _ tmp。如果_ _ name _ _= _ _ main _ _ :MAX _ SIZE=256 src=则返回父代码当你老了，头发灰白，睡意全消， \ 在炉火边打盹，取下这本书，\ 慢慢地读，梦见你的眼睛曾经的柔和的神色，梦见它们深邃的影子；\ 有多少人爱你欢乐优雅的时刻，\ 爱你的美貌，假意或真心，\ 但只有一个人爱你朝圣者的灵魂，\ 爱你衰老的脸上的痛苦；\ \ 在灼热的壁炉旁弯下腰，\ 略带忧伤地低语，爱是如何消逝的\ \ 在头顶的群山上踱步\ \ 把脸藏在群星之中. pw height=[0]* MAX _ SIZE #声明权重数组校准频率(src，pw重量)#计算每个字符出现次数chars _ frequs=[]chars _ frequs=GetCharFreqs(pw weight，chars_frequs) #计算出现字符频数nodes=create nodes([item[1]for item in chars _ frequs])root=CreateHuffmanTree(nodes)codes=Huffman coding(nodes，root) for item in zip(chars_frequs，codes):print( Character:% s freq:%-2d编码：% s“%(项目[0][0]，项目[0][1]，项目[1]))
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。