实现哈夫曼编码的代码
时间: 2024-11-23 20:22:58 浏览: 35
哈夫曼编码是一种基于权值的自底向上的贪心算法,通常用于数据压缩。以下是使用Python实现哈夫曼编码的一个简单例子:
```python
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def get_freq(self):
return self.freq
def build_huffman_tree(freq_list):
if not freq_list:
return None, None
# 将频率列表转换为Node对象
nodes = [Node(char, freq) for char, freq in freq_list]
while len(nodes) > 1:
# 按照频率从小到大排序
nodes.sort(key=lambda x: x.freq)
# 取出最小的两个节点合并
node1, node2 = nodes[:2]
new_node = Node(None, node1.freq + node2.freq)
new_node.left = node1
new_node.right = node2
nodes = nodes[2:] + [new_node]
# 返回根节点和叶子节点组成的字典(键是字符,值是对应的编码)
root = nodes[0]
huffman_codes = {}
_build_codes(root, '', huffman_codes)
return root, huffman_codes
def _build_codes(node, code, codes_dict):
if node is None:
return
if node.char is not None:
codes_dict[node.char] = code
else:
_build_codes(node.left, code + '0', codes_dict)
_build_codes(node.right, code + '1', codes_dict)
# 使用示例
freq_list = [('A', 5), ('B', 9), ('C', 4)]
root, huffman_codes = build_huffman_tree(freq_list)
for char, code in huffman_codes.items():
print(f"{char}: {code}")
```
在这个代码中,我们首先创建了一个`Node`类表示树中的每个节点,然后实现了一个递归函数`_build_codes`来构建Huffman树并生成编码。最后,`build_huffman_tree`函数将给定的字符和频率映射到Huffman编码。
阅读全文