huffman编码

import heapq
from collections import defaultdict

def huffman_encoding(data):
    frequency = defaultdict(int)
    for char in data:
        frequency[char] += 1
    
    heap = [[weight, [char, ""]] for char, weight in frequency.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:])
    
    huffman_code = dict(heapq.heappop(heap)[1:])
    encoded_data = ''.join(huffman_code[char] for char in data)
    return encoded_data, huffman_code

def huffman_decoding(encoded_data, huffman_code):
    reverse_mapping = {v: k for k, v in huffman_code.items()}
    decoded_data = ""
    code = ""
    for bit in encoded_data:
        code += bit
        if code in reverse_mapping:
            decoded_data += reverse_mapping[code]
            code = ""
    return decoded_data

# 示例使用
data = "this is an example for huffman encoding"
encoded_data, huffman_code = huffman_encoding(data)
decoded_data = huffman_decoding(encoded_data, huffman_code)

print(f"Original data: {data}")
print(f"Encoded data: {encoded_data}")
print(f"Decoded data: {decoded_data}")