请写出一段程序,从键盘接收一串电文字符,在程序中构造一颗霍夫曼数,实现霍夫曼编码,用霍夫曼编码生成的代码串进行译码,输出对应的霍夫曼编码。还能翻译由霍夫曼编码生成的代码串,输出对应的电文字符串。
时间: 2024-03-22 13:41:59 浏览: 128
好的,以下是一个简单的 Python 示例程序:
```python
import heapq
from collections import Counter, namedtuple
# 定义节点类
class Node(namedtuple("Node", ["left", "right"])):
def walk(self, code, acc):
self.left.walk(code, acc + "0")
self.right.walk(code, acc + "1")
# 定义叶子节点类
class Leaf(namedtuple("Leaf", ["char"])):
def walk(self, code, acc):
code[self.char] = acc or "0"
# 构造霍夫曼树
def huffman_encode(s):
h = []
for ch, freq in Counter(s).items():
h.append((freq, len(h), Leaf(ch)))
heapq.heapify(h)
count = len(h)
while len(h) > 1:
freq1, _count1, left = heapq.heappop(h)
freq2, _count2, right = heapq.heappop(h)
heapq.heappush(h, (freq1 + freq2, count, Node(left, right)))
count += 1
code = {}
if h:
[(_freq, _count, root)] = h
root.walk(code, "")
return code
# 实现霍夫曼编码
def encode(s, code):
return "".join(code[ch] for ch in s)
# 实现霍夫曼解码
def decode(encoded, code):
inv_code = {v: k for k, v in code.items()}
acc = ""
decoded = ""
for ch in encoded:
acc += ch
if acc in inv_code:
decoded += inv_code[acc]
acc = ""
return decoded
# 主程序
if __name__ == "__main__":
s = input("请输入电文字符串:")
code = huffman_encode(s)
encoded = encode(s, code)
decoded = decode(encoded, code)
print("霍夫曼编码:", encoded)
print("霍夫曼解码:", decoded)
```
这个程序中,我们首先定义了一个节点类和一个叶子节点类。节点类有左右两个子节点,而叶子节点类只有一个字符属性。然后我们使用 Counter 函数统计输入字符串中每个字符出现的次数,将它们放入一个小根堆中,逐个合并出霍夫曼树。在构造树的过程中,我们使用一个字典来记录每个字符的霍夫曼编码。最后,我们使用 encode 函数将输入字符串编码成霍夫曼码,使用 decode 函数将霍夫曼码解码成原始字符串。
阅读全文