运用python实现Huffman编码

好的，以下是一个基于Python的Huffman编码实现：

import heapq
from collections import defaultdict

def huffman_encoding(data):
    # 构建字符频率字典
    freq_dict = defaultdict(int)
    for char in data:
        freq_dict[char] += 1

    # 将字符频率字典转换为堆
    heap = [[freq, [char, ""]] for char, freq in freq_dict.items()]
    heapq.heapify(heap)

    # 合并堆中的节点，构建Huffman树
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        for pair in left[1:]:
            pair[1] = '0' + pair[1]
        for pair in right[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [left[0] + right[0]] + left[1:] + right[1:])

    # 构建编码字典
    encoding_dict = dict(heapq.heappop(heap)[1:])

    # 返回编码后的数据和编码字典
    encoded_data = ""
    for char in data:
        encoded_data += encoding_dict[char]
    return encoded_data, encoding_dict

def huffman_decoding(encoded_data, encoding_dict):
    # 构建反向编码字典
    decoding_dict = {v: k for k, v in encoding_dict.items()}

    # 解码数据
    current_code = ""
    decoded_data = ""
    for bit in encoded_data:
        current_code += bit
        if current_code in decoding_dict:
            decoded_data += decoding_dict[current_code]
            current_code = ""
    return decoded_data

示例用法：

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

输出：

Encoded data: 0110110111000110010011110100111100001010101101101110001
Decoded data: hello world

这个实现使用了Python的heapq和collections模块，用于构建堆和默认字典。它首先构建字符频率字典，然后将其转换为堆。接下来，它在堆中合并节点，直到只剩下一个节点为止。合并过程中，左分支被标记为0，右分支被标记为1。最终，编码字典被构建，用于编码数据。解码过程中，使用反向编码字典将编码数据转换为原始数据。