python编程实现Shannon编码、Huffman编码。 手动输入信源概率分布。 输出:Shannon码、Huffman码,平均码长,编码效率。
时间: 2024-02-27 11:56:47 浏览: 71
好的,这里是手动输入信源概率分布的 Python 代码实现:
```python
import heapq
import math
# 计算熵
def entropy(p):
return -sum([p[i] * math.log(p[i], 2) for i in range(len(p)) if p[i] > 0])
# Shannon 编码
def shannon(p):
n = len(p)
code = [''] * n
code_len = [0] * n
for i in range(n - 1):
for j in range(i + 1, n):
if sum(p[i:j]) >= 0.5:
break
for k in range(i, j):
code[k] += '0'
code_len[k] += 1
for k in range(j, n):
code[k] += '1'
code_len[k] += 1
return code, code_len
# Huffman 编码
def huffman(p):
n = len(p)
heap = [(p[i], i) for i in range(n)]
heapq.heapify(heap)
nodes = [(p[i], i, None, None) for i in range(n)]
for i in range(n - 1):
w1, i1 = heapq.heappop(heap)
w2, i2 = heapq.heappop(heap)
node = (w1 + w2, n + i, i1, i2)
nodes.append(node)
heapq.heappush(heap, (w1 + w2, n + i))
root = nodes[-1]
code = [''] * n
code_len = [0] * n
for i in range(n):
path = []
node = nodes[i]
while node[2] is not None:
if nodes[node[2]][2] == node[3]:
path.append('0')
else:
path.append('1')
node = nodes[node[2]]
code[i] = ''.join(reversed(path))
code_len[i] = len(code[i])
return code, code_len
# 手动输入信源概率分布
p = []
while True:
s = input("请输入信源概率分布(输入空行结束):")
if s == "":
break
p.append(float(s))
# 计算 Shannon 编码和 Huffman 编码
code, code_len = shannon(p)
h_code, h_code_len = huffman(p)
# 输出结果
print("Shannon码为:", code)
print("Shannon码长度为:", code_len)
print("Huffman码为:", h_code)
print("Huffman码长度为:", h_code_len)
print("Shannon编码平均码长为:", sum([p[i] * code_len[i] for i in range(len(p))]))
print("Huffman编码平均码长为:", sum([p[i] * h_code_len[i] for i in range(len(p))]))
print("Shannon编码效率为:", entropy(p) / sum([p[i] * code_len[i] for i in range(len(p))]))
print("Huffman编码效率为:", entropy(p) / sum([p[i] * h_code_len[i] for i in range(len(p))]))
```
这段代码中,我们首先定义了一个计算熵的函数 `entropy`,然后分别实现了 Shannon 编码和 Huffman 编码的函数 `shannon` 和 `huffman`。在主程序中,我们通过 `input` 函数手动输入信源概率分布,并计算了 Shannon 编码和 Huffman 编码的码字、码长、平均码长和编码效率等指标。
希望这个示例代码能够帮助你完成你的编程任务。
阅读全文