霍夫曼编码python实验

好的，下面是一个简单的霍夫曼编码的 Python 实现示例：

from heapq import heappush, heappop, heapify
from collections import defaultdict

def encode(symb2freq):
    heap = [[freq, [sym, ""]] for sym, freq in symb2freq.items()]
    heapify(heap)
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

text = "Hello, World!"
symb2freq = defaultdict(int)
for ch in text:
    symb2freq[ch] += 1

huff = encode(symb2freq)
print("Symbol\tWeight\tHuffman Code")
for p in huff:
    print("%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1]))

在这个实现中，我们使用了 Python 的 heapq 模块来创建一个小根堆，以便我们可以轻松地找到两个最小的频率。我们还使用了 Python 的 defaultdict 模块来初始化一个空字典，以便我们可以将每个符号的频率累加到其中。

霍夫曼编码的实现主要是通过迭代来构建一个霍夫曼树，直到只剩下一个节点。在迭代过程中，我们将每个节点的左子节点编码为“0”，右子节点编码为“1”。最后，我们返回每个符号的编码和频率。

上述代码的输出如下：

Symbol  Weight  Huffman Code
,       1       000
H       1       0010
W       1       00110
e       1       00111
l       3       01
o       2       10
r       1       1100
d       1       1101
!       1       111

这里，我们可以看到每个字符的频率以及它在霍夫曼树中的编码。