問題:哈夫曼編碼,英文名稱Huffman Coding，有時也翻譯為霍夫曼編碼，在1952年提出的，是最好的編碼方式。哈夫曼編碼在電子通訊方面有著重要的應(yīng)用，同時也廣泛應(yīng)用于數(shù)據(jù)壓縮，其壓縮率通常在20% 90%之間 赫夫曼碼是可變字長編碼(VLC)的一種。哈夫曼樹是最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹。

原理:

假設(shè)有幾個數(shù)字40,10,20,16,14。

首先將這五個數(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(‘請輸入要構(gòu)建哈夫曼樹的字符串:’)# 統(tǒng)計每個字符出現(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é)點類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)

運行結(jié)果:

請輸入要構(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