霍夫曼编码python实验
时间: 2023-07-05 13:24:06 浏览: 181
好的,下面是一个简单的霍夫曼编码的 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
```
这里,我们可以看到每个字符的频率以及它在霍夫曼树中的编码。
阅读全文