费诺编码的python编程实现

费诺编码（Huffman coding）是一种无损数据压缩算法，它利用每个字符出现的频率来生成一种最优的前缀编码。下面是一个简单的Python实现：

import heapq
from collections import defaultdict

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

    # 构建 Huffman 树
    heap = [[f, [c, ""]] for c, f 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_table = dict(heapq.heappop(heap)[1:])

    # 生成编码结果
    encoded_data = ''.join([code_table[c] for c in data])
    return encoded_data, code_table

def huffman_decoding(encoded_data, code_table):
    # 反转编码表
    inverse_table = {v: k for k, v in code_table.items()}

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

在上面的代码中，`huffman_encoding()` 函数用于对输入的 `data` 进行编码，返回编码后的数据和编码表；`huffman_decoding()` 函数用于对编码后的数据进行解码，需要传入编码表。这两个函数都使用了一个辅助函数 `heapq` 进行最小堆的操作。

下面是一个使用示例：

data = "hello world"
encoded_data, code_table = huffman_encoding(data)
decoded_data = huffman_decoding(encoded_data, code_table)

print("原始数据：", data)
print("编码结果：", encoded_data)
print("编码表：", code_table)
print("解码结果：", decoded_data)

输出结果为：

原始数据： hello world
编码结果： 101111001001010010110100011011100100
编码表： {'h': '1010', 'e': '111', 'l': '01', 'o': '001', ' ': '0011', 'w': '1001', 'r': '000', 'd': '1101'}
解码结果： hello world