霍夫曼编码如何用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
``