编程实现哈夫曼编码和译码系统。 利用哈夫曼编码进行通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本,但是,这要求在发送端通过一个编码系统对待传数据进行预先编码;在接受端将传来的数据进行解码(复原)对于双工信道(即可以双向传输的信道),每端都要有一个完整的编/译码系统。请为这样的信息收发站写一个哈夫曼的编译码系统。 要求: 1)从终端读入字符集大小为n,及n个字符和n个权值,建立哈夫曼树,进行编码并且输出,并将它存于文件hfmtree中。 2)利用已建好的哈夫曼编码文件hfmtree,对存储于文件中的某正文进行编码。输出字符正文,再输出该文的二进制码。 3)对2)的编码进行译码,译码结果存储到文件中,并与编码前的文件对比。
时间: 2024-03-25 20:35:37 浏览: 127
好的,我可以帮您实现一个哈夫曼编译码系统。以下是Python版本的实现,您可以根据自己的需要进行修改。
```python
import heapq
import os
class HuffmanNode:
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
class HuffmanTree:
def __init__(self, freq_map):
self.root = None
self.freq_map = freq_map
def build_tree(self):
node_list = [HuffmanNode(char, freq) for char, freq in self.freq_map.items()]
heapq.heapify(node_list)
while len(node_list) > 1:
left_node = heapq.heappop(node_list)
right_node = heapq.heappop(node_list)
freq_sum = left_node.freq + right_node.freq
parent_node = HuffmanNode(freq=freq_sum, left=left_node, right=right_node)
heapq.heappush(node_list, parent_node)
self.root = node_list[0]
def encode_map(self):
encode_map = {}
self.build_encode_map(self.root, '', encode_map)
return encode_map
def build_encode_map(self, node, code, encode_map):
if node.char is not None:
encode_map[node.char] = code
return
self.build_encode_map(node.left, code + '0', encode_map)
self.build_encode_map(node.right, code + '1', encode_map)
class HuffmanCoder:
def __init__(self, freq_map):
self.freq_map = freq_map
self.huffman_tree = HuffmanTree(freq_map)
self.huffman_tree.build_tree()
self.encode_map = self.huffman_tree.encode_map()
def encode(self, text):
encoded_text = ''
for char in text:
encoded_text += self.encode_map[char]
return encoded_text
def decode(self, encoded_text):
decoded_text = ''
node = self.huffman_tree.root
for bit in encoded_text:
if bit == '0':
node = node.left
else:
node = node.right
if node.char is not None:
decoded_text += node.char
node = self.huffman_tree.root
return decoded_text
def read_freq_map():
freq_map = {}
n = int(input('输入字符集大小n: '))
for i in range(n):
char, freq = input().strip().split()
freq_map[char] = int(freq)
return freq_map
def write_hfmtree(huffman_tree):
encode_map = huffman_tree.encode_map()
with open('hfmtree', 'w') as f:
for char, code in encode_map.items():
f.write(f'{char} {code}\n')
def read_hfmtree():
encode_map = {}
with open('hfmtree', 'r') as f:
for line in f:
char, code = line.strip().split()
encode_map[char] = code
return encode_map
def write_encoded_text(encoded_text, text):
with open('encoded_text', 'w') as f:
f.write(encoded_text)
f.write('\n')
f.write(' '.join(format(ord(char), 'b') for char in text))
def read_encoded_text():
with open('encoded_text', 'r') as f:
encoded_text = f.readline().strip()
binary_text = f.readline().strip().split()
return encoded_text, binary_text
def write_decoded_text(decoded_text):
with open('decoded_text', 'w') as f:
f.write(decoded_text)
def read_text():
with open('text', 'r') as f:
text = f.read()
return text
def main():
freq_map = read_freq_map()
huffman_coder = HuffmanCoder(freq_map)
write_hfmtree(huffman_coder.huffman_tree)
text = read_text()
encoded_text = huffman_coder.encode(text)
write_encoded_text(encoded_text, text)
encode_map = read_hfmtree()
huffman_coder = HuffmanCoder(encode_map)
encoded_text, binary_text = read_encoded_text()
decoded_text = huffman_coder.decode(encoded_text)
write_decoded_text(decoded_text)
original_text = ''.join([chr(int(binary, 2)) for binary in binary_text])
print(f'原文: {text}')
print(f'编码后的文本: {encoded_text}')
print(f'原文的二进制码: {" ".join(format(ord(char), "b") for char in text)}')
print(f'解码后的文本: {decoded_text}')
print(f'原文与解码后的文本是否一致: {original_text == decoded_text}')
if __name__ == '__main__':
main()
```
在运行程序时,需要在终端输入字符集的大小,以及每个字符的权值。例如:
```
输入字符集大小n: 6
a 45
b 13
c 12
d 16
e 9
f 5
```
然后程序会根据输入的权值建立哈夫曼树,并将编码结果存储到`hfmtree`文件中。接下来,程序会读取一个名为`text`的文件,对其中的文本进行编码,并将编码结果存储到`encoded_text`文件中。程序会输出编码后的文本,以及原文的二进制码。
接着,程序会读取`hfmtree`文件,重建哈夫曼树,并将编码结果存储到一个名为`encoded_text`的文件中。然后程序会读取`encoded_text`文件,对编码后的文本进行译码,并将译码结果存储到一个名为`decoded_text`的文件中。程序会输出解码后的文本,以及原文与解码后的文本是否一致的结果。
阅读全文