费诺香农编码python实现

费诺香农编码（Fano's coding），也称为二进制前缀编码或最优编码，是一种数据压缩技术，用于将信息以最短平均码长的方式表示。它的目标是最小化编码的期望长度，同时保证唯一性。Python实现这种编码通常会涉及到一些数据结构如字典和列表。

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

def fano_encoding(freqs, alphabet):
    sorted_freqs = sorted(freqs.items(), key=lambda x: x[0])
    encoding = {}
    
    for freq, symbol in sorted_freqs:
        if not encoding[symbol]:
            encoding[symbol] = '0'
        else:
            # 使用二进制位数来标记每个字符的位置，从1开始计
            next_code = max(encoding.values()).bit_length()
            encoding[symbol] = format(next_code, '0{}b'.format(len(bin(next_code + 1)) - 2))
            
    return encoding

# 示例频率表
freqs = {'A': 45, 'B': 30, 'C': 20, 'D': 5}
alphabet = list(freqs.keys())

encoding = fano_encoding(freqs, alphabet)
print("编码:", encoding)