根据概率求哈夫曼编码

根据概率求哈夫曼编码的步骤如下：

1. 统计每个字符出现的频率或概率。
2. 将每个字符作为一个叶子节点，构建一个初始的哈夫曼树。
3. 从频率最低的两个节点开始，合并它们并创建一个新的父节点，该父节点的频率为两个子节点的频率之和。将新的父节点插入到哈夫曼树中。
4. 重复步骤3，直到所有的节点都被合并为一个根节点。
5. 根据哈夫曼树的结构，给每个字符分配一个唯一的二进制编码。从根节点开始，向左走为0，向右走为1，直到达到叶子节点。
6. 将每个字符的编码记录下来，即得到了哈夫曼编码。

以下是一个示例代码，演示了如何根据概率求哈夫曼编码：

import heapq
from collections import defaultdict

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

# 示例用法
probabilities = {'a': 0.2, 'b': 0.3, 'c': 0.1, 'd': 0.4}
huffman_code = huffman_encoding(probabilities)
for symbol, code in huffman_code:
    print(f"Symbol: {symbol}, Code: {code}")

输出结果为：

Symbol: d, Code: 0
Symbol: b, Code: 10
Symbol: a, Code: 110
Symbol: c, Code: 111