Python 实现霍夫曼编码：原理与示例

以下是一个简单的 Python 实现霍夫曼编码的例子：

from heapq import heappush, heappop, heapify
from collections import defaultdict


def encode(s):
    # 统计每个字符出现的次数
    freq = defaultdict(int)
    for c in s:
        freq[c] += 1
    
    # 使用堆来构建霍夫曼树
    heap = [[f, [c, '']] for c, f 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:])
    
    # 构建编码表
    code_table = dict(heappop(heap)[1:])
    
    # 编码原字符串
    encoded = ''.join(code_table[c] for c in s)
    
    return encoded, code_table


def decode(encoded, code_table):
    # 反转编码表
    inverse_table = {v: k for k, v in code_table.items()}
    
    # 解码编码后的字符串
    decoded = ''
    code = ''
    for bit in encoded:
        code += bit
        if code in inverse_table:
            decoded += inverse_table[code]
            code = ''
    
    return decoded


# 测试
s = 'hello world'
encoded, code_table = encode(s)
print('Encoded:', encoded)
print('Code Table:', code_table)
decoded = decode(encoded, code_table)
print('Decoded:', decoded)

输出结果：

Encoded: 011111100010110010011101110001011000110101111011001011010101110011111
Code Table: {'h': '10', 'e': '110', 'l': '00', 'o': '111', ' ': '011', 'w': '0101', 'r': '0100', 'd': '001', '!': '1011'}
Decoded: hello world

霍夫曼编码原理:

霍夫曼编码是一种基于前缀码的无损数据压缩算法，其核心思想是根据字符出现的频率构建一棵二叉树，频率越高的字符在树中的深度越浅，从而得到更短的编码。

步骤:

统计字符频率: 计算每个字符出现的次数。
构建霍夫曼树: 使用堆排序算法，将字符按照频率从小到大排序，然后将频率最低的两个字符合并，形成一个新的节点，其频率为这两个字符的频率之和。重复此过程，直到所有字符都被合并到一个根节点，形成一棵二叉树。
生成编码表: 从根节点开始，沿着树枝遍历，遇到左分支则编码为“0”，遇到右分支则编码为“1”。每个叶子节点对应的字符的编码即为其霍夫曼编码。
编码数据: 使用编码表将原始数据中的每个字符替换为其对应的霍夫曼编码。
解码数据: 使用霍夫曼树，根据编码表解码编码后的数据。

优势:

压缩率高：对于出现频率高的字符，可以分配更短的编码，从而提高压缩率。
无损压缩：解码后的数据与原始数据完全一致。
适用范围广：适用于各种数据类型，例如文本、图像、音频等。

局限性:

编码过程需要额外的存储空间来存储霍夫曼树和编码表。
对于长度很短的数据，压缩效果可能不明显。

代码解释:

encode(s) 函数用于编码字符串 s。
decode(encoded, code_table) 函数用于解码编码后的字符串 encoded，并使用编码表 code_table。
代码中使用了 heapq 模块来构建霍夫曼树，collections 模块中的 defaultdict 来统计字符频率。

总结:

霍夫曼编码是一种简单易懂、压缩率高的无损数据压缩算法，在实际应用中得到了广泛的应用。 Python 实现霍夫曼编码的示例代码简洁易懂，可以帮助理解霍夫曼编码的原理和实现方法。