哈夫曼编码
哈夫曼编码
哈夫曼编码是一种用于无损数据压缩的算法。
哈夫曼编码也是许多不同压缩算法的组成部分。它是 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 等有损压缩中。
