要求:1)从终端读入字符集大小为n,及n个字符和n个权值,建立哈夫曼树,进行编码并且输出,并将它存于文件hfmtree中。2)利用已建好的哈夫曼编码文件hfmtree,对存储于文件中的某正文进行编码。输出字符正文,再输出该文的二进制码。3)对2)的编码进行译码,译码结果存储到文件中,并与编码前的文件对比。程序编写
时间: 2024-03-20 08:45:02 浏览: 119
好的,我可以为您提供一个Python的实现。
1. 建立哈夫曼树并输出
```python
import heapq
import pickle
class Node:
def __init__(self, char=None, weight=0, left=None, right=None):
self.char = char
self.weight = weight
self.left = left
self.right = right
def __lt__(self, other):
return self.weight < other.weight
def build_huffman_tree(chars, weights):
nodes = [Node(chars[i], weights[i]) for i in range(len(chars))]
heapq.heapify(nodes)
while len(nodes) > 1:
left = heapq.heappop(nodes)
right = heapq.heappop(nodes)
parent = Node(weight=left.weight + right.weight, left=left, right=right)
heapq.heappush(nodes, parent)
root = nodes[0]
return root
def encode_huffman_tree(root, code, codes):
if root.char is not None:
codes[root.char] = code
return
encode_huffman_tree(root.left, code + '0', codes)
encode_huffman_tree(root.right, code + '1', codes)
# 从终端读入字符集大小为n,及n个字符和n个权值
n = int(input('请输入字符集大小n:'))
chars = []
weights = []
for i in range(n):
char, weight = input('请输入第{}个字符和权值,用空格分隔:'.format(i + 1)).split()
chars.append(char)
weights.append(int(weight))
# 建立哈夫曼树并输出
root = build_huffman_tree(chars, weights)
codes = {}
encode_huffman_tree(root, '', codes)
with open('hfmtree', 'wb') as f:
pickle.dump((chars, weights, codes), f)
print('哈夫曼编码已经存储到文件hfmtree中')
```
2. 利用已建好的哈夫曼编码文件对文本进行编码
```python
# 读入文本
with open('text', 'r') as f:
text = f.read()
# 读入哈夫曼树并建立哈希表
with open('hfmtree', 'rb') as f:
chars, weights, codes = pickle.load(f)
# 对文本进行编码
encoded_text = ''.join(codes[char] for char in text)
# 输出字符正文和二进制码
print('原始文本:', text)
print('编码后文本:', encoded_text)
print('二进制码:', ''.join(format(ord(c), '08b') for c in encoded_text))
# 存储编码后的文本到文件中
with open('encoded_text', 'w') as f:
f.write(encoded_text)
print('编码后的文本已经存储到文件encoded_text中')
```
3. 对编码进行译码并存储到文件中
```python
# 读入编码后的文本
with open('encoded_text', 'r') as f:
encoded_text = f.read()
# 对编码进行译码
decoded_text = ''
i = 0
while i < len(encoded_text):
node = root
while node.char is None:
bit = encoded_text[i]
node = node.left if bit == '0' else node.right
i += 1
decoded_text += node.char
# 存储译码后的文本到文件中
with open('decoded_text', 'w') as f:
f.write(decoded_text)
print('译码后的文本已经存储到文件decoded_text中')
# 检验译码的正确性
with open('text', 'r') as f:
original_text = f.read()
assert decoded_text == original_text, '译码结果与原始文本不一致'
print('译码正确')
```
希望这个Python程序能够帮助您理解哈夫曼编译码系统的实现过程。
阅读全文