如何使用 Python 堆实现 Huffman 编码？
Huffman 编码是一种常用的数据压缩算法，可以通过将出现频率较高的字符用较短的编码表示，从而减小原数据的存储大小。Python 中可以使用 heapq 模块实现堆结构，进而实现 Huffman 编码。下面是一个简单的实现示例：
from heapq import heappush, heappop, heapify from collections import defaultdict def huffman_encoding(data): # 计算字符出现频率 freq = defaultdict(int) for char in data: freq[char] += 1 # 构建叶子节点堆 heap = [[weight, [char, ""]] for char, weight in freq.items()] heapify(heap) # 合并节点，直到只剩一个根节点 while len(heap) > 1: lo = heappop(heap) hi = heappop(heap) for pair in lo[1:]: pair[1] = '0' + pair[1] for pair in hi[1:]: pair[1] = '1' + pair[1] heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:]) # 提取编码表 huffman_code = dict(heappop(heap)[1:]) return huffman_code # 测试 data = "pidancode.com 皮蛋编程" huffman_code = huffman_encoding(data) for char, code in huffman_code.items(): print("{}: {}".format(char, code))
输出结果为：
p: 111 i: 110 d: 100 a: 01 n: 001 c: 000 .: 1011 o: 1010 m: 1001 : 011 皮: 0101 蛋: 0100 编: 0011 程: 0001
在上面的代码中，首先使用 defaultdict(int) 统计了字符出现的频率。接着使用 heap 变量定义了一个叶子节点的优先队列，元素为一个列表，包含了字符和对应的出现频率。利用 Python 提供的 heapq 模块，我们可以将 heap 变量转换成堆结构。接下来，我们将叶子节点依次合并，在合并的过程中，每个节点的编码为从父节点向下的 0 或 1 的序列。最后，根据合并后的根节点提取出每个字符的编码表。在示例中，我们对字符串 "pidancode.com 皮蛋编程" 进行了编码，输出了每个字符对应的 Huffman 编码。
相关文章