加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Python > 正文

贪心法--哈夫曼编码

发布时间:2020-12-20 09:50:54 所属栏目:Python 来源:网络整理
导读:现有五个节点:A B C D E以及对应的权值,如何建立一颗huffman树进行哈夫曼编码? 基本思路:每次选取其中最小的两个权值的和作为左右节点,比如0.1+0.15=0.25,再从0.2,0.2,0.25,0.35中选取两个最小的,以此类推。编码的时候,从上往下,如果是左孩子就记

现有五个节点: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
生成节点列表
 createNodes(freqs):
    return [Node(freq) for freq in freqs]
 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]
 huffmanEncoding(nodes,root):
    用于存储每个节点的编码值
    codes=['']*len(nodes)
    for i  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]=1codes[i]
            node_temp=node_temp.parent
     codes
letters_freqs=[(B',10),(ECDA)]
nodes = createNodes([item[1] for item  letters_freqs])
root = createHuffmanTree(nodes)
codes = zip(letters_freqs,codes):
    print("better:{} freq:{} HuffmanCode:{}".format(item[0][0],item[0][1],item[1]))

最后结果:

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读