python 哈夫曼编码

哈夫曼编码是一种基于字符出现频率的编码方式，它可以将字符编码为不同长度的二进制码，从而实现数据的压缩。下面是一个Python实现的哈夫曼编码的例子：

import heapq
from collections import defaultdict

def encode(s):
    # 统计字符出现频率
    freq = defaultdict(int)
    for c in s:
        freq[c] += 1

    # 构建哈夫曼树
    heap = [[wt, [sym, ""]] for sym, wt in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    # 构建编码表
    code = dict(heapq.heappop(heap)[1:])
    encoded = "".join([code[c] for c in s])

    return encoded, code

def decode(encoded, code):
    inv_code = {v: k for k, v in code.items()}
    current_code = ""
    decoded = ""
    for bit in encoded:
        current_code += bit
        if current_code in inv_code:
            decoded += inv_code[current_code]
            current_code = ""

    return decoded

这个例子中，`encode`函数接受一个字符串作为输入，返回该字符串的哈夫曼编码和编码表。`decode`函数接受一个哈夫曼编码和编码表作为输入，返回解码后的字符串。