### 霍夫曼编码的Python实现 霍夫曼编码是一种用于无损数据压缩的技术，通过构建最优前缀码来减少冗余。下面是一个基于给定字符频率创建霍夫曼树并生成相应编码的过程[^1]。 #### 构建霍夫曼树 为了有效地处理字符及其对应的权重（即出现次数），可以定义一个节点类`HuffmanTree`表示二叉树中的每一个结点： ```python class HuffmanTreeNode: def __init__(self, char=None, freq=0, left=None, right=None): self.char = char # 字符 self.freq = freq # 出现频次 self.left = left # 左子树 self.right = right # 右子树 def __lt__(self, other): # 定义小于运算符以便后续排序操作 return self.freq < other.freq ``` 接着利用优先队列(最小堆)存储这些节点对象，并按照它们所代表符号的概率大小依次取出两个概率最低者组合成新的内部节点直到只剩下一个根节点为止: ```python import heapq def build_huffman_tree(frequencies_dict): heap = [] for ch, fr in frequencies_dict.items(): node = HuffmanTreeNode(ch, fr) heapq.heappush(heap, (fr, id(node), node)) # 使用id防止相同频率时比较node实例 while len(heap) > 1: _, _ ,left_node = heapq.heappop(heap) _, _ ,right_node = heapq.heappop(heap) merged_freq = left_node.freq + right_node.freq parent_node = HuffmanTreeNode(None, merged_freq, left_node, right_node) heapq.heappush(heap, (merged_freq, id(parent_node), parent_node)) return None if not heap else heapq.heappop(heap)[2] ``` #### 生成霍夫曼编码字典 一旦获得了完整的霍夫曼树结构，则可以通过遍历整棵树的方式获取每一片叶节点对应的最佳路径表达形式——也就是最终想要得到的那个唯一最短编码方案列表： ```python def generate_codes(root, prefix="", codebook={}): if root is None: return if root.char is not None: codebook[root.char] = prefix or "0" generate_codes(root.left, prefix+"0", codebook) generate_codes(root.right, prefix+"1", codebook) return codebook ``` 最后一步就是调用上述函数完成整个流程并将结果返回给用户查看或进一步应用到实际场景当中去了。