問題:哈夫曼編碼,英文名稱Huffman Coding，有時(shí)也翻譯為霍夫曼編碼，在1952年提出的，是最好的編碼方式。哈夫曼編碼在電子通訊方面有著重要的應(yīng)用，同時(shí)也廣泛應(yīng)用于數(shù)據(jù)壓縮，其壓縮率通常在20% 90%之間 赫夫曼碼是可變字長(zhǎng)編碼(VLC)的一種。哈夫曼樹是最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹。
原理:
假設(shè)有幾個(gè)數(shù)字40,10,20,16,14。
首先將這五個(gè)數(shù)字按照從小到大的順序排列：10, 14，16，20, 40。
構(gòu)建哈夫曼樹：
1.首先選取10,14
2.重新排序：16,20,24,40
3.重新排序24,36,40,60
4.按照二叉樹左0右1，構(gòu)建哈夫曼樹
所以最終得到數(shù)字10的編碼為100，數(shù)字14的編碼為101，數(shù)字16的編碼為110，數(shù)字20的編碼為111，數(shù)字40的編碼為0。
代碼：
from heapq import *inp = input(‘請(qǐng)輸入要構(gòu)建哈夫曼樹的字符串:’)# 統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻率并生成字典def generate_dict(s): dic = {} for i in s: if i not in dic: dic[i] = 1 else: dic[i] += 1 return dicdic = generate_dict(inp)# 節(jié)點(diǎn)類class Node: def __init__(self, name=None, weight=None): self.name = name self.weight = weight self.parent = None self.left = None self.right = None self.id = None # 自定義類的比較 def __lt__(self, other): return int(self.weight) < int(other.weight)# 按權(quán)值排序def sort(list): return sorted(list, key=lambda Node: Node.weight)def generate_node2(dic): lis = [] for i in dic: newNode = Node(i, dic[i]) heappush(lis, newNode) return lislis = generate_node2(dic)# Huffman編碼2使用堆的方式def HuffmanTree2(lis): global id while len(lis) != 1: a = heappop(lis) b = heappop(lis) new = Node() new.weight = a.weight + b.weight new.left, new.right = a, b a.parent = new b.parent = new heappush(lis, new) return lislis = HuffmanTree2(lis)node = lis[0]# 定義前序遍歷方法并執(zhí)行一定的操作def pre_order(root, code): if root is None: code = code[:-1] return pre_order(root.left, code + '0') if root.name is not None: print(root.name, '的權(quán)重為', root.weight, '編碼為', code) pre_order(root.right, code + '1')code = ''print('構(gòu)造的哈夫曼樹為:')pre_order(node, code)
運(yùn)行結(jié)果:
請(qǐng)輸入要構(gòu)建哈夫曼樹的字符串:12908755343298構(gòu)造的哈夫曼樹為:1 的權(quán)重為 1 編碼為 0007 的權(quán)重為 1 編碼為 0015 的權(quán)重為 2 編碼為 0109 的權(quán)重為 2 編碼為 0112 的權(quán)重為 2 編碼為 1000 的權(quán)重為 1 編碼為 10104 的權(quán)重為 1 編碼為 10118 的權(quán)重為 2 編碼為 1103 的權(quán)重為 2 編碼為 111
