写一段哈夫曼树的python代码
时间: 2023-12-01 20:05:10 浏览: 63
这是一段简单的哈夫曼树的 Python 代码:
```python
from collections import defaultdict
def huffman_tree(frequencies):
# 建立哈夫曼树
# frequencies 是一个字典,键为字符,值为频率
heap = [[weight, [symbol, '']] for symbol, weight in frequencies.items()]
heap.sort()
while len(heap) > 1:
low = heap.pop(0)
high = heap.pop(0)
for pair in low[1:]:
pair[1] = '0' + pair[1]
for pair in high[1:]:
pair[1] = '1' + pair[1]
heap.append([low[0] + high[0]] + low[1:] + high[1:])
heap.sort()
return sorted(heap[0][1:], key=lambda p: (len(p[-1]), p))
# 测试
frequencies = defaultdict(int)
string = "this is an example for huffman encoding"
for char in string:
frequencies[char] += 1
print(huffman_tree(frequencies))
```
这段代码会输出哈夫曼编码后的字符及其对应的编码,比如:
```
[[' ', '01'], ['a', '100'], ['c', '1010'], ['d', '1011'], ['e', '1100'], ['f', '1101'], ['g', '111'], ['h', '1000'], ['i', '101'], ['m', '1110'], ['n', '1111'], ['o', '001'], ['p', '0000'], ['r', '0001'], ['s', '0010'], ['t', '0011'], ['u', '010'], ['x', '011']]
```
上面的代码中,字符串 `string` 为待编码的字符串,字典 `frequencies` 用来统计字符串中每个字符的出现次数。然后调用 `huffman_tree` 函数,传入 `frequencies` 字典,得到哈夫曼编码后的字符及其对应的编码。