Python算法之哈夫曼编码

　　问题:哈夫曼编码,英文名称Huffman Coding，有时也翻译为霍夫曼编码，在1952年提出的，是最好的编码方式。哈夫曼编码在电子通讯方面有着重要的应用，同时也广泛应用于数据压缩，其压缩率通常在20% 90%之间 赫夫曼码是可变字长编码(VLC)的一种。哈夫曼树是最优二叉树， 带权路径长度最小的二叉树。
　　原理:
　　假设有几个数字40,10,20,16,14。
　　首先将这五个数字按照从小到大的顺序排列：10, 14，16，20, 40。
　　构建哈夫曼树：
　　1.首先选取10,14
　　2.重新排序：16,20,24,40
　　3.重新排序24,36,40,60
　　4.按照二叉树左0右1，构建哈夫曼树
　　所以最终得到数字10的编码为100，数字14的编码为101，数字16的编码为110，数字20的编码为111，数字40的编码为0。
　　代码：from heapq import *  inp = input(＂请输入要构建哈夫曼树的字符串:＂)   # 统计每个字符出现的频率并生成字典 def generate_dict(s):     dic = {}     for i in s:         if i not in dic:             dic[i] = 1         else:             dic[i] += 1     return dic   dic = generate_dict(inp)   # 节点类 class Node:     def __init__(self, name=None, weight=None):         self.name = name         self.weight = weight         self.parent = None         self.left = None         self.right = None         self.id = None      # 自定义类的比较     def __lt__(self, other):         return int(self.weight) < int(other.weight)   # 按权值排序 def sort(list):     return sorted(list, key=lambda Node: Node.weight)   def generate_node2(dic):     lis = []     for i in dic:         newNode = Node(i, dic[i])         heappush(lis, newNode)     return lis   lis = generate_node2(dic)   # Huffman编码2使用堆的方式 def HuffmanTree2(lis):     global id     while len(lis) != 1:         a = heappop(lis)         b = heappop(lis)         new = Node()         new.weight = a.weight + b.weight         new.left, new.right = a, b          a.parent = new         b.parent = new          heappush(lis, new)     return lis   lis = HuffmanTree2(lis) node = lis[0]   # 定义前序遍历方法并执行一定的操作 def pre_order(root, code):     if root is None:         code = code[:-1]         return     pre_order(root.left, code + ＂0＂)     if root.name is not None:         print(root.name, ＂的权重为＂, root.weight, ＂编码为＂, code)     pre_order(root.right, code + ＂1＂)   code = ＂＂ print(＂构造的哈夫曼树为:＂) pre_order(node, code)
　　运行结果:请输入要构建哈夫曼树的字符串:12908755343298 构造的哈夫曼树为: 1 的权重为 1 编码为 000 7 的权重为 1 编码为 001 5 的权重为 2 编码为 010 9 的权重为 2 编码为 011 2 的权重为 2 编码为 100 0 的权重为 1 编码为 1010 4 的权重为 1 编码为 1011 8 的权重为 2 编码为 110 3 的权重为 2 编码为 111