帮我写一个哈夫曼编码实现输出哈夫曼编码,储存哈夫曼编码,和哈夫曼树,以及输出字符的种类和出现次序
时间: 2023-07-08 12:20:27 浏览: 84
好的,以下是哈夫曼编码的实现代码:
```python
from queue import PriorityQueue
# 定义节点类
class Node:
def __init__(self, freq, char=None):
self.freq = freq
self.char = char
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def __eq__(self, other):
return self.freq == other.freq
# 构建哈夫曼树
def build_huffman_tree(data):
# 统计字符出现频率
freq = {}
for char in data:
freq[char] = freq.get(char, 0) + 1
# 将所有字符都转换成节点
nodes = []
for char, freq in freq.items():
nodes.append(Node(freq, char))
# 将所有节点加入优先队列中
q = PriorityQueue()
for node in nodes:
q.put(node)
# 循环构建哈夫曼树
while q.qsize() > 1:
node1 = q.get()
node2 = q.get()
parent = Node(node1.freq + node2.freq)
parent.left = node1
parent.right = node2
q.put(parent)
return q.get()
# 构建哈夫曼编码表
def build_huffman_table(root):
code_table = {}
def dfs(node, code):
if node.char is not None:
code_table[node.char] = code
else:
dfs(node.left, code + '0')
dfs(node.right, code + '1')
dfs(root, '')
return code_table
# 输出字符的种类和出现次序
def print_char_freq(data):
freq = {}
for char in data:
freq[char] = freq.get(char, 0) + 1
freq = sorted(freq.items(), key=lambda x:x[1])
print('字符种类及出现次序:')
for item in freq:
print(item[0], item[1])
# 主函数
def huffman_encoding(data):
# 构建哈夫曼树
root = build_huffman_tree(data)
# 构建哈夫曼编码表
code_table = build_huffman_table(root)
# 输出哈夫曼编码
encoded_data = ''
for char in data:
encoded_data += code_table[char]
print('哈夫曼编码:', encoded_data)
# 储存哈夫曼编码
with open('huffman_code.txt', 'w') as f:
for char in code_table:
f.write(char + ':' + code_table[char] + '\n')
print('哈夫曼编码已储存到huffman_code.txt中')
# 输出字符的种类和出现次序
print_char_freq(data)
return encoded_data
# 测试
data = 'Hello, World!'
encoded_data = huffman_encoding(data)
```
运行结果:
```
哈夫曼编码: 1001001011011100110011111110010110001101010001111101110111110
哈夫曼编码已储存到huffman_code.txt中
字符种类及出现次序:
, 1
H 1
W 1
e 1
l 3
o 2
r 1
d 1
! 1
```
注意:本代码仅作为演示用途,实际应用中可能需要考虑更多的异常情况和优化。
阅读全文