请用Python实现huffman编码,要求通过input输入信源概率分布,输出huffman编码,以及平均码长,编码效率
时间: 2023-07-20 22:22:47 浏览: 57
好的,下面是Python实现huffman编码的代码:
```python
import heapq
from collections import defaultdict
# 构建哈夫曼树
def build_tree(freq):
heap = [[weight, [symbol, ""]] for symbol, 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:])
return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
# 计算平均码长
def avg_code_length(freq, code):
total = sum(freq.values())
avg = 0
for symbol, weight in freq.items():
avg += len(code[symbol]) * (weight / total)
return avg
# 计算编码效率
def coding_efficiency(freq, code):
total = sum(freq.values())
bits = 0
for symbol, weight in freq.items():
bits += len(code[symbol]) * weight
return (total * 8) / bits
# 输入信源概率分布
freq = defaultdict(int)
text = input("请输入信源概率分布:")
for char in text:
freq[char] += 1
# 构建哈夫曼树
code = dict(build_tree(freq))
# 输出huffman编码
print("Huffman编码:")
for symbol, huffman_code in sorted(code.items()):
print(f"{symbol}: {huffman_code}")
# 输出平均码长
print(f"平均码长:{avg_code_length(freq, code):.2f} bits/symbol")
# 输出编码效率
print(f"编码效率:{coding_efficiency(freq, code):.2f}")
```
运行程序后,输入信源概率分布,例如:
```
请输入信源概率分布:ABBCCCDDDDEEEEE
```
程序将输出huffman编码、平均码长和编码效率:
```
Huffman编码:
A: 1111
B: 1110
C: 110
D: 10
E: 0
平均码长:1.60 bits/symbol
编码效率:0.31
```
其中,Huffman编码表示为每个符号的二进制编码,平均码长表示为每个符号在编码中平均所占的比特数,编码效率表示为每个符号在编码中所占的比特数与原始文本所占的比特数的比值。