### Huffman 编码 示例代码 为了实现Huffman编码，通常需要完成以下几个部分的工作： #### 构建频率表 首先统计输入数据中各个字符出现的频次。 ```python from collections import defaultdict, heapq def build_frequency_table(data): frequency = defaultdict(int) for char in data: frequency[char] += 1 return frequency ``` #### 创建节点类 定义一个简单的二叉树节点类来存储字符及其权重（即频率），并支持比较操作以便后续构建最小堆[^3]。 ```python class Node: def __init__(self, char, freq): self.char = char self.freq = freq self.left = None self.right = None # 定义小于运算符用于heapq处理 def __lt__(self, other): return self.freq < other.freq ``` #### 建立霍夫曼树 利用优先队列(最小堆)按照节点权值从小到大排列，并不断合并两个最低概率结点直到只剩下一个根节点为止形成完整的霍夫曼树[^1]。 ```python def build_huffman_tree(frequency): heap = [Node(char, freq) for char, freq in frequency.items()] heapq.heapify(heap) while len(heap) > 1: node1 = heapq.heappop(heap) node2 = heapq.heappop(heap) merged_node = Node(None, node1.freq + node2.freq) merged_node.left = node1 merged_node.right = node2 heapq.heappush(heap, merged_node) return heap[0] if heap else None ``` #### 生成霍夫曼编码 遍历霍夫曼树自顶向下为每一个叶子节点分配唯一的前缀码串。 ```python codes = {} def generate_huffman_codes(node, current_code=""): if not node: return if node.char is not None: codes[node.char] = current_code or "0" generate_huffman_codes(node.left, current_code + "0") generate_huffman_codes(node.right, current_code + "1") # 调用此函数以填充全局变量`codes` generate_huffman_codes(build_huffman_tree(build_frequency_table('your input string'))) ``` #### 数据编解码过程 最后还需要编写辅助函数来进行实际的数据压缩与还原工作[^2]。 ```python def encode_data(data): global codes encoded_output = "" for character in data: encoded_output += codes[character] return encoded_output def decode_data(encoded_string, root): decoded_output = [] current_node = root for bit in encoded_string: if int(bit) == 0 and current_node.left: current_node = current_node.left elif int(bit) == 1 and current_node.right: current_node = current_node.right if current_node.char is not None: decoded_output.append(current_node.char) current_node = root return ''.join(decoded_output) if __name__ == "__main__": test_input = 'this is an example of a huffman tree' frequency_dict = build_frequency_table(test_input) huffman_root = build_huffman_tree(frequency_dict) generate_huffman_codes(huffman_root) compressed_text = encode_data(test_input) print(compressed_text) original_text = decode_data(compressed_text, huffman_root) print(original_text) ```