本资源提供了一种带有详细注释的哈夫曼编码及解码算法实现方式，并附有可以直接运行的示例代码。适合初学者学习和参考使用。
哈夫曼编码译码代码如下所示，并配有详细注释以供直接运行使用。
```python
import heapq
class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
# 用于堆排序的比较方法
def __lt__(self, other):
return self.freq < other.freq
def build_frequency_dict(text):
frequency = {}
for char in text:
if char not in frequency:
frequency[char] = 0
frequency[char] += 1
return frequency
def build_huffman_tree(frequency):
priority_queue = [HuffmanNode(char, freq) for char, freq in frequency.items()]
heapq.heapify(priority_queue)
while len(priority_queue) > 1:
left_node = heapq.heappop(priority_queue)
right_node = heapq.heappop(priority_queue)
merged_freq = left_node.freq + right_node.freq
merged_node = HuffmanNode(None, merged_freq)
merged_node.left = left_node
merged_node.right = right_node
heapq.heappush(priority_queue, merged_node)
return priority_queue[0]
def generate_codes(node, prefix=, codebook={}):
if node is not None:
if node.char is not None and len(prefix) > 0:
codebook[node.char] = prefix
generate_codes(node.left, prefix + 0, codebook)
generate_codes(node.right, prefix + 1, codebook)
def huffman_encode(text):
frequency_dict = build_frequency_dict(text)
tree_root = build_huffman_tree(frequency_dict)
code_book = {}
generate_codes(tree_root, , code_book)
encoded_text =
for char in text:
if char in code_book:
encoded_text += code_book[char]
return encoded_text
def huffman_decode(encoded_data, tree):
decoded_output = []
node = tree
for bit in encoded_data:
if bit == 0:
node = node.left
else:
node = node.right
if node.char is not None:
decoded_output.append(node.char)
node = tree
return .join(decoded_output)
# 示例使用方法：
text_input = this is an example for huffman encoding
frequency_dict = build_frequency_dict(text_input)
huffman_tree_root = build_huffman_tree(frequency_dict)
encoded_data = huffman_encode(text_input)
print(Encoded data:, encoded_data)
decoded_text = huffman_decode(encoded_data, huffman_tree_root)
print(Decoded text:, decoded_text)
```
以上代码实现了哈夫曼编码的构建、编码和解码过程，包括频率字典生成、哈夫曼树建立以及基于此树进行数据压缩与还原。
5星
