在學習 word2vec 時,首先接觸到的就是 Huffman 編碼,這裡簡單記錄一下學習内容。
目錄
一、簡介
二、Huffman樹
(一)基礎術語
(二)建構
三、Huffman編碼
四、代碼
(一)python
(二)結果
一、簡介
哈夫曼編碼(Huffman Coding),又稱霍夫曼編碼,是一種編碼方式,哈夫曼編碼是可變字長編碼(VLC)的一種。是 Huffman 于 1952 年提出一種編碼方法,該方法完全依據字元出現機率來構造異字頭的平均長度最短的碼字,有時稱之為最佳編碼,一般就叫做Huffman 編碼(有時也稱為霍夫曼編碼)[1]。
首先,為介紹引入 Huffman 編碼的重要性,這裡介紹一種簡單的 word2vec 方法:One-Hot 編碼。
One-Hot 編碼即獨熱編碼,又稱一位有效編碼,其方法是使用
位狀态寄存器來對
個狀态進行編碼,每個狀态都有它獨立的寄存器位,并且在任意時候,其中隻有一位有效。舉個例子,“冬天的雨和夏天的雪”,這句中存在的詞有“冬天”、“夏天”、“雨”、“雪”、“和”、“的”,即
,故我們分别編碼得:[100000]、[010000]、[001000]、[000100]、[000010]、[000001]。
這種編碼方式存在離散稀疏問題,比如當語料庫的十分龐大時,得到的編碼向量會過于稀疏,并且會造成次元災難。
Huffman 編碼給出了一種解決方案,它是一種用于無損資料壓縮的熵編碼(權編碼)算法。
二、Huffman樹
給定
個權值作為
個葉子結點,構造一棵二叉樹,若該樹的帶權路徑長度達到最小,稱這樣的二叉樹為最優二叉樹,也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹,權值較大的結點離根較近[2]。
哈夫曼樹又稱為最優樹,這裡先給出一個哈夫曼樹便于了解下面概念(圖1 )。
圖1:哈夫曼樹
(一)基礎術語
1. 路徑和路徑長度
在一棵樹中,從一個結點往下可以達到的子或孫子結點之間的通路(不可逆向、橫向傳遞),稱為路徑。通路中分支的數目稱為路徑長度(等同于通過經過的層數)。若規定根結點的層數為
,則從根結點到第
層結點的路徑長度為
。
圖1 中,權重為 38 的結點為根結點,以權重為 4 結點為例,其路徑為 38→23→9→4,路徑長度為 3 。
2. 結點的權及帶權路徑長度
若将樹中結點賦予一個有着某種含義的數值,則這個數值稱為該結點的權。結點的帶權路徑長度為:從根結點到該結點之間的路徑長度與該結點的權的乘積。
圖1 中,權重為 4 結點的帶權路徑長度為
。
3. 樹的帶權路徑長度
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和,記為 WPL 。
。
圖1 中,樹的帶權路徑長度為
。
(二)建構
假設有
個權值,則構造出的哈夫曼樹有
個葉子結點。
個權值分别設為
,則哈夫曼樹的構造規則為:
1. 将
看成是有
棵樹的森林(每棵樹僅有一個結點);
2. 在森林中選出兩個根結點的權值最小的樹合并,作為一棵新樹的左、右葉子結點,且新樹的根結點權值為其左、右葉子結點權值之和;
3. 從森林中删除選取的兩棵樹,并将新樹加入森林(新樹隻觀察其合并之後的根結點,不再考慮其葉子結點);
4. 重複2、3步,直到森林中隻剩一棵樹為止,該樹即為所求得的哈夫曼樹。
下面給出一個具體例子,友善了解。
例:假設我們在一個文本中發現“冬天”、“夏天”、“雨”、“雪”、“和”、“的”這六個詞出現的次數分别是1、3、5、6、8、15。我們以這六個詞為葉子結點,以相應詞頻為權值,構造一棵哈夫曼樹(圖2 )。
圖2:哈夫曼樹構造過程
從圖2 中可以看到,權值越大的結點離根越近。
三、Huffman編碼
這裡直接給出一個定理:在變字長編碼中,如果碼字長度嚴格按照對應符号出現的機率大小逆序排列(從大到小),則其平均碼字長度為最小(證明略,詳細可見[1])。我們就上例中“冬天”、“夏天”、“雨”、“雪”、“和”、“的”六個詞給出 Huffman 編碼方法,具體過程以圖示展示(圖3 ):
圖3:Huffman編碼示意圖
如圖3 所示,我們在每個分支結點分别标注 1 或 0 ,注意,這裡标注時保證整體标準一緻即可(即可左 1 右 0 ,或左 0 右 1 )。最終的 Huffman 編碼結果分别為:
- “冬天”:[1,0,0,0]
- “夏天”:[1,0,0,1]
- “雨”:[1,0,1]
- “雪”:[1,1,0]
- “和”:[1,1,1]
- “的”:[0]
四、代碼
這裡直接給出相關代碼,具體描述請看代碼中的注釋資訊。
(一)python
# 結點對象
class Node:
def __init__(self):
# 權重
self.frequency = 0
# 符号名
self.name = None
# 左結點
self.l_child = None
# 右結點
self.r_child = None
self.code = None
# 對頻數排序
def __lt__(self, other):
return self.frequency < other.frequency
# 從文本中擷取每個符号的頻數
def frequency(origin_path):
# 頻數字典
frequency_dict = dict()
with open(origin_path, 'r') as f:
for line in f.readlines():
line = line.lower()
for j in line:
if j.isalpha():
if j in frequency_dict:
frequency_dict[j] += 1
else:
frequency_dict.update({j: 1})
# 傳回頻數字典
return frequency_dict
# 建立哈夫曼樹
def establish_huffman_tree(frequency_dict):
# 輸出哈夫曼樹的根結點
node_list = []
for j in frequency_dict:
a = Node()
# 頻數
a.frequency = frequency_dict[j]
# 符号名
a.name = j
node_list.append(a)
# while len(node_list) > 1:
# 生成N-1個新結點
for j in range(len(frequency_dict) - 1):
# 從大到小排序
node_list.sort(reverse=True)
# 提取頻數最小的兩個結點,并将它們從node_list中删除
node_1 = node_list.pop()
node_2 = node_list.pop()
# 新結點
new_node = Node()
new_node.frequency = node_1.frequency + node_2.frequency
# 左邊頻數較右邊頻數大
new_node.l_child = node_2
new_node.r_child = node_1
node_list.append(new_node)
# 傳回哈夫曼樹的根結點
return node_list[0]
# 哈夫曼編碼
def encode(base_node, rst_dict, code):
if base_node.name:
rst_dict.update({base_node.name: code})
return
code += '1'
encode(base_node.l_child, rst_dict, code)
code = code[:-1]
code += '0'
encode(base_node.r_child, rst_dict, code)
return rst_dict
# 編碼文本檔案,并寫入新的檔案
def encode_text(code_dict, origin_path, code_text):
string = ''
with open(origin_path, 'r') as f:
for line in f.readlines():
line = line.lower()
for j in line:
if j.isalpha():
string += code_dict[j]
else:
string += '\n'
with open(code_text, 'w') as f:
f.write(string)
# 解碼
def decode(text_address, result_address, base_node):
text_string = ''
a = base_node
with open(text_address, 'r') as f:
for line in f.readlines():
for j in line:
if j == '1':
b = a.l_child
if b.name:
text_string += b.name
a = base_node
else:
a = b
elif j == '0':
b = a.r_child
if b.name:
text_string += b.name
a = base_node
else:
a = b
else:
text_string += '\n'
with open(result_address, 'w') as f:
f.write(text_string)
if __name__ == '__main__':
# 原始檔案路徑
my_origin_path = "../data/origin.txt"
# 擷取頻數字典
my_frequency_dict = frequency(my_origin_path)
# my_frequency_dict = {'冬天': 1, '夏天': 3, '雨': 5, '雪': 6, '和': 8, '的': 15}
# my_frequency_dict = {'a': 1, 'b': 3, 'c': 5, 'd': 6, 'e': 8, 'f': 15}
# 建構哈夫曼樹
my_base_node = establish_huffman_tree(my_frequency_dict)
# 哈夫曼編碼
my_code_dict = encode(my_base_node, {}, '')
# 編碼檔案路徑
my_code_text = "../data/code.txt"
# 編碼文本檔案
encode_text(my_code_dict, my_origin_path, my_code_text)
# 解碼檔案路徑
my_result_address = "../data/result.txt"
decode(my_code_text, my_result_address, my_base_node)
(二)結果
- origin.txt
該檔案為待編碼檔案,内容如下,這裡分别将“冬天”、“夏天”、“雨”、“雪”、“和”、“的”比對到“a”、“b”、“c”、“d”、“e”、“f”,并頻數分别設定為1、3、5、6、8、15。
abbbcccccddddddeeeeeeeefffffffffffffff
- code.txt
檔案内容如下:
1000100110011001101101101101101110110110110110110111111111111111111111111000000000000000
該檔案為對 origin.txt 進行哈夫曼編碼的結果檔案,該結果與第三部分得出的編碼結果相同。
- result.txt
檔案内容如下:
abbbcccccddddddeeeeeeeefffffffffffffff
該檔案輸出結果是對 code.txt 檔案内容的解碼,解碼結果與 origin.txt 檔案内容相同。
[1] https://baike.baidu.com/item/哈夫曼編碼/1719730?fromtitle=HUFFMAN%E7%BC%96%E7%A0%81&fromid=364674&fr=aladdin
[2] https://baike.baidu.com/item/哈夫曼樹/2305769?fromtitle=%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A0%91&fromid=7783678&fr=aladdin