刚学《数据结构》的时候我把哈夫曼树当成一棵“考试树”——背下构造方法算对 WPL画完一棵树交卷然后就想当然地认为这玩意儿跟实际开发没什么关系。直到后来做文件压缩相关的需求我才发现自己错得离谱ZIP、gzip、PNG、JPEG、MP3这些天天在用的格式底层几乎都有哈夫曼编码的影子。这篇文章我把哈夫曼树和哈夫曼编码的构造方法从头到尾拆一遍包含完整的手算过程、贪心思想为什么成立、一套可以直接跑通的 Python 实现以及我自己调试时踩过的坑。无论你是正在备考数据结构的学生还是想真正搞懂压缩原理的开发者建议跟着手动建一棵树再跑一遍代码。只要走完这两步这个知识点基本就焊死在脑子里了。1. 先搞清楚哈夫曼树到底是什么1.1 从“路径长度”到“带权路径长度”要理解哈夫曼树绕不开两个概念路径长度和带权路径长度。在二叉树里从根节点往下走到某个节点所经过的边的条数就是该节点的路径长度。根节点自己的路径长度是 0它的左右孩子是 1再往下是 2以此类推。那“带权路径长度”加了个“带权”意思是每个节点不再一视同仁。假设一棵树的 n 个叶子节点分别带有权重 w₁、w₂、……、wₙ其中第 i 个叶子节点深度是 lᵢ那么整棵树的带权路径长度定义为WPL w₁ × l₁ w₂ × l₂ …… wₙ × lₙ这里每个权重乘的是它所在叶子节点的深度。为什么要乘深度因为在一个实际场景里深度往往代表代价。比如用一棵树来做编码深度就是编码长度用一棵树来做决策深度就是判定次数。权重越大的节点越希望它待在离根近的地方这样总代价才小。哈夫曼树又叫最优二叉树就是给定一组叶子节点的权重在所有这些叶子构成的二叉树里构造出 WPL 最小的一棵。它不一定是唯一的但它的带权路径长度一定是最小的。1.2 为什么 WPL 越小越好用一个非常具体的例子来说明。假设五个字符的出现次数分别是 2、3、5、7、11如果随便摆一棵二叉树比如把权重最小的 2 放在最靠近根的位置权重最大的 11 反而沉在最底层得到一棵极度倾斜的树它的 WPL 是2×1 3×2 5×3 7×4 11×4 2 6 15 28 44 95这个值非常大。原因很直观11 这个最常用的字符被分到了 4 层深的位置每次编码它都要多花好几个 bit代价被成倍放大了。那怎么安排才合理核心直觉就一句话权重越大的叶子离根越近。哈夫曼的构造方法恰恰保证了这一点。同样五个权重按哈夫曼算法建出来的树WPL 只有 60。同样是编码这五个字符一个用 95 个 bit一个用 60 个 bit差了将近 40。这就是最优树和普通树的差距。如果把这些权重理解成字符在文本中的出现频率那 WPL 就直接对应编码后的总比特数。压缩的本质就是把频率高的东西用短码表示频率低的东西用长码表示。哈夫曼把这件事做到了给定频率分布下的最优。2. 哈夫曼树的构造方法贪心思想的直观与证明2.1 构造算法的四个步骤哈夫曼树构造算法可能是整个数据结构课程里最“无脑”的贪心算法之一本质就是反复做同一件事。完整流程如下把每个权重都看成森林里的一棵单节点树所有根节点组成一个集合。从集合里挑出根节点权重最小的两棵树。把这两棵树作为左右子树合并出一棵新树新根的权重等于两者之和。把新树放回集合重复第 2 步直到集合里只剩一棵树。这个反复“挑最小、合并、放回去”的过程一共要执行 n-1 次。初始有 n 棵树每合并一次减少一棵最后剩一棵就是哈夫曼树。整个过程不需要回溯不需要调整前面的结构贪心到底。为什么用“每次都选最小”就能得到全局最优而不是局部最优陷阱这是整个算法最值得琢磨的地方后面我会专门解释。先看一遍完整手算过程对这个算法形成肌肉记忆。2.2 一步步建树2、3、5、7、11 的完整过程以权重集合 {2, 3, 5, 7, 11} 为例跟着走一遍。初始森林里有五棵单节点树。每一轮都取两个最小根权重合并过程如下表轮次当前森林根权重选中的两个权重合并后的新权重12, 3, 5, 7, 112, 3525, 5, 7, 115, 51037, 10, 117, 1017411, 1711, 1728重点看一下第 2 轮这时集合里有两个 5一个是原始的叶子节点 5一个是第 1 轮合并出来的内部节点 5。它们权重相同选谁当左谁当右都行没有任何区别最终树的形状细节可能不同但 WPL 完全一样。这里唯一的注意点是内部节点和叶子节点权重相等的概率很高处理时不要搞混它们背后的结构只要权重数值参与比较即可。最后一轮合并出的根节点权重 28正好等于所有叶子权重之和。这也能用来检验整个过程有没有算错。2.3 贪心为什么是对的很多人学到这里会有一个疑问每次只选两个最小的万一这一步选了后面就亏了怎么办这个问题值得认真回答因为理解了它才算真正理解哈夫曼算法的灵魂。标准的证明思路是“交换论证”。考虑一棵真正最优的树深度最深的两个叶子节点它们的权重必然是所有叶子中最小的两个。为什么假设最深的叶子中有一个节点的权重 x它不是最小的而另有一个权重更小的节点 y 待在更浅的位置那把 x 和 y 交换x 上移、y 下移。因为 x 的权重大但路径变短y 的权重小但路径变长整体 WPL 必然会下降。既然交换前已经是最优说明这种局面不可能存在所以最深的两个叶子必然是最小的两个权重。既然两个最小权重的叶子在最深层那把它们合并成一个父节点用“父节点权重 两者之和”替代它们问题的规模就从 n 个叶子缩小到 n-1 个最小性不受影响。每合并一次就等价于在原问题上做一次最优子结构的拆解。反复归纳下去每一步“选两个最小”的操作都被证明是安全的。这就是为什么哈夫曼树成为贪心算法的经典案例。它不是碰巧好用而是有严格的交换论证做保证。面试或者考试里如果被问到“为什么哈夫曼一定最优”把这个论证讲清楚基本就稳了。3. 从哈夫曼树到哈夫曼编码压缩的本质3.1 前缀编码为什么解码不会产生歧义树建好了接下来就要给它一个用途。最经典的应用是哈夫曼编码把每个叶子节点对应一个字符从根出发往左走记 0往右走记 1走到某个叶子节点停下的路径就是该字符的编码。这种编码方式有一个极其重要的性质它一定是前缀编码。所谓前缀编码是指任何一个字符的编码都不能是另一个字符编码的前缀。最简单的反例是如果 a 的编码是 0b 的编码是 1c 的编码是 01那么收到一段“01”你根本不知道是 c 还是 a 后面跟着 b这就是歧义。哈夫曼编码不会出现这种问题因为每个字符都对应一个叶子节点从根到叶子的路径是完整的不可能出现“走到某个中间节点刚好停住”的情况。解码的时候一路顺着 0 和 1 往下走走到叶子就只能确定一个字符然后回到根继续。这就是前缀编码天生无歧义的底层原因。可以拿生活中的例子类比你给同事安排值班表为了减少记录量给高频出现的同事用最简短的代号低频的同事用长一点的代号但前提是任何一个人的代号不能是另一个代号的开头否则一登记就容易读串。哈夫曼编码就是在这种约束下把总记录长度压缩到最小。3.2 编码表生成与实例回到刚才建好的哈夫曼树按“左 0 右 1”的约定从上到下读出叶子编码。为了看清楚完整结构我把树展开描述一遍根节点 28左孩子是叶子 11右孩子是内部节点 1717 的左孩子是叶子 7右孩子是内部节点 1010 的左孩子是内部节点 5右孩子是叶子 5最底下内部节点 5 的左右孩子分别是叶子 2 和叶子 3。按照这个结构从上到下给每个叶子编号得到以下编码表字符权重哈夫曼编码编码长度1101710251113211004311014验证一下总比特数11×1 7×2 5×3 2×4 3×4 60正好等于哈夫曼树的 WPL。这里能看到一个很有意思的对应关系WPL 不只是树的带权路径长度它同时就是在每个字符出现次数为权重的序列中用哈夫曼编码压缩后的总比特数。树的深度就是编码长度权重就是频率这两个视角实际上是同一件事。注意哈夫曼编码不是唯一的。如果某几轮合并时权重相等左右子树对调或者把“左 0 右 1”的约定换成“左 1 右 0”都会产生不同形式的编码但这些编码的总长度是一样的都是最优的。平时做题或者看别人的代码只要保证“建树规则一致、左右约定一致”结果就是自洽的。3.3 解码过程解码是编码的逆过程逻辑反而比编码更简单。拿到比特流之后从根节点开始遇到 0 走左遇到 1 走右每走到一个叶子节点就还原出一个字符然后立刻回到根节点继续消费后面的比特。比如用刚才的编码表比特流“010111001101”从左往右解0 到叶子 11解出第一个字符接着走右 1 再走左 0到叶子 7然后 111 到叶子 5接着 1100 到叶子 2最后 1101 到叶子 3。整个过程一气呵成中间不需要任何回溯因为前缀编码保证了解码路径不会走进死胡同。这里要特别强调一个工程项目里容易忽略的点解码端必须拥有和编码端完全一致的树或者完全一致的编码表。树如果对不上解码结果就是一堆乱码。所以真实压缩格式里要么把树结构写进文件头要么用一个更聪明的办法——只存每个字符的编码长度见后面第 5 章的规范哈夫曼编码。4. 代码实现手写一遍比看十遍更管用4.1 用最小堆实现构造哈夫曼算法的核心操作是“反复取集合里权值最小的两个元素”。这个需求天然适合用最小堆来实现。Python 里直接用heapq每次取出两个最小根合并后 push 回去n-1 轮就得到整棵树的根。我写了一段自认为比较干净的最小实现包含了建树、编码表生成、编码和解码四个部分import heapq from collections import Counter class HuffNode: 哈夫曼树节点 def __init__(self, weight, symbolNone, leftNone, rightNone): self.weight weight # 权重也就是出现次数 self.symbol symbol # 叶子节点对应的字符内部节点为 None self.left left self.right right def is_leaf(self): return self.symbol is not None def __lt__(self, other): # heap 比较节点时按权重权重相同的情况保持一致性即可 return self.weight other.weight def build_huffman_tree(freq): freq 是 dict 或 Counter例如 {a: 5, b: 9, c: 12} heap [HuffNode(w, ch) for ch, w in freq.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) parent HuffNode(left.weight right.weight, leftleft, rightright) heapq.heappush(heap, parent) return heap[0] if heap else None def generate_code_table(node, code, tableNone): 深度优先遍历生成 字符 - 编码 的映射表 if table is None: table {} if node.is_leaf(): table[node.symbol] code else: generate_code_table(node.left, code 0, table) generate_code_table(node.right, code 1, table) return table有一个极易写错的细节__lt__这个方法。heapq在比较堆元素时如果两个重量相等就会尝试比较对象本身而 Python 对象默认没有可比较的大小关系不实现__lt__会在合并相等权重时直接给你抛TypeError。这是新手写哈夫曼实现最常见的崩溃点之一。4.2 编码、解码与比特打包建树之后编码就是对原文本统计频率然后逐个查表替换。解码则像前面说的沿着树往下走。完整过程看这段def huffman_encode(text): freq Counter(text) if not freq: return {} if len(freq) 1: # 只有一种字符时没有真正的树约定编码为 0 return {next(iter(freq)): 0} root build_huffman_tree(freq) return generate_code_table(root) def huffman_decode(bit_string, root): result [] node root for bit in bit_string: node node.left if bit 0 else node.right if node.is_leaf(): result.append(node.symbol) node root return .join(result)解码函数有个隐藏假设传入的root和编码时使用的树完全一致。工程上把整棵树序列化存进文件是可行的但会占用不小的空间。实际压缩格式通常不直接存树而是存每个字符的编码长度然后用“规范哈夫曼编码”在解码端重建编码表。这个技巧能显著减少文件头体积后面会展开讲。另外huffman_encode返回的是字符到二进制字符串的映射真正写文件时不能把 “0” 和 “1” 当成字符写进去那样反而把数据撑大了。正确做法是把每 8 个 bit 打包成一个字节。打包逻辑很简单但很多初学压缩的人会栽在这里def bits_to_bytes(bits): 把 0101... 形式的字符串打包成字节序列最后不足 8 位补 0 buf bytearray() for i in range(0, len(bits), 8): byte 0 for j, bit in enumerate(bits[i:i 8]): byte | int(bit) (7 - j) buf.append(byte) return bytes(buf)解码端拿到字节后首先要做逆操作把每个字节展开成 8 位比特再送入哈夫曼树解码。头文件里的长度信息或者特殊的结束标记就是用来应对最后那几位补零问题的。4.3 复杂度分析整个哈夫曼构造过程的复杂度非常好算初始建堆是 O(n)其中 n 是叶子节点数量之后要合并 n-1 次每次涉及两次弹出和一次压入每次堆操作都是 O(log n)。所以总体复杂度是 O(n log n)。编码阶段如果做成查表每编码一个字符的时间是 O(1)遍历整段文本就是 O(m)m 是文本长度。解码阶段稍有不同每还原一个字符都要从根重新走到叶子路径长度就是编码长度平均意义上接近 O(1) 常数最坏情况下接近 O(n)。整体来看哈夫曼的编解码速度非常快这也是它几十年后依然活跃在各类压缩算法底层的原因之一。空间方面额外需要 O(n) 存堆和树。对字符集 256 的字节流来说n 最多 256代价完全可以忽略。所以哈夫曼是那种“时间又快、空间又省、实现又简单”的算法非常难得。5. 常见问题排查与避坑记录5.1 构造阶段的常见错误我见过好几次有人把内部节点当成叶子节点在合并完之后竟然继续用原来的两个叶子去参与下一轮比较导致整个树的结构完全错误。记住权重 5 的叶子一旦和权重 2、3 合并这个 5 就“消失”了取而代之的是一个新创建的内部节点 5。旧节点不再属于森林否则会出现重复计数。还有个考试高频陷阱内部节点不能携带字符。哈夫曼编码的字符只允许出现在叶子节点上如果为了让某个字符的编码更短而把它放到内部节点就会立刻破坏前缀编码的性质。判断一棵树是不是合法的哈夫曼树先看字符是不是都在叶子上再看 WPL 是不是最小顺序别搞反。5.2 编码和解码阶段的坑左右子树约定不一致是个隐蔽问题。有的人建树时习惯“左小右大”生成编码时却按“左 1 右 0”两套规则打架最后解出来的文本首尾错乱。建议在代码里把约定固定成一个全局常量比如LEFT_BIT 0、RIGHT_BIT 1不要散落在多个函数里手写 0 和 1。单字符输入是另一个边界问题。如果整个文本只有一种字符比如全是“a”那哈夫曼树退化成只有一个节点按正常流程走下来编码表里 a 的编码是空字符串。空编码没法写文件必须在编码前单独处理我习惯直接把唯一字符的编码约定为 “0”并在文件头记录一个标志。最后就是存储问题。一次压缩流程的完整数据包应该包含哈夫曼树或编码长度表、编码后的比特流、必要的长度信息。很多人自己玩的时候只写了编码和解码函数却忘了把树存下来结果是压缩完自己都解不开。设计文件格式时把头部信息、数据区和长度标记三件事一起规划清楚。5.3 工程化的几个进阶技巧如果只是应付考试知道前面这些已经够了。但想在真实项目里用得顺手再补两个实战技巧。第一个是规范哈夫曼编码。它的思路是解码端其实不需要知道树长什么样只需要知道每个字符的编码长度。按“码长递增、同码长按字符顺序”的规则就能推导出一套唯一的规范编码。像 DEFLATE 算法ZIP、gzip、PNG 都用它就采用这种方案文件头只存码长序列省掉了一大块树结构数据。第二个是比特流边界处理。真实编码时最后一组可能凑不满 8 个 bit打包时会补 0。解码端如果不记录原始比特长度就会把补的 0 当成有效数据。常见做法是在文件头保存“最后一个字节的有效位数”或者保存原始比特流总长度二选一但绝不能两个都不写。6. 哈夫曼编码在真实世界中的位置6.1 哪些压缩算法在用哈夫曼哈夫曼编码至今仍然是许多主流压缩格式的重要基石。DEFLATE 把 LZ77 窗口匹配和哈夫曼编码结合广泛用于 ZIP、gzip、PNG 图像。JPEG 在量化后的 DCT 系数上使用哈夫曼编码MP3 和许多视频编码标准同样包含哈夫曼风格的熵编码环节。传真机协议比如 CCITT Group 3也用了类似思想。可以说凡是需要“把分布不均匀的符号变成尽量短的比特流”的场景几乎都能看到哈夫曼的影子。6.2 哈夫曼编码的局限与替代方案但哈夫曼也有它的天花板每个符号的编码长度必须是整数个 bit。如果某个字符的真实概率是 1/3理论上最优编码长度是 log₂3 ≈ 1.585 bit哈夫曼却只能分配 1 bit 或 2 bit必然产生浪费。概率分布越“偏”这种整数长度限制造成的损失越明显。算术编码、区间编码和近年流行的 rANS 熵编码可以做到接近理论极限的分数比特编码这就是为什么现代压缩算法如 LZMA、Brotli、Zstandard更倾向于使用这些更复杂的熵编码器而非纯粹的哈夫曼。6.3 动手做个小实验写代码跑一个实验比背十遍原理都管用。我建议你拿一本英文电子书的前几章做素材统计一下字符频率然后实现哈夫曼编码对比压缩前后的大小。大概率你会得到一个 1.5 到 2 倍左右的压缩率然后再试试把“the”这种高频单词当作一个整体符号参与统计压缩率会进一步提升。把这个实验做完你对“频率如何决定编码长度”的体会会深刻很多。我自己当时做这个小实验时还有意外的收获发现同样的频率表左右子树对调之后编码完全变了但总长度不变。这让我彻底理解了“最优”指的是总代价最优而不是编码形式唯一。也正因为这一点面试官特别喜欢在这里追加提问“哈夫曼编码唯一吗”。答案是不唯一但最优长度是确定的先想清楚这层后面遇到再刁钻的变形题也不慌。 
长河君 · 2026/10/10 21:28:36 · 阅读 1.2k 哈夫曼树与哈夫曼编码详解：从手算到Python实现
刚学《数据结构》的时候我把哈夫曼树当成一棵“考试树”——背下构造方法算对 WPL画完一棵树交卷然后就想当然地认为这玩意儿跟实际开发没什么关系。直到后来做文件压缩相关的需求我才发现自己错得离谱ZIP、gzip、PNG、JPEG、MP3这些天天在用的格式底层几乎都有哈夫曼编码的影子。这篇文章我把哈夫曼树和哈夫曼编码的构造方法从头到尾拆一遍包含完整的手算过程、贪心思想为什么成立、一套可以直接跑通的 Python 实现以及我自己调试时踩过的坑。无论你是正在备考数据结构的学生还是想真正搞懂压缩原理的开发者建议跟着手动建一棵树再跑一遍代码。只要走完这两步这个知识点基本就焊死在脑子里了。1. 先搞清楚哈夫曼树到底是什么1.1 从“路径长度”到“带权路径长度”要理解哈夫曼树绕不开两个概念路径长度和带权路径长度。在二叉树里从根节点往下走到某个节点所经过的边的条数就是该节点的路径长度。根节点自己的路径长度是 0它的左右孩子是 1再往下是 2以此类推。那“带权路径长度”加了个“带权”意思是每个节点不再一视同仁。假设一棵树的 n 个叶子节点分别带有权重 w₁、w₂、……、wₙ其中第 i 个叶子节点深度是 lᵢ那么整棵树的带权路径长度定义为WPL w₁ × l₁ w₂ × l₂ …… wₙ × lₙ这里每个权重乘的是它所在叶子节点的深度。为什么要乘深度因为在一个实际场景里深度往往代表代价。比如用一棵树来做编码深度就是编码长度用一棵树来做决策深度就是判定次数。权重越大的节点越希望它待在离根近的地方这样总代价才小。哈夫曼树又叫最优二叉树就是给定一组叶子节点的权重在所有这些叶子构成的二叉树里构造出 WPL 最小的一棵。它不一定是唯一的但它的带权路径长度一定是最小的。1.2 为什么 WPL 越小越好用一个非常具体的例子来说明。假设五个字符的出现次数分别是 2、3、5、7、11如果随便摆一棵二叉树比如把权重最小的 2 放在最靠近根的位置权重最大的 11 反而沉在最底层得到一棵极度倾斜的树它的 WPL 是2×1 3×2 5×3 7×4 11×4 2 6 15 28 44 95这个值非常大。原因很直观11 这个最常用的字符被分到了 4 层深的位置每次编码它都要多花好几个 bit代价被成倍放大了。那怎么安排才合理核心直觉就一句话权重越大的叶子离根越近。哈夫曼的构造方法恰恰保证了这一点。同样五个权重按哈夫曼算法建出来的树WPL 只有 60。同样是编码这五个字符一个用 95 个 bit一个用 60 个 bit差了将近 40。这就是最优树和普通树的差距。如果把这些权重理解成字符在文本中的出现频率那 WPL 就直接对应编码后的总比特数。压缩的本质就是把频率高的东西用短码表示频率低的东西用长码表示。哈夫曼把这件事做到了给定频率分布下的最优。2. 哈夫曼树的构造方法贪心思想的直观与证明2.1 构造算法的四个步骤哈夫曼树构造算法可能是整个数据结构课程里最“无脑”的贪心算法之一本质就是反复做同一件事。完整流程如下把每个权重都看成森林里的一棵单节点树所有根节点组成一个集合。从集合里挑出根节点权重最小的两棵树。把这两棵树作为左右子树合并出一棵新树新根的权重等于两者之和。把新树放回集合重复第 2 步直到集合里只剩一棵树。这个反复“挑最小、合并、放回去”的过程一共要执行 n-1 次。初始有 n 棵树每合并一次减少一棵最后剩一棵就是哈夫曼树。整个过程不需要回溯不需要调整前面的结构贪心到底。为什么用“每次都选最小”就能得到全局最优而不是局部最优陷阱这是整个算法最值得琢磨的地方后面我会专门解释。先看一遍完整手算过程对这个算法形成肌肉记忆。2.2 一步步建树2、3、5、7、11 的完整过程以权重集合 {2, 3, 5, 7, 11} 为例跟着走一遍。初始森林里有五棵单节点树。每一轮都取两个最小根权重合并过程如下表轮次当前森林根权重选中的两个权重合并后的新权重12, 3, 5, 7, 112, 3525, 5, 7, 115, 51037, 10, 117, 1017411, 1711, 1728重点看一下第 2 轮这时集合里有两个 5一个是原始的叶子节点 5一个是第 1 轮合并出来的内部节点 5。它们权重相同选谁当左谁当右都行没有任何区别最终树的形状细节可能不同但 WPL 完全一样。这里唯一的注意点是内部节点和叶子节点权重相等的概率很高处理时不要搞混它们背后的结构只要权重数值参与比较即可。最后一轮合并出的根节点权重 28正好等于所有叶子权重之和。这也能用来检验整个过程有没有算错。2.3 贪心为什么是对的很多人学到这里会有一个疑问每次只选两个最小的万一这一步选了后面就亏了怎么办这个问题值得认真回答因为理解了它才算真正理解哈夫曼算法的灵魂。标准的证明思路是“交换论证”。考虑一棵真正最优的树深度最深的两个叶子节点它们的权重必然是所有叶子中最小的两个。为什么假设最深的叶子中有一个节点的权重 x它不是最小的而另有一个权重更小的节点 y 待在更浅的位置那把 x 和 y 交换x 上移、y 下移。因为 x 的权重大但路径变短y 的权重小但路径变长整体 WPL 必然会下降。既然交换前已经是最优说明这种局面不可能存在所以最深的两个叶子必然是最小的两个权重。既然两个最小权重的叶子在最深层那把它们合并成一个父节点用“父节点权重 两者之和”替代它们问题的规模就从 n 个叶子缩小到 n-1 个最小性不受影响。每合并一次就等价于在原问题上做一次最优子结构的拆解。反复归纳下去每一步“选两个最小”的操作都被证明是安全的。这就是为什么哈夫曼树成为贪心算法的经典案例。它不是碰巧好用而是有严格的交换论证做保证。面试或者考试里如果被问到“为什么哈夫曼一定最优”把这个论证讲清楚基本就稳了。3. 从哈夫曼树到哈夫曼编码压缩的本质3.1 前缀编码为什么解码不会产生歧义树建好了接下来就要给它一个用途。最经典的应用是哈夫曼编码把每个叶子节点对应一个字符从根出发往左走记 0往右走记 1走到某个叶子节点停下的路径就是该字符的编码。这种编码方式有一个极其重要的性质它一定是前缀编码。所谓前缀编码是指任何一个字符的编码都不能是另一个字符编码的前缀。最简单的反例是如果 a 的编码是 0b 的编码是 1c 的编码是 01那么收到一段“01”你根本不知道是 c 还是 a 后面跟着 b这就是歧义。哈夫曼编码不会出现这种问题因为每个字符都对应一个叶子节点从根到叶子的路径是完整的不可能出现“走到某个中间节点刚好停住”的情况。解码的时候一路顺着 0 和 1 往下走走到叶子就只能确定一个字符然后回到根继续。这就是前缀编码天生无歧义的底层原因。可以拿生活中的例子类比你给同事安排值班表为了减少记录量给高频出现的同事用最简短的代号低频的同事用长一点的代号但前提是任何一个人的代号不能是另一个代号的开头否则一登记就容易读串。哈夫曼编码就是在这种约束下把总记录长度压缩到最小。3.2 编码表生成与实例回到刚才建好的哈夫曼树按“左 0 右 1”的约定从上到下读出叶子编码。为了看清楚完整结构我把树展开描述一遍根节点 28左孩子是叶子 11右孩子是内部节点 1717 的左孩子是叶子 7右孩子是内部节点 1010 的左孩子是内部节点 5右孩子是叶子 5最底下内部节点 5 的左右孩子分别是叶子 2 和叶子 3。按照这个结构从上到下给每个叶子编号得到以下编码表字符权重哈夫曼编码编码长度1101710251113211004311014验证一下总比特数11×1 7×2 5×3 2×4 3×4 60正好等于哈夫曼树的 WPL。这里能看到一个很有意思的对应关系WPL 不只是树的带权路径长度它同时就是在每个字符出现次数为权重的序列中用哈夫曼编码压缩后的总比特数。树的深度就是编码长度权重就是频率这两个视角实际上是同一件事。注意哈夫曼编码不是唯一的。如果某几轮合并时权重相等左右子树对调或者把“左 0 右 1”的约定换成“左 1 右 0”都会产生不同形式的编码但这些编码的总长度是一样的都是最优的。平时做题或者看别人的代码只要保证“建树规则一致、左右约定一致”结果就是自洽的。3.3 解码过程解码是编码的逆过程逻辑反而比编码更简单。拿到比特流之后从根节点开始遇到 0 走左遇到 1 走右每走到一个叶子节点就还原出一个字符然后立刻回到根节点继续消费后面的比特。比如用刚才的编码表比特流“010111001101”从左往右解0 到叶子 11解出第一个字符接着走右 1 再走左 0到叶子 7然后 111 到叶子 5接着 1100 到叶子 2最后 1101 到叶子 3。整个过程一气呵成中间不需要任何回溯因为前缀编码保证了解码路径不会走进死胡同。这里要特别强调一个工程项目里容易忽略的点解码端必须拥有和编码端完全一致的树或者完全一致的编码表。树如果对不上解码结果就是一堆乱码。所以真实压缩格式里要么把树结构写进文件头要么用一个更聪明的办法——只存每个字符的编码长度见后面第 5 章的规范哈夫曼编码。4. 代码实现手写一遍比看十遍更管用4.1 用最小堆实现构造哈夫曼算法的核心操作是“反复取集合里权值最小的两个元素”。这个需求天然适合用最小堆来实现。Python 里直接用heapq每次取出两个最小根合并后 push 回去n-1 轮就得到整棵树的根。我写了一段自认为比较干净的最小实现包含了建树、编码表生成、编码和解码四个部分import heapq from collections import Counter class HuffNode: 哈夫曼树节点 def __init__(self, weight, symbolNone, leftNone, rightNone): self.weight weight # 权重也就是出现次数 self.symbol symbol # 叶子节点对应的字符内部节点为 None self.left left self.right right def is_leaf(self): return self.symbol is not None def __lt__(self, other): # heap 比较节点时按权重权重相同的情况保持一致性即可 return self.weight other.weight def build_huffman_tree(freq): freq 是 dict 或 Counter例如 {a: 5, b: 9, c: 12} heap [HuffNode(w, ch) for ch, w in freq.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) parent HuffNode(left.weight right.weight, leftleft, rightright) heapq.heappush(heap, parent) return heap[0] if heap else None def generate_code_table(node, code, tableNone): 深度优先遍历生成 字符 - 编码 的映射表 if table is None: table {} if node.is_leaf(): table[node.symbol] code else: generate_code_table(node.left, code 0, table) generate_code_table(node.right, code 1, table) return table有一个极易写错的细节__lt__这个方法。heapq在比较堆元素时如果两个重量相等就会尝试比较对象本身而 Python 对象默认没有可比较的大小关系不实现__lt__会在合并相等权重时直接给你抛TypeError。这是新手写哈夫曼实现最常见的崩溃点之一。4.2 编码、解码与比特打包建树之后编码就是对原文本统计频率然后逐个查表替换。解码则像前面说的沿着树往下走。完整过程看这段def huffman_encode(text): freq Counter(text) if not freq: return {} if len(freq) 1: # 只有一种字符时没有真正的树约定编码为 0 return {next(iter(freq)): 0} root build_huffman_tree(freq) return generate_code_table(root) def huffman_decode(bit_string, root): result [] node root for bit in bit_string: node node.left if bit 0 else node.right if node.is_leaf(): result.append(node.symbol) node root return .join(result)解码函数有个隐藏假设传入的root和编码时使用的树完全一致。工程上把整棵树序列化存进文件是可行的但会占用不小的空间。实际压缩格式通常不直接存树而是存每个字符的编码长度然后用“规范哈夫曼编码”在解码端重建编码表。这个技巧能显著减少文件头体积后面会展开讲。另外huffman_encode返回的是字符到二进制字符串的映射真正写文件时不能把 “0” 和 “1” 当成字符写进去那样反而把数据撑大了。正确做法是把每 8 个 bit 打包成一个字节。打包逻辑很简单但很多初学压缩的人会栽在这里def bits_to_bytes(bits): 把 0101... 形式的字符串打包成字节序列最后不足 8 位补 0 buf bytearray() for i in range(0, len(bits), 8): byte 0 for j, bit in enumerate(bits[i:i 8]): byte | int(bit) (7 - j) buf.append(byte) return bytes(buf)解码端拿到字节后首先要做逆操作把每个字节展开成 8 位比特再送入哈夫曼树解码。头文件里的长度信息或者特殊的结束标记就是用来应对最后那几位补零问题的。4.3 复杂度分析整个哈夫曼构造过程的复杂度非常好算初始建堆是 O(n)其中 n 是叶子节点数量之后要合并 n-1 次每次涉及两次弹出和一次压入每次堆操作都是 O(log n)。所以总体复杂度是 O(n log n)。编码阶段如果做成查表每编码一个字符的时间是 O(1)遍历整段文本就是 O(m)m 是文本长度。解码阶段稍有不同每还原一个字符都要从根重新走到叶子路径长度就是编码长度平均意义上接近 O(1) 常数最坏情况下接近 O(n)。整体来看哈夫曼的编解码速度非常快这也是它几十年后依然活跃在各类压缩算法底层的原因之一。空间方面额外需要 O(n) 存堆和树。对字符集 256 的字节流来说n 最多 256代价完全可以忽略。所以哈夫曼是那种“时间又快、空间又省、实现又简单”的算法非常难得。5. 常见问题排查与避坑记录5.1 构造阶段的常见错误我见过好几次有人把内部节点当成叶子节点在合并完之后竟然继续用原来的两个叶子去参与下一轮比较导致整个树的结构完全错误。记住权重 5 的叶子一旦和权重 2、3 合并这个 5 就“消失”了取而代之的是一个新创建的内部节点 5。旧节点不再属于森林否则会出现重复计数。还有个考试高频陷阱内部节点不能携带字符。哈夫曼编码的字符只允许出现在叶子节点上如果为了让某个字符的编码更短而把它放到内部节点就会立刻破坏前缀编码的性质。判断一棵树是不是合法的哈夫曼树先看字符是不是都在叶子上再看 WPL 是不是最小顺序别搞反。5.2 编码和解码阶段的坑左右子树约定不一致是个隐蔽问题。有的人建树时习惯“左小右大”生成编码时却按“左 1 右 0”两套规则打架最后解出来的文本首尾错乱。建议在代码里把约定固定成一个全局常量比如LEFT_BIT 0、RIGHT_BIT 1不要散落在多个函数里手写 0 和 1。单字符输入是另一个边界问题。如果整个文本只有一种字符比如全是“a”那哈夫曼树退化成只有一个节点按正常流程走下来编码表里 a 的编码是空字符串。空编码没法写文件必须在编码前单独处理我习惯直接把唯一字符的编码约定为 “0”并在文件头记录一个标志。最后就是存储问题。一次压缩流程的完整数据包应该包含哈夫曼树或编码长度表、编码后的比特流、必要的长度信息。很多人自己玩的时候只写了编码和解码函数却忘了把树存下来结果是压缩完自己都解不开。设计文件格式时把头部信息、数据区和长度标记三件事一起规划清楚。5.3 工程化的几个进阶技巧如果只是应付考试知道前面这些已经够了。但想在真实项目里用得顺手再补两个实战技巧。第一个是规范哈夫曼编码。它的思路是解码端其实不需要知道树长什么样只需要知道每个字符的编码长度。按“码长递增、同码长按字符顺序”的规则就能推导出一套唯一的规范编码。像 DEFLATE 算法ZIP、gzip、PNG 都用它就采用这种方案文件头只存码长序列省掉了一大块树结构数据。第二个是比特流边界处理。真实编码时最后一组可能凑不满 8 个 bit打包时会补 0。解码端如果不记录原始比特长度就会把补的 0 当成有效数据。常见做法是在文件头保存“最后一个字节的有效位数”或者保存原始比特流总长度二选一但绝不能两个都不写。6. 哈夫曼编码在真实世界中的位置6.1 哪些压缩算法在用哈夫曼哈夫曼编码至今仍然是许多主流压缩格式的重要基石。DEFLATE 把 LZ77 窗口匹配和哈夫曼编码结合广泛用于 ZIP、gzip、PNG 图像。JPEG 在量化后的 DCT 系数上使用哈夫曼编码MP3 和许多视频编码标准同样包含哈夫曼风格的熵编码环节。传真机协议比如 CCITT Group 3也用了类似思想。可以说凡是需要“把分布不均匀的符号变成尽量短的比特流”的场景几乎都能看到哈夫曼的影子。6.2 哈夫曼编码的局限与替代方案但哈夫曼也有它的天花板每个符号的编码长度必须是整数个 bit。如果某个字符的真实概率是 1/3理论上最优编码长度是 log₂3 ≈ 1.585 bit哈夫曼却只能分配 1 bit 或 2 bit必然产生浪费。概率分布越“偏”这种整数长度限制造成的损失越明显。算术编码、区间编码和近年流行的 rANS 熵编码可以做到接近理论极限的分数比特编码这就是为什么现代压缩算法如 LZMA、Brotli、Zstandard更倾向于使用这些更复杂的熵编码器而非纯粹的哈夫曼。6.3 动手做个小实验写代码跑一个实验比背十遍原理都管用。我建议你拿一本英文电子书的前几章做素材统计一下字符频率然后实现哈夫曼编码对比压缩前后的大小。大概率你会得到一个 1.5 到 2 倍左右的压缩率然后再试试把“the”这种高频单词当作一个整体符号参与统计压缩率会进一步提升。把这个实验做完你对“频率如何决定编码长度”的体会会深刻很多。我自己当时做这个小实验时还有意外的收获发现同样的频率表左右子树对调之后编码完全变了但总长度不变。这让我彻底理解了“最优”指的是总代价最优而不是编码形式唯一。也正因为这一点面试官特别喜欢在这里追加提问“哈夫曼编码唯一吗”。答案是不唯一但最优长度是确定的先想清楚这层后面遇到再刁钻的变形题也不慌。