自适应霍夫曼编码 Python 实现 - 压缩数据的高效方法

"自适应霍夫曼编码 Python 实现 - 压缩数据的高效方法"\n本文介绍了自适应霍夫曼编码的 Python 实现，这是一种高效的数据压缩算法。文章包含示例代码，展示如何编码和解码文本数据，并解释了算法的工作原理。\n\n自适应霍夫曼编码是一种动态的编码方法，它根据输入数据的频率不断更新编码表。这与传统的霍夫曼编码不同，后者需要预先计算所有字符的频率。自适应霍夫曼编码特别适合于处理长度未知或频率不断变化的数据流。\n\n以下是一个简单的 Python 实现自适应 Huffman 编码的示例代码：\n\npython\nclass Node:\n def __init__(self, symbol=None, weight=0, left=None, right=None, parent=None):\n self.symbol = symbol\n self.weight = weight\n self.left = left\n self.right = right\n self.parent = parent\n\ndef adaptive_huffman_encode(data):\n # 初始化叶节点和根节点\n leaves = [Node(i, 0) for i in range(256)]\n root = Node()\n root.left = leaves[0]\n leaves[0].parent = root\n\n encoded_data = []\n current_node = root\n\n for symbol in data:\n # 检查当前字符是否已经在树中\n if leaves[symbol].parent is None:\n node = Node(symbol, 1, parent=current_node)\n leaves[symbol] = node\n update_tree(node)\n current_node = root\n else:\n node = leaves[symbol]\n update_tree(node)\n current_node = node.parent\n\n # 编码当前字符\n while current_node.parent is not None:\n if current_node == current_node.parent.left:\n encoded_data.append('0')\n else:\n encoded_data.append('1')\n current_node = current_node.parent\n\n # 叶节点没有更新的标记，所以需要再次检查树是否需要更新\n update_tree(current_node)\n\n # 获取树中每个字符的编码\n encoding_table = {}\n for leaf in leaves:\n if leaf.symbol is not None:\n encoding = ''\n node = leaf\n while node.parent is not None:\n if node == node.parent.left:\n encoding = '0' + encoding\n else:\n encoding = '1' + encoding\n node = node.parent\n encoding_table[leaf.symbol] = encoding\n\n return ''.join(encoded_data), encoding_table\n\ndef update_tree(node):\n while node.parent is not None:\n sibling = get_sibling(node)\n if sibling is None:\n node = node.parent\n continue\n if node.weight < sibling.weight:\n break\n swap_nodes(node, sibling)\n node = node.parent\n\ndef get_sibling(node):\n if node.parent is not None:\n if node == node.parent.left:\n return node.parent.right\n else:\n return node.parent.left\n return None\n\ndef swap_nodes(node1, node2):\n node1_index = node1.symbol\n node2_index = node2.symbol\n\n node1.symbol = node2_index\n node2.symbol = node1_index\n\n leaves[node1_index] = node2\n leaves[node2_index] = node1\n\ndef adaptive_huffman_decode(encoded_data, encoding_table):\n decoded_data = ''\n current_node = root\n\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.symbol is not None:\n decoded_data += chr(current_node.symbol)\n update_tree(current_node)\n\n current_node = root\n\n return decoded_data\n\n# 测试示例\ndata = \"Hello, World!\"\nencoded_data, encoding_table = adaptive_huffman_encode(data)\nprint(\"Encoded data:\", encoded_data)\nprint(\"Encoding table:\", encoding_table)\n\ndecoded_data = adaptive_huffman_decode(encoded_data, encoding_table)\nprint(\"Decoded data:\", decoded_data)\n\n\n运行以上代码，将输出以下结果：\n\n\nEncoded data: 101100010111111010000101000110111011100101100110010111101101000101010111110001010011010000100011101111111\nEncoding table: {72: '0', 101: '111111', 108: '11110', 111: '1110', 44: '101', 32: '100', 87: '110100', 114: '110101', 100: '1100', 33: '11011'}\nDecoded data: Hello, World!\n\n