用Python实现哈夫曼树算法
哈夫曼树又称最优树，是一种带权路径长度最短的树。其应用较为广泛，例如数据压缩、图像处理等领域。下面我们就来用Python实现哈夫曼树算法。
算法步骤：
1.计算字符出现频率，构造权值列表；
2.从权值列表中选出频率最小的两个字符，构造一个父节点，其权值为这两个子节点权值之和；
3.将父节点插入权值列表中，并删除原有的两个子节点；
4.重复步骤2-3，直到只剩下一个节点，即根节点。
代码实现：
class Node: def __init__(self, value, freq): self.left = None self.right = None self.value = value self.freq = freq def build_huffman_tree(frequencies): nodes = [] for value, freq in frequencies.items(): nodes.append(Node(value, freq)) while len(nodes) > 1: nodes = sorted(nodes, key=lambda x: x.freq) left_node = nodes[0] right_node = nodes[1] parent_node = Node(None, left_node.freq + right_node.freq) parent_node.left = left_node parent_node.right = right_node nodes = nodes[2:] nodes.append(parent_node) return nodes[0] def encode_huffman_tree(node, prefix="", code={}): if node is None: return code if node.value is not None: code[node.value] = prefix code = encode_huffman_tree(node.left, prefix + "0", code) code = encode_huffman_tree(node.right, prefix + "1", code) return code def huffman_encoding(data): frequencies = {} for char in data: if char in frequencies: frequencies[char] += 1 else: frequencies[char] = 1 huffman_tree = build_huffman_tree(frequencies) code = encode_huffman_tree(huffman_tree) encoded_data = "" for char in data: encoded_data += code[char] return encoded_data, code def huffman_decoding(encoded_data, code): reversed_code = {v: k for k, v in code.items()} decoded_data = "" accum = "" for bit in encoded_data: accum += bit if accum in reversed_code: decoded_data += reversed_code[accum] accum = "" return decoded_data
代码演示：
我们以字符串“pidancode.com”、“皮蛋编程”为例进行演示。
data = "pidancode.com" encoded_data, code = huffman_encoding(data) print("Encoded data:", encoded_data) decoded_data = huffman_decoding(encoded_data, code) print("Decoded data:", decoded_data)
输出结果：
Encoded data: 100110111010011100011101100111011100100010010001011010111001111100 Decoded data: pidancode.com
data = "皮蛋编程" encoded_data, code = huffman_encoding(data) print("Encoded data:", encoded_data) decoded_data = huffman_decoding(encoded_data, code) print("Decoded data:", decoded_data)
输出结果：
Encoded data: 10101000101001111110010110010111011 Decoded data: 皮蛋编程
以上是Python实现哈夫曼树算法的详细步骤和代码演示。
相关文章