分類目錄：《算法設計與分析》總目錄
赫夫曼編碼可以很有效地壓縮資料：通常可以節省20%~90%的空間，具體壓縮率依賴于資料的特性。我們将待壓縮資料看做字元序列。根據每個字元的出現頻率，赫夫曼貪心算法構造出字元的最優二進制表示。
假定我們希望壓縮一個10萬個字元的資料檔案。下圖給出了檔案中所出現的字元和它們的出現頻率。也就是說，檔案中隻出現了6個不同字元，其中字元a出現了45000次。
我們有很多方法可以表示這個檔案的資訊。在本文中，我們考慮一種二進制字元編碼（或簡稱編碼）的方法，每個字元用一個唯一的二進制串表示，稱為碼字。如果使用定長編碼，需要用3位來表示6個字元：
a
=
000
,
b
=
001.
⋯
,
f
=
101
a=000, b=001. \cdots, f=101
a=000,b=001.⋯,f=101。這種方法需要300000個二進制位來編碼檔案。
變長編碼（ variable-length code）可以達到比定長編碼好得多的壓縮率，其思想是賦予高頻字元短碼字，賦予低頻字元長碼字。上圖顯示了本例的一種變長編碼：1位的串0表示a，4位的串1100表示f。是以，這種編碼表示此檔案共需
(
45
×
1
+
13
×
3
+
12
×
3
+
16
×
3
+
9
×
4
+
5
⋅
4
)
×
1000
=
224000
(45\times1+13\times3+12\times3+16\times3+9\times4+5·4)\times1000=224000
(45×1+13×3+12×3+16×3+9×4+5⋅4)×1000=224000位。與定長編碼相比節約了25%的空間。實際上，我們将看到，這是此檔案的最優字元編碼。
我們這裡隻考慮所謂字首碼（prefix code），即沒有任何碼字是其他碼字的字首。雖然我們這裡不會證明，但與任何字元編碼相比，字首碼确實可以保證達到最優資料壓縮率，是以我們隻關注字首碼，不會喪失一般性。
任何二進制字元碼的編碼過程都很簡單，隻要将表示每個字元的碼字連接配接起來即可完成檔案壓縮。例如，使用上圖所示的變長字首碼，我們可以将3個字元的檔案
abc
編碼為0·101·100（0101100），“·”表示連結操作。
字首碼的作用是簡化解碼過程。由于沒有碼字是其他碼字的字首，編碼檔案的開始碼字是無歧義的。我們可以簡單地識别出開始碼字，将其轉換回原字元，然後對編碼檔案剩餘部分重複。這種解碼過程。在我們的例子中，二進制串001011101可以唯一地解析為0·0·101·1101，解碼為
aabe
。
解碼過程需要字首碼的一種友善的表示形式，以便我們可以容易地截取開始碼字。一種二叉樹表示可以滿足這種需求，其葉結點為給定的字元。字元的二進制碼字用從根結點到該字元葉結點的簡單路徑表示，其中0意味着“轉向左孩子”，1意味着“轉向右孩子”。下圖給出了兩個編碼示例的二叉樹表示。注意，編碼樹并不是二叉搜尋樹，因為葉結點并未有序排列，而内部結點并不包含字元關鍵字。
檔案的最優編碼方案總是對應一棵滿二叉樹，即每個非葉結點都有兩個孩子結點。前文給出的定長編碼執行個體不是最優的，因為它的二叉樹表示并非滿二叉樹，如上圖(a)所示：它包含以10開頭的碼字，但不包含以11開頭的碼字。現在我們可以隻關注滿二叉樹了，是以可以說，若
C
C
C為字母表且所有字元的出現頻率均為正數，則最優字首碼對應的樹恰有
∣
C
∣
|C|
∣C∣個葉結點，每個葉結點對應字母表中一個字元，且恰有
∣
C
∣
−
1
|C|-1
∣C∣−1個内部結點。
給定一棵對應字首碼的樹
T
T
T，我們可以容易地計算出編碼一個檔案需要多少個二進制位。對于字母表
C
C
C中的每個字元
c
c
c，令屬性
c.freq
表示
c
c
c在檔案中出現的頻率，令
dr(c)
表示
c
c
c的葉結點在樹中的深度。注意，
dr(c)
也是字元
c
c
c的碼字的長度。則編碼檔案需要：
B
(
t
)
=
∑
c
∈
C
c
.
f
r
e
q
×
d
r
(
c
)
B(t)=\sum_{c\in C}c.freq\times dr(c)
B(t)=c∈C∑c.freq×dr(c)
個二進制位，我們将
B
(
t
)
B(t)
B(t)定義為
T
T
T的代價。
構造赫夫曼編碼赫夫曼設計了一個貪心算法來構造最優字首碼，被稱為赫夫曼編碼（ Huffman code）。它的正确性證明也依賴于貪心選擇性質和最優子結構。接下來，我們并不是先證明這些性質成立然後再設計算法，而是先設計算法。這樣做可以幫助我們明确算法是如何做出貪心選擇的。
class HuffNode(object):
"""
定義一個HuffNode虛類，裡面包含兩個虛方法：
1. 擷取節點的權重函數
2. 擷取此節點是否是葉節點的函數
"""
def get_wieght(self):
raise NotImplementedError(
"The Abstract Node Class doesn't define 'get_wieght'")
def isleaf(self):
raise NotImplementedError(
"The Abstract Node Class doesn't define 'isleaf'")
class LeafNode(HuffNode):
"""
樹葉節點類
"""
def __init__(self, value=0, freq=0,):
"""
初始化 樹節點 需要初始化的對象參數有 ：value及其出現的頻率freq
"""
super(LeafNode, self).__init__()
# 節點的值
self.value = value
self.wieght = freq
def isleaf(self):
"""
基類的方法，傳回True，代表是葉節點
"""
return True
def get_wieght(self):
"""
基類的方法，傳回對象屬性 weight，表示對象的權重
"""
return self.wieght
def get_value(self):
"""
擷取葉子節點的 字元 的值
"""
return self.value
class IntlNode(HuffNode):
"""
中間節點類
"""
def __init__(self, left_child=None, right_child=None):
"""
初始化 中間節點 需要初始化的對象參數有 ：left_child, right_chiled, weight
"""
super(IntlNode, self).__init__()
# 節點的值
self.wieght = left_child.get_wieght() + right_child.get_wieght()
# 節點的左右子節點
self.left_child = left_child
self.right_child = right_child
def isleaf(self):
"""
基類的方法，傳回False，代表是中間節點
"""
return False
def get_wieght(self):
"""
基類的方法，傳回對象屬性 weight，表示對象的權重
"""
return self.wieght
def get_left(self):
"""
擷取左孩子
"""
return self.left_child
def get_right(self):
"""
擷取右孩子
"""
return self.right_child
class HuffTree(object):
"""
huffTree
"""
def __init__(self, flag, value =0, freq=0, left_tree=None, right_tree=None):
super(HuffTree, self).__init__()
if flag == 0:
self.root = LeafNode(value, freq)
else:
self.root = IntlNode(left_tree.get_root(), right_tree.get_root())
def get_root(self):
"""
擷取huffman tree 的根節點
"""
return self.root
def get_wieght(self):
"""
擷取這個huffman樹的根節點的權重
"""
return self.root.get_wieght()
def traverse_huffman_tree(self, root, code, char_freq):
"""
利用遞歸的方法周遊huffman_tree，并且以此方式得到每個 字元 對應的huffman編碼
儲存在字典 char_freq中
"""
if root.isleaf():
char_freq[root.get_value()] = code
print ("it = %c and freq = %d code = %s")%(chr(root.get_value()),root.get_wieght(), code)
return None
else:
self.traverse_huffman_tree(root.get_left(), code+'0', char_freq)
self.traverse_huffman_tree(root.get_right(), code+'1', char_freq)
def buildHuffmanTree(list_hufftrees):
"""
構造huffman樹
"""
while len(list_hufftrees) >1 :
# 1. 按照weight 對huffman樹進行從小到大的排序
list_hufftrees.sort(key=lambda x: x.get_wieght())
# 2. 跳出weight 最小的兩個huffman編碼樹
temp1 = list_hufftrees[0]
temp2 = list_hufftrees[1]
list_hufftrees = list_hufftrees[2:]
# 3. 構造一個新的huffman樹
newed_hufftree = HuffTree(1, 0, 0, temp1, temp2)
# 4. 放入到數組當中
list_hufftrees.append(newed_hufftree)
# last. 數組中最後剩下來的那棵樹，就是構造的Huffman編碼樹
return list_hufftrees[0]
return list_hufftrees[0]