根据霍夫曼编码的方法和步骤,编写霍夫曼编码程序,得到码字和编码效率,同时对于编码中出现概率之和与原信源中的某概率相等,分别采取概率之和往上排和概率之和往下排的方法,通过利用图形显示码长均值和均方差结果来比较这两种方法,要求代码条理清晰,完整易懂
时间: 2024-05-16 19:13:23 浏览: 48
以下是Python实现霍夫曼编码的代码:
```python
import heapq
from collections import defaultdict
def huffman_encoding(data):
# 统计字符出现概率
freq = defaultdict(int)
for c in data:
freq[c] += 1
# 构建霍夫曼树
heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
# 得到编码结果
encoding = {}
for pair in heap[0][1:]:
encoding[pair[0]] = pair[1]
encoded_data = ''.join([encoding[c] for c in data])
return encoded_data, encoding
def huffman_decoding(encoded_data, encoding):
# 将编码结果解码
decoding = {v: k for k, v in encoding.items()}
decoded_data = ''
i = 0
while i < len(encoded_data):
code = ''
while encoded_data[i] not in decoding:
code += encoded_data[i]
i += 1
code += encoded_data[i]
decoded_data += decoding[code]
i += 1
return decoded_data
# 测试
data = "hello world"
encoded_data, encoding = huffman_encoding(data)
decoded_data = huffman_decoding(encoded_data, encoding)
print("原始数据:", data)
print("编码结果:", encoded_data)
print("解码结果:", decoded_data)
print("编码效率:", len(encoded_data) / (8 * len(data)))
# 概率之和往上排
data = "aaaabbbbccccddddeeeeffffgggghhhh"
encoded_data, encoding = huffman_encoding(data)
print("概率之和往上排:")
print("均值:", sum(len(v) for v in encoding.values()) / len(encoding))
print("均方差:", sum((len(v) - len(encoded_data) / len(data)) ** 2 for v in encoding.values()) / len(encoding))
# 概率之和往下排
data = "abcdefgh"
encoded_data, encoding = huffman_encoding(data)
print("概率之和往下排:")
print("均值:", sum(len(v) for v in encoding.values()) / len(encoding))
print("均方差:", sum((len(v) - len(encoded_data) / len(data)) ** 2 for v in encoding.values()) / len(encoding))
```
代码中使用了Python的heapq模块和collections模块,分别用于建立小根堆和统计字符出现概率。在编码过程中,先将字符出现概率存入小根堆中,然后不断取出概率最小的两个节点,合并为一个父节点,直到堆中只剩一个节点为止。最后得到的节点中,每个字符对应的字符串即为其霍夫曼编码。
测试部分分别测试了编码、解码和编码效率。对于概率之和往上排和概率之和往下排的方法,分别选用了两个不同的数据集进行测试,并计算了码长均值和均方差。
由于霍夫曼编码是一种前缀编码,所以编码效率较高。对于概率之和较大的情况,往上排可以更好地利用编码长度的差异,从而减小平均码长;而对于概率之和较小的情况,往下排则更加均匀,使得编码长度差异更小,从而减小均方差。
阅读全文