Python算法之哈夫曼编码

　　问题：哈夫曼编码，英文名称HuffmanCoding，有时也翻译为霍夫曼编码，在1952年提出的，是最好的编码方式。哈夫曼编码在电子通讯方面有着重要的应用，同时也广泛应用于数据压缩，其压缩率通常在2090之间赫夫曼码是可变字长编码（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。
　　代码：fromheapqimportinpinput（请输入要构建哈夫曼树的字符串：）统计每个字符出现的频率并生成字典defgeneratedict（s）：dic｛｝foriins：ifinotindic：dic〔i〕1else：dic〔i〕1returndicdicgeneratedict（inp）节点类classNode：definit（self，nameNone，weightNone）：self。namenameself。weightweightself。parentNoneself。leftNoneself。rightNoneself。idNone自定义类的比较deflt（self，other）：returnint（self。weight）int（other。weight）按权值排序defsort（list）：returnsorted（list，keylambdaNode：Node。weight）defgeneratenode2（dic）：lis〔〕foriindic：newNodeNode（i，dic〔i〕）heappush（lis，newNode）returnlislisgeneratenode2（dic）Huffman编码2使用堆的方式defHuffmanTree2（lis）：globalidwhilelen（lis）！1：aheappop（lis）bheappop（lis）newNode（）new。weighta。weightb。weightnew。left，new。righta，ba。parentnewb。parentnewheappush（lis，new）returnlislisHuffmanTree2（lis）nodelis〔0〕定义前序遍历方法并执行一定的操作defpreorder（root，code）：ifrootisNone：codecode〔：1〕returnpreorder（root。left，code0）ifroot。nameisnotNone：print（root。name，的权重为，root。weight，编码为，code）preorder（root。right，code1）codeprint（构造的哈夫曼树为：）preorder（node，code）
　　运行结果：请输入要构建哈夫曼树的字符串：12908755343298构造的哈夫曼树为：1的权重为1编码为0007的权重为1编码为0015的权重为2编码为0109的权重为2编码为0112的权重为2编码为1000的权重为1编码为10104的权重为1编码为10118的权重为2编码为1103的权重为2编码为111