Python Huffman Tree Implementation: Efficient Data Compression

以下是一个Python实现的Huffman树的例子：\n\npython\nimport heapq\nfrom collections import defaultdict\n\nclass Node:\n def __init__(self, freq, char=None):\n self.freq = freq\n self.char = char\n self.left = None\n self.right = None\n\n def __lt__(self, other):\n return self.freq < other.freq\n\ndef build_huffman_tree(data):\n # 统计字符频率\n freq_table = defaultdict(int)\n for char in data:\n freq_table[char] += 1\n \n # 构建优先队列\n heap = []\n for char, freq in freq_table.items():\n node = Node(freq, char)\n heapq.heappush(heap, node)\n\n # 构建Huffman树\n while len(heap) > 1:\n node1 = heapq.heappop(heap)\n node2 = heapq.heappop(heap)\n merged = Node(node1.freq + node2.freq)\n merged.left = node1\n merged.right = node2\n heapq.heappush(heap, merged)\n\n return heap[0]\n\ndef traverse_huffman_tree(root, code='', codes={}):\n if root is None:\n return\n if root.char is not None:\n codes[root.char] = code\n traverse_huffman_tree(root.left, code + '0', codes)\n traverse_huffman_tree(root.right, code + '1', codes)\n\ndef huffman_encoding(data):\n if data == '':\n return '', None\n\n root = build_huffman_tree(data)\n codes = {}\n traverse_huffman_tree(root, codes=codes)\n\n encoded_data = ''.join(codes[char] for char in data)\n return encoded_data, root\n\ndef huffman_decoding(encoded_data, root):\n if encoded_data == '':\n return ''\n\n decoded_data = ''\n node = root\n for bit in encoded_data:\n if bit == '0':\n node = node.left\n else:\n node = node.right\n if node.char is not None:\n decoded_data += node.char\n node = root\n\n return decoded_data\n\n# 测试\ndata = 'hello world'\nencoded_data, root = huffman_encoding(data)\ndecoded_data = huffman_decoding(encoded_data, root)\n\nprint('原始数据:', data)\nprint('编码后:', encoded_data)\nprint('解码后:', decoded_data)\n\n\n上述代码中，build_huffman_tree函数用于构建Huffman树，traverse_huffman_tree函数用于遍历Huffman树并生成每个字符的编码，huffman_encoding函数用于对数据进行编码，huffman_decoding函数用于对编码数据进行解码。最后通过测试数据进行验证编码和解码的正确性。