#头条创作挑战赛#

哈夫曼编码树使用不定长编码方式，对于常用信息使用较短的编码，不常用信息使用较长的编码，从而整体提高信息传送效率。比如我们要传送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)))