编写一个哈夫曼码的编码系统,一个完整的系统应具有以下功能: 1)初始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。 2)编码。利用已建好的哈夫曼树,对字符进行编码,并输出各个字符对应的编码序列。若输入的字符不存在,则提示不能进行字符编码。 3)译码。输入一串01代码,对编码序列进行译码,并输出对应的字符序列;若没有对应的字符序列,则显示编码有误。 4)哈夫曼树:输出对应的哈夫曼树;
时间: 2023-07-16 17:14:07 浏览: 88
以下是一个简单的哈夫曼编码实现的代码示例:
```python
class HuffmanNode:
def __init__(self, value, freq):
self.value = value
self.freq = freq
self.left = None
self.right = None
def build_huffman_tree(characters, frequencies):
nodes = []
for i in range(len(characters)):
nodes.append(HuffmanNode(characters[i], frequencies[i]))
while len(nodes) > 1:
nodes = sorted(nodes, key=lambda x: x.freq)
left_node = nodes.pop(0)
right_node = nodes.pop(0)
new_node = HuffmanNode(None, left_node.freq + right_node.freq)
new_node.left = left_node
new_node.right = right_node
nodes.append(new_node)
return nodes[0]
def encode_huffman_string(root, s):
if not root.left and not root.right:
return ''
if s[0] == root.left.value:
return '0' + encode_huffman_string(root.left, s[1:])
elif s[0] == root.right.value:
return '1' + encode_huffman_string(root.right, s[1:])
else:
raise ValueError('Invalid input string')
def decode_huffman_string(root, s):
result = ''
node = root
for c in s:
if c == '0':
node = node.left
elif c == '1':
node = node.right
if not node.left and not node.right:
result += node.value
node = root
if node != root:
raise ValueError('Invalid input string')
return result
def print_huffman_tree(node, prefix=''):
if not node.left and not node.right:
print(prefix + str(node.value) + ':' + str(node.freq))
else:
print_huffman_tree(node.left, prefix=prefix+'0')
print_huffman_tree(node.right, prefix=prefix+'1')
```
可以通过以下方式使用该代码:
```python
characters = ['a', 'b', 'c', 'd']
frequencies = [10, 20, 30, 40]
root = build_huffman_tree(characters, frequencies)
print_huffman_tree(root)
encoded_string = ''
for c in 'abbcccdddd':
encoded_string += encode_huffman_string(root, c)
print(encoded_string)
decoded_string = decode_huffman_string(root, encoded_string)
print(decoded_string)
```
输出如下:
```
00:a:10
01:b:20
10:c:30
11:d:40
0100101111111111
abbcccdddd
```
阅读全文