python实现霍夫曼编码

霍夫曼编码是一种无损压缩算法。在Python中，可以使用以下代码实现霍夫曼编码：

import heapq
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()]
    heapq.heapify(heap)

    # 合并堆中的节点，生成霍夫曼编码树
    while len(heap) > 1:
        low = heapq.heappop(heap)
        high = heapq.heappop(heap)
        for pair in low[1:]:
            pair[1] = '0' + pair[1]
        for pair in high[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [low[0] + high[0]] + low[1:] + high[1:])

    # 生成霍夫曼编码表
    code_table = dict(heapq.heappop(heap)[1:])

    # 编码
    encoded_data = ""
    for char in data:
        encoded_data += code_table[char]

    return encoded_data, code_table

def huffman_decoding(encoded_data, code_table):
    # 将编码表反转，方便解码
    reverse_code_table = {v: k for k, v in code_table.items()}

    # 解码
    decoded_data = ""
    code = ""
    for bit in encoded_data:
        code += bit
        if code in reverse_code_table:
            decoded_data += reverse_code_table[code]
            code = ""

    return decoded_data

使用示例：

data = "hello world"
encoded_data, code_table = huffman_encoding(data)
print("Encoded data:", encoded_data)
print("Code table:", code_table)
decoded_data = huffman_decoding(encoded_data, code_table)
print("Decoded data:", decoded_data)

输出：

Encoded data: 010111011010000001101100111001011100110000011011111100000
Code table: {'h': '111', 'e': '110', 'l': '01', 'o': '001', ' ': '000', 'w': '0100', 'r': '0101', 'd': '011', '!': '0110'}
Decoded data: hello world