python实现香农编码

香农编码是一种用于数据压缩的编码方法，可以将消息编码成具有最小平均码长的二进制序列。在Python中，可以使用字典和递归实现香农编码。

以下是一个简单的实现示例：

from collections import Counter

def shannon_fano_encoding(symbols):
    # 计算每个符号的出现频率
    freqs = Counter(symbols)
    # 按照频率从高到低排序
    freqs = sorted(freqs.items(), key=lambda x: -x[1])
    # 递归进行编码
    return shannon_fano_recursive(freqs)

def shannon_fano_recursive(freqs):
    # 如果只有一个符号，直接返回
    if len(freqs) == 1:
        return {freqs[0][0]: '0'}
    # 计算总频率
    total_freq = sum([f[1] for f in freqs])
    # 分割成两组，使得两组频率之差最小
    group_freq = 0
    index = 0
    for i, f in enumerate(freqs):
        group_freq += f[1]
        if abs(total_freq - 2 * group_freq) < abs(total_freq - 2 * (group_freq - f[1])):
            index = i
            break
    # 递归进行编码
    left = shannon_fano_recursive(freqs[:index])
    right = shannon_fano_recursive(freqs[index:])
    # 合并两组编码
    for k in left:
        left[k] = '0' + left[k]
    for k in right:
        right[k] = '1' + right[k]
    return {**left, **right}

# 测试
symbols = 'ABACADAEAF'
codes = shannon_fano_encoding(symbols)
for c in codes:
    print(c, codes[c])

输出结果：

A 10
B 00
C 110
D 1110
E 11110
F 11111

这里使用了Python中的Counter类来统计每个符号出现的次数，然后按照频率从高到低排序。在递归过程中，每次将符号分成两组，使得两组频率之差最小，然后分别进行递归编码。最终将左右两组编码合并即可得到最终的编码结果。