核心内容摘要
LeetCode热题100 将有序数组转换为二叉搜索树
关键特性哈夫曼节点类HuffmanNode存储字符和频率支持堆排序的比较操作哈夫曼树类HuffmanTree从文本或频率字典构建自动生成最优编码支持编码和解码操作核心功能build_from_text(): 从文本构建哈夫曼树encode(): 编码文本为二进制字符串decode(): 解码二进制字符串为文本get_compression_ratio(): 计算压缩率辅助功能可视化树结构需要graphviz计算加权路径长度文件压缩示例实现代码import heapq from collections import defaultdict, Counter from typing import List, Tuple, Optional import graphviz # 可选用于可视化树结构 class HuffmanNode: 哈夫曼树节点类 def __init__(self, char: Optional[str], freq: int): self.char char # 字符叶子节点才有 self.freq freq # 频率 self.left None # 左子节点 self.right None # 右子节点 def __lt__(self, other): # 用于堆排序的比较函数 return self.freq other.freq def __repr__(self): return fNode({self.char}, {self.freq}) class HuffmanTree: 哈夫曼树类 def __init__(self, text: str None): 初始化哈夫曼树 Args: text: 用于构建哈夫曼树的文本 self.root None self.codes {} # 字符到编码的映射 self.reverse_codes {} # 编码到字符的映射 if text: self.build_from_text(text) def build_from_text(self, text: str) - None: 从文本构建哈夫曼树 Args: text: 输入文本 #
统计字符频率 freq_dict Counter(text) #
构建哈夫曼树 self.root self._build_tree(freq_dict) #
生成编码表 self._generate_codes(self.root, ) def _build_tree(self, freq_dict: dict) - HuffmanNode: 构建哈夫曼树的核心算法 Args: freq_dict: 字符频率字典 Returns: 哈夫曼树的根节点 # 创建最小堆 heap [] for char, freq in freq_dict.items(): heapq.heappush(heap, HuffmanNode(char, freq)) # 特殊情况处理只有一个字符 if len(heap) 1: node heapq.heappop(heap) new_node HuffmanNode(None, node.freq) new_node.left node return new_node # 构建哈夫曼树 while len(heap) 1: # 弹出两个最小频率的节点 left heapq.heappop(heap) right heapq.heappop(heap) # 创建新节点频率为两个子节点之和 merged HuffmanNode(None, left.freq right.freq) merged.left left merged.right right # 将新节点放回堆中 heapq.heappush(heap, merged) return heap[0] if heap else None def _generate_codes(self, node: HuffmanNode, code: str) - None: 递归生成哈夫曼编码 Args: node: 当前节点 code: 当前编码字符串 if node is None: return # 如果是叶子节点保存编码 if node.char is not None: self.codes[node.char] code self.reverse_codes[code] node.char return # 递归处理左右子树 self._generate_codes(node.left, code
self._generate_codes(node.right, code
def encode(self, text: str) - str: 编码文本 Args: text: 要编码的文本 Returns: 编码后的二进制字符串 return .join(self.codes[char] for char in text) def decode(self, encoded_text: str) - str: 解码二进制字符串 Args: encoded_text: 编码后的二进制字符串 Returns: 解码后的文本 decoded_text [] current_code node self.root # 特殊情况树只有一个节点 if node.char is not None: return node.char * len(encoded_text) # 遍历编码字符串 for bit in encoded_text: if bit 0: node node.left else: node node.right if node.char is not None: decoded_text.append(node.char) node self.root return .join(decoded_text) def get_compression_ratio(self, original_text: str) - float: 计算压缩率 Args: original_text: 原始文本 Returns: 压缩率压缩后大小 / 原始大小 if not original_text: return 0 # 原始文本大小按字节计算 original_size len(original_text) * 8 # 假设每个字符8位 # 编码后的大小 encoded_text self.encode(original_text) compressed_size len(encoded_text) return compressed_size / original_size def print_tree_info(self) - None: 打印哈夫曼树信息 print(哈夫曼编码表:) for char, code in sorted(self.codes.items()): print(f {char}: {code}) print(f\n总字符数: {len(self.codes)}) def visualize(self, filename: str huffman_tree) - None: 可视化哈夫曼树需要安装graphviz Args: filename: 输出文件名 try: dot graphviz.Digraph(commentHuffman Tree) self._add_nodes(dot, self.root, ) dot.render(filename, viewTrue, formatpng) print(f树结构已保存到 {filename}.png) except ImportError: print(请先安装graphviz: pip install graphviz) def _add_nodes(self, dot, node: HuffmanNode, node_id: str) - None: 递归添加节点到graphviz图 if node is None: return # 创建节点标签 label ffreq: {node.freq} if node.char is not None: label f{node.char}: {node.freq} # 添加节点 dot.node(node_id, label) # 递归添加子节点 if node.left: left_id node_id L dot.edge(node_id, left_id, label
self._add_nodes(dot, node.left, left_id) if node.right: right_id node_id R dot.edge(node_id, right_id, label
self._add_nodes(dot, node.right, right_id) def build_huffman_from_freq(freq_dict: dict) - HuffmanTree: 从频率字典构建哈夫曼树 Args: freq_dict: 字符频率字典 Returns: 哈夫曼树实例 tree HuffmanTree() tree.root tree._build_tree(freq_dict) tree._generate_codes(tree.root, ) return tree def calculate_weighted_path_length(tree: HuffmanTree) - float: 计算哈夫曼树的加权路径长度 Args: tree: 哈夫曼树实例 Returns: 加权路径长度 def dfs(node: HuffmanNode, depth: int) - int: if node is None: return 0 if node.char is not None: return node.freq * depth return dfs(node.left, depth
dfs(node.right, depth
return dfs(tree.root,
if tree.root else 0 # 使用示例 def example_usage(): # 示例1: 基本使用 print( *
print(示例1: 基本使用) print( *
text this is an example for huffman encoding huffman HuffmanTree(text) print(f原始文本: {text}) print(f文本长度: {len(text)} 字符) # 显示编码表 huffman.print_tree_info() # 编码和解码 encoded huffman.encode(text) print(f\n编码结果: {encoded}) print(f编码长度: {len(encoded)} 位) decoded huffman.decode(encoded) print(f解码结果: {decoded}) print(f解码是否正确: {decoded text}) # 计算压缩率 ratio huffman.get_compression_ratio(text) print(f压缩率: {ratio:.2%}) # 计算加权路径长度 wpl calculate_weighted_path_length(huffman) print(f加权路径长度: {wpl}) # 示例2: 从频率字典构建 print(\n *
print(示例2: 从频率字典构建) print( *
freq_dict {a: 5, b: 9, c: 12, d: 13, e: 16, f: 45} tree2 build_huffman_from_freq(freq_dict) tree
print_tree_info() # 测试编码解码 test_text abcdeff encoded2 tree
encode(test_text) decoded2 tree
decode(encoded
print(f\n测试文本: {test_text}) print(f编码结果: {encoded2}) print(f解码结果: {decoded2}) print(f解码是否正确: {decoded2 test_text}) # 高级功能文件压缩示例 class HuffmanFileCompressor: 哈夫曼文件压缩器简化版 staticmethod def compress_text_to_file(text: str, filename: str) - None: 将文本压缩保存到文件 # 构建哈夫曼树 tree HuffmanTree(text) # 编码文本 encoded tree.encode(text) # 保存编码表和编码结果 with open(filename, w, encodingutf-
as f: # 保存编码表 f.write(f{len(tree.codes)}\n) for char, code in tree.codes.items(): # 处理特殊字符如换行符 char_encoded char.encode(unicode_escape).decode(utf-
f.write(f{char_encoded} {code}\n) # 保存编码结果 f.write(encoded) print(f压缩完成文件已保存到: {filename}) # 显示压缩信息 original_bits len(text) * 8 compressed_bits len(encoded) ratio compressed_bits / original_bits print(f原始大小: {original_bits} 位) print(f压缩后大小: {compressed_bits} 位) print(f压缩率: {ratio:.2%}) if __name__ __main__: # 运行示例 example_usage() # 文件压缩示例 print(\n *
print(文件压缩示例) print( *
sample_text hello world! this is huffman compression example. compressor HuffmanFileCompressor() compressor.compress_text_to_file(sample_text, compressed.huff)运行结果Installing collected packages: graphvizSuccessfully installed graphviz-
21(mlstat) [haichaonode01 imagenet]$ python demo
py示例1: 基本使用原始文本: this is an example for huffman encoding文本长度: 39 字符哈夫曼编码表: : 111a: 1011c: 10010d: 00011e: 1010f: 1101g: 01111h: 0011i: 1100l: 01101m: 0010n: 010o: 10011p: 10001r: 01110s: 0000t: 01100u: 00010x: 10000总字符数: 19编码结果: 0110000111100000011111000000111101101011110101000010110010100010110110101111101100110111011100110001011011101001010110101111010010100101001100011110001001111编码长度: 157 位解码结果: this is an example for huffman encoding解码是否正确: True压缩率:
5
32%加权路径长度: 157示例2: 从频率字典构建哈夫曼编码表:a: 1100b: 1101c: 100d: 101e: 111f: 0总字符数: 6测试文本: abcdeff编码结果: 1100110110010111100解码结果: abcdeff解码是否正确: True文件压缩示例压缩完成文件已保存到: compressed.huff原始大小: 392 位压缩后大小: 206 位压缩率:
5