专栏首页数据分析与挖掘贪心法--哈夫曼编码

贪心法--哈夫曼编码

现有五个节点:A B C D E以及对应的权值,如何建立一颗huffman树进行哈夫曼编码?

基本思路:每次选取其中最小的两个权值的和作为左右节点,比如0.1+0.15=0.25,再从0.2,0.2,0.25,0.35中选取两个最小的,以此类推。编码的时候,从上往下,如果是左孩子就记为0,右孩子则记为1。

#定义树的结构
class Node:
    def __init__(self,freq):
        self.left = None
        self.right = None
        self.parent = None
        self.freq =freq
    def isLeft(self):
        return self.parent.left == self
#生成节点列表
def createNodes(freqs):
    return [Node(freq) for freq in freqs]
def createHuffmanTree(nodes):
    queue=nodes[:]
    while len(queue)>1:
        #按权值对节点排序
        queue.sort(key=lambda x:x.freq)
        #前两个最小的值出队列
        node_left=queue.pop(0)
        node_right = queue.pop(0)
        node_parent=Node(node_left.freq+node_right.freq)
        node_parent.left=node_left
        node_parent.right=node_right
        node_left.parent = node_parent
        node_right.parent=node_parent
        #生成新的节点,放到队列后
        queue.append(node_parent)
    #队列中最后剩下的元素就是根节点
    queue[0].parent=None
    return queue[0]
def huffmanEncoding(nodes,root):
    #用于存储每个节点的编码值
    codes=['']*len(nodes)
    for i in range(len(nodes)):
        #第i个节点
        node_temp=nodes[i]
        while node_temp !=root:
            if node_temp.isLeft():
                #如果是左节点就加‘0’
                codes[i]='0'+codes[i]
            else:
                #否则加‘1’
                codes[i]='1'+codes[i]
            node_temp=node_temp.parent
    return codes
letters_freqs=[('B',10),('E',15),('C',20),('D',20),('A',35)]
nodes = createNodes([item[1] for item in letters_freqs])
root = createHuffmanTree(nodes)
codes = huffmanEncoding(nodes,root)
for item in zip(letters_freqs,codes):
    print("better:{} freq:{} HuffmanCode:{}".format(item[0][0],item[0][1],item[1]))

最后结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【python-leetcode102-树的宽度遍历】二叉树的层次遍历

    3 / \ 9 20 / \ 15 7 返回其层次遍历结果:

    绝命生
  • 使用vue-cli之使用vue ui指令搭建第一个vue程序(vue-cli 4.2.2)

    绝命生
  • vuejs小例子之天气查询

    说明:使用v-model,v-on点击事件,v-on回车事件,v-for遍历数据,axios发送请求。

    绝命生
  • 使用Prometheus监控Linux系统各项指标

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明...

    Jerry Wang
  • 基于HTML5 Canvas 实现弹出框

      用户鼠标移入时,有弹出框出现,这样的需求很常见。这在处理HTML元素实现时简单,但是如果是对 HTML5 Canvas 构成的图形进行处理,这种方法不再适用...

    HT for Web
  • 基于HTML5 Canvas 实现弹出框

    HT_hightopo
  • What is LRU?

    LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率...

    用户3467126
  • 一日一技:Rsync如何使用SSH Key?

    青南
  • 9月最新184道阿里、百度、腾讯、头条Java面试题合集

    2. 已知sqrt(2)约等于1.414,要求不用数学库,求sqrt(2)精确到小数点后10位

    程序员追风
  • 机械公敌成真?Sophia机器人和联合国秘书长展开对话

    特斯拉执行长马斯克(Elon Musk)和逾百名科技界菁英,日前公开呼吁联合国,应加速禁止人工智能(AI)和机器人技术被用于发展武器,以防止各国展开又一场军备竞...

    机器人网

扫码关注云+社区

领取腾讯云代金券