### Fano 编码 Python 实现 以下是基于 Shannon-Fano 编码原理的一个简单 Python 实现。该实现通过构建二叉树来分配编码给输入字符。 ```python def shannon_fano_coding(probabilities): """ 对概率分布进行 Shannon-Fano 编码。 参数: probabilities (dict): 字符及其对应的概率/频率 返回: dict: 字符到其对应二进制编码的映射 """ # 将概率按降序排列并转换为列表形式 [(char, prob), ...] items = sorted(probabilities.items(), key=lambda x: x[1], reverse=True) def split(items_list): """将项目分为两组，使得每组的概率总和尽可能接近""" total_prob = sum([prob for _, prob in items_list]) cumulative_sum = 0 index_split = 0 for i, (_, p) in enumerate(items_list): cumulative_sum += p if abs(cumulative_sum - (total_prob / 2)) < abs((cumulative_sum + items_list[i+1][1] if i+1<len(items_list) else 0) - (total_prob / 2)): index_split = i + 1 else: break return items_list[:index_split], items_list[index_split:] def assign_codes(items_list, prefix=""): """递归地为每个分组赋值编码""" if len(items_list) == 1: codes[items_list[0][0]] = prefix elif len(items_list) >= 2: group1, group2 = split(items_list) assign_codes(group1, prefix=prefix+"0") # 左子树加 '0' assign_codes(group2, prefix=prefix+"1") # 右子树加 '1' codes = {} assign_codes(items) return codes # 测试示例 if __name__ == "__main__": freq_dict = {'A': 0.4, 'B': 0.2, 'C': 0.2, 'D': 0.1, 'E': 0.1} result = shannon_fano_coding(freq_dict) print("Shannon-Fano Coding Result:") for char, code in result.items(): print(f"{char}: {code}") ``` #### 解析说明 上述代码实现了 Shannon-Fano 编码的核心逻辑： - 首先按照字符出现的概率大小对其进行排序[^1]。 - 使用 `split` 函数将字符集划分为两个部分，使每一部分的概率之和尽可能相等。 - 利用递归方法分别为左分支（'0'）和右分支（'1'）分配编码[^2]。 此算法虽然概念清晰，但由于划分方式的原因，在实际应用中通常不如 Huffman 编码高效。