哈夫曼编码
哈夫曼编码
哈夫曼编码是一种用于无损数据压缩的算法。
哈夫曼编码也被用作许多不同压缩算法的组成部分。它被用作无损压缩（如 zip、gzip 和 png）的组成部分，甚至被用作有损压缩算法（如 mp3 和 jpeg）的一部分。
使用下面的动画查看如何使用哈夫曼编码压缩文本。
{{ huffmanBitCount }} 位
结果 哈夫曼编码是原始大小的 {{compression}}%。
动画展示了文本中的字母是如何使用 UTF-8 存储的，以及哈夫曼编码如何使存储相同文本所需的位数更少。
工作原理
- 统计每个数据块出现的频率。
- 构建一个 二叉树，从计数最小的节点开始。新的父节点拥有其子节点的组合计数。
- 从父节点到左子节点的边标记为“0”，从父节点到右子节点的边标记为“1”。
- 在完成的二叉树中，从根节点开始沿着边向下走，为每个分支添加“0”或“1”，找到每个数据块的新的哈夫曼编码。
- 通过使用二叉树将数据逐个转换成二进制代码来创建哈夫曼编码。
哈夫曼编码使用可变长度的位来表示每个数据块，对于出现频率更高的数据块，使用更短的位表示。
此外，哈夫曼编码确保没有任何代码是另一个代码的前缀，这使得压缩后的数据易于解码。
数据压缩是指将原始数据大小减小，但大部分或全部信息都保留。例如，声音或音乐文件通常以压缩格式存储，大约仅为原始数据大小的 10%，但大部分信息都保留下来了。
无损意味着即使在数据压缩之后，所有信息仍然保留。这意味着，例如，压缩后的文本仍然包含与原始文本相同的字母和字符。
有损是数据压缩的另一种变体，其中一些原始信息丢失或被牺牲，以便可以进一步压缩数据。音乐、图像和视频通常以有损压缩格式存储和流式传输，如 mp3、jpeg 和 mp4。
手动创建哈夫曼编码
为了更好地理解哈夫曼编码的工作原理，让我们手动创建一个哈夫曼编码，使用与动画中相同的文本：“lossless”。
文本通常使用 UTF-8 在计算机中存储，这意味着每个字母都使用 8 位存储，就像我们在 “lossless” 中一样。其他字母或符号，如“€”或“🦄”，则使用更多位存储。
为了使用哈夫曼编码压缩文本 “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)霍夫曼解码实现
除了使用霍夫曼编码对数据进行编码之外，我们还应该有一种方法来解码它，以重建原始信息。
下面的实现与之前的代码示例基本相同，但增加了一个用于解码霍夫曼编码的函数。
The 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。
