编写一个程序,对下表中的单词按出现频度构造一棵哈夫曼树并输出对应的哈夫曼编码
时间: 2024-11-10 22:25:17 浏览: 17
【C++】根据输入的字符串生成哈夫曼树, 并进行哈夫曼编码和解码
5星 · 资源好评率100%
哈夫曼树(Huffman Tree),也称为最优二叉树,是一种用于数据压缩的构造算法。它通过对字符按照其频率进行排序,构建出一棵带权路径长度最短的二叉树。每个叶子节点代表一个字符,内部节点的权重是两个子节点之和。
要编写一个程序来生成这个过程,我们可以分步骤操作:
1. **统计字符频率**:首先读取输入文本,计算每个单词的出现次数,并存储在一个字典(Python 中可以用 `collections.Counter`)里。
```python
import collections
word_counts = collections.Counter(words_in_your_table)
```
2. **创建堆(优先级队列)**:将字符及其频率作为键值对放入堆中,小频率在前。
```python
import heapq
heap = [(count, word) for word, count in word_counts.items()]
heapq.heapify(heap)
```
3. **合并堆中的节点**:不断从堆顶取出两个最小的节点,合并成一个新的节点(新的节点的频率是两个子节点的和),并将新节点放回堆中,直到只剩下一个节点为止。这一步形成了哈夫曼树的结构。
```python
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
combined_freq = left[0] + right[0]
combined_node = (combined_freq, left[1] + '0' + right[1])
heapq.heappush(heap, combined_node)
```
4. **构建哈夫曼编码**:从根节点开始遍历哈夫曼树,对于每一个字符,记录从根到该字符节点的所有边(左孩子加1,右孩子加0),即得到了它的哈夫曼编码。
5. **输出结果**:最后,可以遍历堆中的哈夫曼树,输出每个字符及其相应的哈夫曼编码。
```python
def huffman_code(node):
if isinstance(node, tuple): # 叶子节点
return node[1]
else: # 内部节点
return huffman_code(node[0]) + huffman_code(node[1])
root = heap[0][1] # 获取根节点
for word, code in zip(word_counts.keys(), huffman_code(root)):
print(f"{word}: {code}")
```
阅读全文