AI文库-您身边的智能助手,如没有想要的内容请与本站万能的AI助手联系。

哈夫曼编码的实验代码 1. 初始化一个大小为n的优先队列(最小堆),并将所有字符及其频率插入队列。 2. 当队列的大小大于1时,执行以下操作: a. 从队列中删除两个最小频率的字符及其编码。 b. 将

来自 辽宁省沈阳市 的网友 时间: 热度:°C 加入收藏 我要投稿 点赞()
进行n-1次插入和删除操作,所以总的时间复杂度为O((n-1)logn)。空间复杂度:优先队列的大小为n,所以空间复杂度为O(n)。

以下是哈夫曼编码的实验代码:

```python
import heapq
from collections import defaultdict

def huffman_encoding(s):
# 统计字符频率
freq = defaultdict(int)
for c in s:
freq[c] += 1

# 初始化优先队列(最小堆)
min_heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapq.heapify(min_heap)

# 构建哈夫曼树
while len(min_heap) > 1:
lo = heapq.heappop(min_heap)
hi = heapq.heappop(min_heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(min_heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

# 提取哈夫曼编码
huff_dict = dict(heapq.heappop(min_heap)[1:])
encoded_str = "".join(huff_dict[c] for c in s)

return huff_dict, encoded_str

# 测试
s = "this is an example for huffman encoding"
huff_dict, encoded_str = huffman_encoding(s)
print("哈夫曼编码字典:", huff_dict)
print("编码后的字符串:", encoded_str)
```

注意:这个代码示例仅适用于给定的输入字符串,如果需要处理其他字符串,请将`s`替换为相应的输入。
221381
领取福利

微信扫码领取福利

微信扫码分享