Python实现哈夫曼编码

在Python中，可以利用哈夫曼树（Huffman Tree）的构建过程来实现哈夫曼编码。这是一种基于贪心算法的无损数据压缩技术，用于给每个输入字符分配一个独特的二进制编码。以下是简单的步骤：

1. **计算频率**：首先，统计输入字符串中各个字符的出现频率。

2. **构造初始节点**：创建一个空的优先级队列（通常用堆数据结构），将字符及其频率作为键值对放入队列。

3. **构建哈夫曼树**：从队列中取出两个频率最小的节点合并成一个新的节点，新节点的频率为两者之和，并将它放回队列。重复这个过程直到只剩下一个节点。

4. **编码规则**：从根节点到每个叶子节点的路径记录下所经过的分支，0表示向左走，1表示向右走。这样每个字符就对应了一条唯一的二进制路径，即其哈夫曼编码。

5. **存储编码**：遍历哈夫曼树，对于每个字符，将其路径转换为二进制编码并存储起来。

from heapq import heappush, heappop

def huffman_encoding(freqs):
    heap = [[freq, [char]] for char, freq in freqs.items()]
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        for pair in lo[1:]:
            heappush(heap, [lo[0] + hi[0], pair + hi[1]])
        for pair in hi[1:]:
            heappush(heap, [lo[0] + hi[0], lo[1] + pair])
    
    root, codes = heappop(heap), {}
    def traverse(node, code=""):
        if node[1]:
            traverse(node[1][0], code + "0")
            traverse(node[1][1], code + "1")
        else:
            codes[node[0]] = code
    traverse(root)
    return codes

# 示例用法
freqs = {'a': 10, 'b': 5, 'c': 3}
encoded_freqs = huffman_encoding(freqs)
print(encoded_freqs)  # 输出：{'a': '0', 'b': '10', 'c': '11'}