根据电文中各字符出现的频率,建立哈夫曼树,并设计字符的哈夫曼编码。 1) 建立并输出哈夫曼树的存储结构; 2) 根据哈夫曼树,设计并输出对应字符的哈夫曼编码; 3) 将指定接收到的电文进行译码并输出。
时间: 2024-03-19 18:44:45 浏览: 73
好的,以下是实现该任务的 Python 代码:
```python
import heapq
from collections import defaultdict
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
def build_huffman_tree(text):
freq_dict = defaultdict(int)
for char in text:
freq_dict[char] += 1
heap = [HuffmanNode(char, freq) for char, freq in freq_dict.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
heapq.heappush(heap, parent)
return heap[0]
def build_huffman_codes(node, code='', codes={}):
if node.char:
codes[node.char] = code
else:
build_huffman_codes(node.left, code + '0', codes)
build_huffman_codes(node.right, code + '1', codes)
return codes
def encode_text(text, codes):
return ''.join(codes[char] for char in text)
def decode_text(encoded_text, node):
text = ''
current_node = node
for bit in encoded_text:
current_node = current_node.left if bit == '0' else current_node.right
if current_node.char:
text += current_node.char
current_node = node
return text
if __name__ == '__main__':
# 例子
text = 'hello world'
huffman_tree_root = build_huffman_tree(text)
huffman_codes = build_huffman_codes(huffman_tree_root)
encoded_text = encode_text(text, huffman_codes)
decoded_text = decode_text(encoded_text, huffman_tree_root)
print('Huffman Tree:')
print(huffman_tree_root.__dict__)
print('Huffman Codes:')
print(huffman_codes)
print('Encoded Text:')
print(encoded_text)
print('Decoded Text:')
print(decoded_text)
```
这段代码实现了建立哈夫曼树、设计字符的哈夫曼编码、对指定接收到的电文进行译码功能。你可以根据需求自行修改代码。
阅读全文