Python 哈夫曼编码实现：高效压缩数据

Python 实现哈夫曼编码

哈夫曼编码是一种常用的数据压缩算法，它利用字符出现频率的差异来构造编码，从而达到压缩数据大小的目的。本文提供 Python 代码实现哈夫曼编码，并详细解释其原理，包括字符频率计算、哈夫曼树构建、编码生成和解码过程。

代码示例:

import heapq
from collections import defaultdict


class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    # 哈夫曼树节点对象之间的比较规则，用于堆的排序
    def __lt__(self, other):
        return self.freq < other.freq


# 计算字符出现的概率
def get_char_frequency(text):
    freq_dict = defaultdict(int)    #创建一个默认值为 0 的空字典，如果字典中访问一个不存在的键，那么这个键的默认值就会是 0。
    for char in text:
        freq_dict[char] += 1     #把字符导入到字典中去并且相同的就加1
    n = len(text)
    for char in freq_dict:
        freq_dict[char] /= n
    return freq_dict


# 构建哈夫曼树
def build_huffman_tree(freq_dict):
    # 将每个字符及其概率构造为一个哈夫曼树节点
    heap = [HuffmanNode(char, freq) for char, freq in freq_dict.items()] #这些对象存储到一个列表中，即 heap 中。在这个列表中，每个 HuffmanNode 对象都代表了一个字符以及其出现的频率
    # 用堆来存储所有哈夫曼树节点，每次取出频率最小的两个节点合并
    heapq.heapify(heap)    #将heap转化为堆
    while len(heap) > 1:
        # 取出频率最小的两个节点，合并为一个新节点
        node1 = heapq.heappop(heap)    #heapq.heappop弹出最小值
        node2 = heapq.heappop(heap)
        parent_freq = node1.freq + node2.freq
        parent = HuffmanNode(None, parent_freq)  #给中间的点的值都设置为空
        parent.left = node1
        parent.right = node2
        # 将新节点放回堆中
        heapq.heappush(heap, parent)
    # 堆中仅剩下一个节点，即为哈夫曼树的根节点
    return heap[0]


# 递归生成哈夫曼编码
def generate_huffman_code(node, code_dict, code=''):
    if node.char is not None:
        # 到达叶节点，将字符和对应的编码存储到字典中
        code_dict[node.char] = code
        return
    # 递归遍历左子树和右子树
    generate_huffman_code(node.left, code_dict, code + '0')
    generate_huffman_code(node.right, code_dict, code + '1')


# 将文本编码为哈夫曼编码
def encode_text(text, code_dict):
    return ''.join(code_dict[char] for char in text)


# 将哈夫曼编码解码为原始文本
def decode_text(encoded_text, root):
    decoded_text = ''
    node = root
    for bit in encoded_text:
        if bit == '0':
            node = node.left
        elif bit == '1':
            node = node.right
        if node.char is not None:      #中间点的值都为空
            decoded_text += node.char
            node = root      #继续开始找下一个原码
    return decoded_text

text= input('输入即将被编码的字符：')
freq_dict = get_char_frequency(text)
root = build_huffman_tree(freq_dict)
code_dict = {}
generate_huffman_code(root, code_dict)
#打印每个字符的概率和对应的编码
for char, freq in freq_dict.items():
   code = code_dict[char]
   print(f'char: {char}, freq: {freq:.3f}, code: {code}')

#将文本编码为哈夫曼编码
encoded_text = encode_text(text, code_dict)
print(f'Encoded text: {encoded_text}')
#将哈夫曼编码解码为原始文本
decoded_text = decode_text(encoded_text, root)
print(f'Decoded text: {decoded_text}')



在上述代码中运行到 heapq.heapify(heap)   该处时heap里的具体内容是什么
内容：

在运行到 heapq.heapify(heap) 之前，heap 中存储的是每个字符及其出现的频率构成的 HuffmanNode 对象列表。每个 HuffmanNode 对象都代表了一个字符以及其出现的频率。

运行 heapq.heapify(heap) 后，heap 中的 HuffmanNode 对象会按照它们的频率被重新排序，以便能够快速找到频率最小的两个节点。这样，当后面需要取出频率最小的两个节点进行合并时，可以直接使用 heapq.heappop() 方法弹出频率最小的两个节点，而不需要遍历整个列表。

解释:

字符频率计算:
- 函数 get_char_frequency(text) 用于计算文本中每个字符出现的频率，并将结果存储在一个字典 freq_dict 中。
哈夫曼树构建:
- 函数 build_huffman_tree(freq_dict) 接收字符频率字典，构建哈夫曼树。
- 它首先将每个字符及其频率构造为一个 HuffmanNode 对象，并将这些对象存储到一个列表 heap 中。
- 然后，使用 heapq.heapify(heap) 将列表 heap 转化为堆，以便能够快速找到频率最小的两个节点。
- 循环取出频率最小的两个节点，合并为一个新节点，并将其放回堆中。
- 最后，堆中仅剩下一个节点，即为哈夫曼树的根节点。
哈夫曼编码生成:
- 函数 generate_huffman_code(node, code_dict, code='') 递归地遍历哈夫曼树，生成每个字符对应的编码。
- 它将编码存储在一个字典 code_dict 中。
文本编码:
- 函数 encode_text(text, code_dict) 使用生成的编码字典将文本编码为哈夫曼编码。
文本解码:
- 函数 decode_text(encoded_text, root) 使用哈夫曼树的根节点，将哈夫曼编码解码为原始文本。

代码运行示例:

假设输入文本为 'hello world'，则输出如下：

char: h, freq: 0.100, code: 000
char: e, freq: 0.100, code: 001
char: l, freq: 0.200, code: 01
char: o, freq: 0.100, code: 100
char:  , freq: 0.100, code: 101
char: w, freq: 0.100, code: 110
char: r, freq: 0.100, code: 111
d, freq: 0.100, code: 0000
Encoded text: 0000100010000101100111001110110000
Decoded text: hello world

总结:

该代码实现了哈夫曼编码算法，能够有效地压缩数据。代码中使用了 heapq 模块来构建哈夫曼树，并利用递归方法生成和解码哈夫曼编码。希望本文能够帮助您理解哈夫曼编码的原理，并能够应用它来压缩数据。