Python 实现动态 Huffman 编码算法

以下是一个 Python 实现的动态 Huffman 编码算法：\n\npython\nclass Node:\n def __init__(self, value, freq):\n self.value = value\n self.freq = freq\n self.left = None\n self.right = None\n\ndef construct_huffman_tree(data):\n freq_table = {}\n for char in data:\n if char in freq_table:\n freq_table[char] += 1\n else:\n freq_table[char] = 1\n\n nodes = []\n for char, freq in freq_table.items():\n nodes.append(Node(char, freq))\n\n while len(nodes) > 1:\n nodes = sorted(nodes, key=lambda x: x.freq)\n\n left_node = nodes.pop(0)\n right_node = nodes.pop(0)\n\n parent_freq = left_node.freq + right_node.freq\n parent_node = Node(None, parent_freq)\n parent_node.left = left_node\n parent_node.right = right_node\n\n nodes.append(parent_node)\n\n return nodes[0]\n\ndef generate_huffman_codes(root, current_code, codes):\n if root is None:\n return\n\n if root.value is not None:\n codes[root.value] = current_code\n return\n\n generate_huffman_codes(root.left, current_code + '0', codes)\n generate_huffman_codes(root.right, current_code + '1', codes)\n\ndef huffman_encode(data):\n root = construct_huffman_tree(data)\n codes = {}\n generate_huffman_codes(root, '', codes)\n\n encoded_data = ''\n for char in data:\n encoded_data += codes[char]\n\n return encoded_data\n\ndef huffman_decode(encoded_data, root):\n decoded_data = ''\n current_node = root\n for bit in encoded_data:\n if bit == '0':\n current_node = current_node.left\n else:\n current_node = current_node.right\n\n if current_node.value is not None:\n decoded_data += current_node.value\n current_node = root\n\n return decoded_data\n\n\n# 测试例子\ndata = 'aabbbccccddd'\nencoded_data = huffman_encode(data)\nprint('Encoded data:', encoded_data)\n\nroot = construct_huffman_tree(data)\ndecoded_data = huffman_decode(encoded_data, root)\nprint('Decoded data:', decoded_data)\n\n\n此实现首先构建了一个 Huffman 树，然后根据树生成了编码表。编码表中保存了每个字符对应的 Huffman 编码。然后，使用编码表对原始数据进行编码，并将编码后的数据输出。最后，使用 Huffman 树对编码后的数据进行解码，并将解码后的数据输出。