[python]Huffman Encoding哈夫曼编码

作者:杭州车成汽车事务代理服务部 来源:www.guohuicar.com 发布时间:2017-09-08 19:12:09
[python]Huffman Encoding哈夫曼编码 #Huffman Encoding #Tree-Node Type class Node: def __init__(self,freq): self.left = None self.right = None self.father = None self.freq = freq def isLeft(self): return self.father.left == self #create nodes创建叶子节点 def createNodes(freqs): return [Node(freq) for freq in freqs] #create Huffman-Tree创建Huffman树 def createHuffmanTree(nodes): queue = nodes[:] while len(queue) > 1: queue.sort(key=lambda item:item.freq) node_left = queue.pop(0) node_right = queue.pop(0) node_father = Node(node_left.freq + node_right.freq) node_father.left = node_left node_father.right = node_right node_left.father = node_father node_right.father = node_father queue.append(node_father) queue[0].father = None return queue[0] #Huffman编码 def huffmanEncoding(nodes,root): codes = [''] * len(nodes) for i in range(len(nodes)): node_tmp = nodes[i] while node_tmp != root: if node_tmp.isLeft(): codes[i] = '0' + codes[i] else: codes[i] = '1' + codes[i] node_tmp = node_tmp.father return codes if __name__ == '__main__': #chars = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N'] #freqs = [10,4,2,5,3,4,2,6,4,4,3,7,9,6] chars_freqs = [('C', 2), ('G', 2), ('E', 3), ('K', 3), ('B', 4), ('F', 4), ('I', 4), ('J', 4), ('D', 5), ('H', 6), ('N', 6), ('L', 7), ('M', 9), ('A', 10)] nodes = createNodes([item[1] for item in chars_freqs]) root = createHuffmanTree(nodes) codes = huffmanEncoding(nodes,root) for item in zip(chars_freqs,codes): print 'Character:%s freq:%-2d encoding: %s' % (item[0][0],item[0][1],item[1])

输出结果

>>> Character:C freq:2 encoding: 10100 Character:G freq:2 encoding: 10101 Character:E freq:3 encoding: 0000 Character:K freq:3 encoding: 0001 Character:B freq:4 encoding: 0100 Character:F freq:4 encoding: 0101 Character:I freq:4 encoding: 0110 Character:J freq:4 encoding: 0111 Character:D freq:5 encoding: 1011 Character:H freq:6 encoding: 1110 Character:N freq:6 encoding: 1111 Character:L freq:7 encoding: 001 Character:M freq:9 encoding: 100 Character:A freq:10 encoding: 110 ,站群

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:襄阳网站建设 http://xiangyang.45qun.com

  • 上一篇:WebView自适应
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 杭州车成汽车事务代理服务部 ALL RIGHTS RESERVED.
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100