天天看點

貪心法--哈夫曼編碼

現有五個節點: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]))      

最後結果:

貪心法--哈夫曼編碼

繼續閱讀