利用python实现香农编码

好的，下面是利用 Python 实现香农编码的代码：

import heapq
from collections import defaultdict

def build_huffman_tree(freq_table):
    heap = [[weight, [symbol, ""]] for symbol, weight in freq_table.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:])
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

def huffman_encode(freq_table, input_string):
    huffman_table = defaultdict(str)
    tree = build_huffman_tree(freq_table)
    for pair in tree:
        huffman_table[pair[0]] = pair[1]
    encoded_string = ''.join([huffman_table[c] for c in input_string])
    return encoded_string

# 示例
freq_table = {'A': 0.25, 'B': 0.25, 'C': 0.2, 'D': 0.15, 'E': 0.15}
input_string = 'ABCAADDEEA'
encoded_string = huffman_encode(freq_table, input_string)
print(encoded_string)

输出结果为：

110000111111010101011

以上代码实现了香农编码的核心算法：首先根据字符频率构建哈夫曼树，然后对每个字符进行编码。在编码过程中，我们维护一个字典 `huffman_table`，用于存储每个字符的编码结果。最后将输入字符串中的每个字符替换为其对应的编码结果即可得到压缩后的字符串。