哈夫曼編碼
哈夫曼編碼
哈夫曼編碼是一種用於無損資料壓縮的演算法。
哈夫曼編碼也是許多不同壓縮演算法的組成部分。它是 zip、gzip 和 png 等無失真壓縮的組成部分，甚至是 mp3 和 jpeg 等有失真壓縮演算法的一部分。
使用下面的動畫，瞭解如何使用哈夫曼編碼壓縮文字。
{{ huffmanBitCount }} 位
結果 哈夫曼碼是原始大小的 {{compression}}%。
動畫顯示了文字中的字母通常如何使用 UTF-8 儲存，以及哈夫曼編碼如何能夠用更少的位數儲存相同的文字。
工作原理
- 計算每種資料的出現頻率。
- 構建一個 二叉樹，從計數最低的節點開始。新的父節點具有其子節點的計數總和。
- 父節點的邊為左子節點獲得“0”，為右子節點獲得“1”。
- 在完成的二叉樹中，從根節點開始，為每個分支新增“0”或“1”，以找到每種資料的新的哈夫曼碼。
- 透過使用二叉樹將資料逐塊轉換為二進位制碼來建立哈夫曼碼。
哈夫曼編碼使用可變長度的位數來表示每種資料，對於出現頻率更高的資料，其位數表示更短。
此外，哈夫曼編碼確保沒有一個碼是另一個碼的字首，這使得壓縮資料易於解碼。
資料壓縮是指在資料原始大小減小的情況下，資訊大部分或全部保留。例如，聲音或音樂檔案通常以壓縮格式儲存，大約只有原始資料大小的 10%，但保留了大部分資訊。
無損意味著即使資料被壓縮，所有資訊仍然存在。這意味著例如壓縮後的文字仍然具有與原始文字相同的字母和字元。
有損是資料壓縮的另一種變體，其中丟失或犧牲了部分原始資訊，以便可以更進一步地壓縮資料。音樂、影像和影片通常使用有失真壓縮（如 mp3、jpeg 和 mp4）進行儲存和流式傳輸。
手動建立哈夫曼碼
為了更好地理解哈夫曼編碼的工作原理，讓我們手動建立一個哈夫曼碼，使用與動畫中相同的文字：“lossless”。
文字通常使用 UTF-8 在計算機中儲存，這意味著對於我們“lossless”中的普通拉丁字母，每個字母都使用 8 位儲存。其他字母或符號，如“€”或“🦄”，則使用更多位數儲存。
要使用哈夫曼編碼壓縮文字“lossless”，我們首先計算每個字母的出現次數。
如上方的節點所示，“s”出現 4 次，“l”出現 2 次，“o”和“e”各出現 1 次。
我們開始用出現次數最少的字母“o”和“e”構建樹，它們的父節點計數為“2”，因為字母“o”和“e”的計數被彙總了。
下一個獲得新父節點的節點是計數最低的節點：“l”，以及“o”和“e”的父節點。
現在，必須將最後一個節點“s”新增到二叉樹中。字母節點“s”和計數為“4”的父節點獲得一個計數為“8”的新父節點。
沿著從根節點開始的邊，我們現在可以確定單詞“lossless”中每個字母的哈夫曼碼。
每個字母的哈夫曼碼現在可以在上方影像的每個字母節點下找到。哈夫曼編碼的一個優點是，使用頻率最高的資料塊獲得最短的程式碼，因此“s”字母的程式碼僅僅是“0”。
如前所述，這些普通的拉丁字母通常使用 UTF-8 儲存，這意味著它們每個需要 8 位。例如，字母“o”在 UTF-8 中儲存為“01101111”，但在我們用於單詞“lossless”的哈夫曼碼中，它儲存為“110”。
注意：使用 UTF-8 時，一個字母始終具有相同的二進位制碼，但使用哈夫曼碼時，每個字母（資料塊）的二進位制碼會隨著我們正在壓縮的文字（資料集）而變化。
總結一下，我們已經將單詞“lossless”從其 UTF-8 碼壓縮到
01101100 01101111 01110011 01110011 01101100 01100101 01110011 01110011
僅用
10 110 0 0 10 111 0 0
使用哈夫曼編碼，這是一個巨大的改進。
但是，如果資料以哈夫曼碼 10 110 0 0 10 111 0 0 的形式儲存，或者程式碼被髮送給我們，我們如何才能解碼它以看到哈夫曼碼包含什麼資訊呢？
此外，二進位制碼實際上是 10110001011100，沒有空格，並且每個資料塊的位長度可變，那麼計算機如何理解每個資料塊的二進位制碼從哪裡開始到哪裡結束呢？
解碼哈夫曼碼
就像 UTF-8 儲存的程式碼一樣，我們的計算機可以將其解碼為正確的字母，計算機需要知道哪些位代表哈夫曼碼中的哪些資料塊。
因此，除了哈夫曼碼之外，還必須有一個包含有關每個資料塊的哈夫曼二進位制碼資訊的轉換表，以便它可以被解碼。
所以，對於這個哈夫曼碼
100110110
有了這個轉換表
| 字母 | 哈夫曼碼 |
|---|---|
| a | 0 |
| b | 10 |
| n | 11 |
您能解碼這個哈夫曼碼嗎？
工作原理
- 從哈夫曼碼的左側開始，查詢表中的每個位序列。
- 將每個碼與相應的字母匹配。
- 繼續，直到整個哈夫曼碼被解碼。
我們從第一個位元開始
100110110表中沒有以僅 1 作為哈夫曼碼的字母，因此我們繼續幷包含下一個位元。
100110110從表中我們可以看到 10 是“b”，所以現在我們有了第一個字母。我們檢查下一個位元
100110110我們發現 0 是“a”，所以現在我們有了哈夫曼碼中儲存的兩個字母“ba”。
我們繼續查詢表中的哈夫曼碼
100110110碼 11 是“n”。
100110110碼 0 是“a”。
100110110碼 11 是“n”。
100110110碼 0 是“a”。
哈夫曼碼現在已被解碼，單詞是“banana”！
哈夫曼碼字首
哈夫曼編碼演算法一個有趣且非常有用的部分是，它確保沒有一個碼是另一個碼的字首。
想象一下，如果我們剛才使用的轉換表看起來像這樣
| 字母 | 哈夫曼碼 |
|---|---|
| a | 1 |
| b | 10 |
| n | 11 |
如果真是這樣，我們從一開始解碼就會感到困惑，對吧？
100110110因為我們怎麼知道第一個位元 1 代表字母“a”，還是它是字母“b”或“c”的第一個位元？
這個屬性，即沒有一個碼是另一個碼的字首，使得解碼成為可能。並且由於可變的位元長度，它在哈夫曼編碼中尤為重要。
哈夫曼編碼實現
根據資料或文字建立哈夫曼碼的正確術語是“編碼”，而相反的操作是“解碼”，即根據程式碼重建物原始資料或文字。
下面的程式碼示例將一個單詞或任何文字透過哈夫曼編碼進行壓縮。
示例
哈夫曼編碼。
class Node:
def __init__(self, char=None, freq=0):
self.char = char
self.freq = freq
self.left = None
self.right = None
nodes = []
def calculate_frequencies(word):
frequencies = {}
for char in word:
if char not in frequencies:
freq = word.count(char)
frequencies[char] = freq
nodes.append(Node(char, freq))
def build_huffman_tree():
while len(nodes) > 1:
nodes.sort(key=lambda x: x.freq)
left = nodes.pop(0)
right = nodes.pop(0)
merged = Node(freq=left.freq + right.freq)
merged.left = left
merged.right = right
nodes.append(merged)
return nodes[0]
def generate_huffman_codes(node, current_code, codes):
if node is None:
return
if node.char is not None:
codes[node.char] = current_code
generate_huffman_codes(node.left, current_code + '0', codes)
generate_huffman_codes(node.right, current_code + '1', codes)
def huffman_encoding(word):
global nodes
nodes = []
calculate_frequencies(word)
root = build_huffman_tree()
codes = {}
generate_huffman_codes(root, '', codes)
return codes
word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)
print("Word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)哈夫曼解碼實現
除了使用哈夫曼編碼進行資料編碼外，我們還應該有一種解碼方法，以重建物原始資訊。
下面的實現基本上與前面的程式碼示例相同，但增加了一個用於解碼哈夫曼碼的函式。
該 huffman_decoding 函式接受哈夫曼碼以及一個 codes Python 字典（一個 雜湊對映），其中包含字元及其對應的二進位制碼。該函式然後反轉對映，並逐位元檢查哈夫曼碼以重建物原始文字。
示例
哈夫曼解碼。
class Node:
def __init__(self, char=None, freq=0):
self.char = char
self.freq = freq
self.left = None
self.right = None
nodes = []
def calculate_frequencies(word):
frequencies = {}
for char in word:
if char not in frequencies:
freq = word.count(char)
frequencies[char] = freq
nodes.append(Node(char, freq))
def build_huffman_tree():
while len(nodes) > 1:
nodes.sort(key=lambda x: x.freq)
left = nodes.pop(0)
right = nodes.pop(0)
merged = Node(freq=left.freq + right.freq)
merged.left = left
merged.right = right
nodes.append(merged)
return nodes[0]
def generate_huffman_codes(node, current_code, codes):
if node is None:
return
if node.char is not None:
codes[node.char] = current_code
generate_huffman_codes(node.left, current_code + '0', codes)
generate_huffman_codes(node.right, current_code + '1', codes)
def huffman_encoding(word):
global nodes
nodes = []
calculate_frequencies(word)
root = build_huffman_tree()
codes = {}
generate_huffman_codes(root, '', codes)
return codes
def huffman_decoding(encoded_word, codes):
current_code = ''
decoded_chars = []
# Invert the codes dictionary to get the reverse mapping
code_to_char = {v: k for k, v in codes.items()}
for bit in encoded_word:
current_code += bit
if current_code in code_to_char:
decoded_chars.append(code_to_char[current_code])
current_code = ''
return ''.join(decoded_chars)
word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)
decoded_word = huffman_decoding(encoded_word, codes)
print("Initial word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)
print("Decoded word:", decoded_word)
您現在已經看到了如何使用哈夫曼編碼壓縮文字，以及如何解碼哈夫曼碼以重建物原始文字。
注意：哈夫曼編碼可用於任何型別資料的無失真壓縮，不僅僅是文字。哈夫曼編碼也用作 zip 等其他壓縮演算法的元件，甚至用在 jpeg 和 mp3 等有失真壓縮中。
