每日一题做到第三天不少刷题群里已经有人开始“怎么又是树”的哀嚎了。今天这道题叫哈夫曼编码题目描述通常很简单但真正让人卡住的往往不是题目本身而是它背后连着的一条完整知识链贪心策略、优先队列、二叉树遍历、前缀编码、WPL 计算甚至几句就能扯到 gzip、JPEG 这些日常都在用的压缩技术。哈夫曼编码是 David Huffman 在 1952 年提出的无损数据压缩算法核心思想可以压缩成一句话给出现频率高的字符配短编码给出现频率低的字符配长编码让整段文本最终占用的二进制位数最少。这句话不难懂但如果你没亲手把一棵哈夫曼树建出来、把一串 01 解回原文你会觉得它像一个“听过但没真的懂”的经典算法。这篇就把 Day3 这道题从头到尾拆开讲适合正在刷题的人、刚学完二叉树的同学、以及工作中要处理压缩/序列化场景的后端和嵌入式工程师。1. 哈夫曼编码在解决什么问题从等长编码的浪费说起1.1 一个最简单的压缩需求假设有一段文本里面只有 6 种字符A、B、C、D、E、F。如果用二进制给每个字符做等长编码因为 6 种字符至少需要 3 个二进制位来表示所以编码表会是这样A: 000B: 001C: 010D: 011E: 100F: 101这种编码有一个好处每个字符都一样长解码的时候每读 3 位就换一个字符不需要任何额外信息。但这个方案有一个明显的浪费如果这段文本里 F 出现了 45 次A 只出现 5 次那 F 这种高频字符也要老老实实花 3 个 bit 来存A 这种低频字符也照样要 3 个 bit。这就像每天给所有人发同一种套餐不管你饭量大不大价格都一样结果是吃不下的人白白浪费胃口大的人又没吃饱。哈夫曼的出发点恰恰相反既然字符出现的频率差别这么大为什么不能让高频字符用更短的编码、低频字符用更长的编码F 出现 45 次就给它一个短码比如 0A 只出现 5 次给它一个长一点也没关系比如 1100。整体算下来总比特数会显著下降。这里要引入一个贯穿全文的度量指标WPL带权路径长度Weighted Path Length。在一棵二叉树里每个叶子节点代表一个字符叶子节点的“权”就是字符出现的次数路径长度就是从根走到这个叶子经过的边的数量。WPL 就是所有叶子节点的“权 × 路径长度”之和。哈夫曼编码要做的事就是构造一棵二叉树让这棵树的 WPL 最小。WPL 越小意味着把所有字符编码后拼起来的二进制串越短压缩效果越好。1.2 变长编码的直觉和理想结局变长编码的直觉很容易理解把出现频率高的字符尽量往树的浅层放走几步就能到达叶子编码自然短低频字符往深层放多走几步编码长一点也没关系因为它们在整体文本里出现次数少总代价低。但这里有一个必须解决的隐患变长编码会带来解码歧义。比如给 A 编码 0给 B 编码 01那么当你看到编码串 01 的时候它到底是“AB”还是“B”这问题不解决压缩再小也没意义。哈夫曼树的妙处就在于它天然规避了这个歧义每个字符都对应树的叶子节点而从根到某个叶子的路径不可能是从根到另一个叶子的路径的前缀。这就是“前缀编码”特性。后面第 3 章会具体分析和验证这一点。所以哈夫曼编码这个题目本质上不是“写一个编码函数”而是要你理解并且实现一棵能最小化 WPL 的二叉树。理解了这一点你会瞬间看明白很多刷题题目的本质。2. 建树过程的逐步拆解5、9、12、13、16、45 的完整推演2.1 从频率表到哈夫曼树每一次合并都在做什么先给一个经典到几乎每个教材都会用的频率表字符ABCDEF频率5912131645哈夫曼算法的建树过程非常简单可以归纳成五步把所有字符看成一个个独立的节点每个节点带一个频率。从集合里选出频率最小的两个节点。把这两个节点合并成一个新节点新节点的频率是两者之和。把新节点放回集合。重复第 2 步直到集合里只剩一个节点这个节点就是树根。上面这个频率表的完整推演过程是这样的第 1 次合并取频率最小的 5(A) 和 9(B)合并出一个频率为 14 的内部节点。此时集合里剩下 12(C)、13(D)、14(AB)、16(E)、45(F)。第 2 次合并从剩下的节点里取频率最小的 12(C) 和 13(D)合并出频率为 25 的内部节点。集合里剩下 14(AB)、16(E)、25(CD)、45(F)。第 3 次合并取 14(AB) 和 16(E)合并出频率为 30 的内部节点。集合里剩下 25(CD)、30(ABE)、45(F)。第 4 次合并取 25(CD) 和 30(ABE)合并出频率为 55 的内部节点。集合里剩下 45(F)、55(ABCDE)。第 5 次合并取 45(F) 和 55(ABCDE)合并出频率为 100 的根节点。建树完成。合并到根节点之后原来 6 个字符都在叶子节点上6 个内部节点在树上整棵树一共有 11 个节点。你要注意一点叶子节点永远是原来的字符内部节点只是用来把两个分支汇合到一起它本身不代表任何字符。2.2 为什么“每次合并最小的两个”一定是全局最优这句话是哈夫曼算法最核心的贪心策略但很多刷题写到一半会突然心虚我怎么知道这样合并一定是最优的万一我这次不急着小合并先合并比较大的后面能拿到更好的 WPL 呢这里需要一个直观的解释。想一下哈夫曼树的深层叶子节点承担的责任路径最长所以放在这个位置的节点应当是整棵树上频率最小的那批节点。如果在一棵最优树里最深处躺着两个频率不是最小的节点而树里另有一个更小的节点待在浅层那把这两个节点交换位置会怎样浅层那个低频节点被换到深层深层那个高频节点被换到浅层。高频节点变浅节省的代价是大的低频节点变深增加的代价是小的。一减一增整体 WPL 变小了。这说明原来的树不可能是最优的。所以哈夫曼建树的过程等于从下往上把“最该待在深层”的节点先找到一步一步合并最后把频率最高的节点留到最靠近根的位置。这个交换论证是贪心算法正确性的标准解释刷题时不需要在代码里体现但面试时如果被追问“为什么贪心成立”你能用自己的话把它讲清楚通过率会明显不一样。还有一个容易问到的细节合并两个最小节点的时候如果出现频率相同的节点怎么办比如集合里同时有 7、7、14那么“最小两个”就存在选择歧义。这个问题我们先留着第 4 章会专门展开因为它直接关系到“哈夫曼编码唯一吗”这个热词。3. 编码表与解码路径从二叉树到 01 串再回到原文的闭环3.1 左 0 右 1从树根到每个叶子的路径就是编码树建完之后下一步是从树里提取出每个字符的二进制编码。通常约定往左子树走记成 0往右子树走记成 1。从根节点出发到某个叶子节点经过的路径就是该字符的哈夫曼编码。用上面例子里的树走一遍约定左 0 右 1编码表是这样的字符频率编码编码长度总位数F450145C12100336D13101339A51100420B91101436E16111348把所有字符的总位数加起来45 × 1 12 × 3 13 × 3 5 × 4 9 × 4 16 × 3 224 bit。还记得 6 个字符用等长编码需要多少位吗每个字符 3 bit总共 100 × 3 300 bit。用哈夫曼编码后文本缩到了 224 bit省了大约 25%。如果你把对比对象换成计算机存储最常用的 ASCII 编码那更夸张原始文本按 8 bit 一个字符存需要 800 bit压缩到 224 bit 就是省下 72%。3.2 前缀编码为什么解码过程永远不会“读串行”编码好生成但真正要验证一个压缩方案能不能用最终还得看解码。编码串是一长串 01没有分隔符怎么知道从哪里切分、到哪里结束答案就是前面提到过的前缀编码性质。由于树的结构是从根到叶子而叶子是树的终点任何一个叶子都不可能是另一个叶子的祖先那任何一个字符的编码就不可能成为另一个字符编码的前缀。比如 F 的编码是 0而 C 的编码是 100两者不冲突A 的编码是 1100B 的编码是 1101它们共享了前缀 110但没有任何一个编码吃掉了整个另一个编码。解码的规则极其简单从根节点开始每读一个 bit如果是 0 就走左子树如果是 1 就走右子树。每走到一个叶子节点就输出这个叶子对应的字符然后立刻回到根节点继续读下一个 bit。整个过程不会出现“走到一半发现没有路了”的情况也不会有“读到这里不知道是继续走还是停下来”的纠结。用上面这张编码表做个快速验证。要编码的字符串是“FADE”查表得到F0A1100D101E111拼起来就是 01100101111。现在从这根字符串解码起点在根读到 0走到 F 叶子输出 F回到根接着读 1 1 0 0沿途经过两次向右、一次向左、一次向左落在 A 叶子输出 A然后是 1 0 1落在 D 叶子最后三个 1落在 E 叶子。解出来的字符串正好是“FADE”完全无歧义。这个闭环一旦跑通哈夫曼编码的基本原理你就拿下了。4. “哈夫曼编码唯一吗”树形不同但 WPL 唯一4.1 不唯一的来源一左右子树分配方向不同很多人第一次做这道题时会发现自己写的代码和别人写的代码跑出来的编码表对不上同样的一组字符别人给出的 F 是 0我给出的 F 是 1然后互相觉得对方写错了。实际上两边都没错。只要在编码的时候约定“往左走记 0、往右走记 1”那么如果把某个内部节点的左右子树交换位置所有经过该节点的编码里的 0 和 1 就会整体互换。比如上面例子中根节点的左子树是 F右子树是其余所有字符编码表里 F0。如果把根节点左右子树交换编码表就变成 F1而 C、D、E 的编码也都会跟着互换成以 0 开头。树的结构是“对称”的码长分布完全一致WPL 也完全相同。这种不唯一是“重名编码方案”层面的不是错误。4.2 不唯一的来源二出现相同频率时合并对象的取舍不同更隐蔽的不唯一来自频率相同的节点。假设现在有 4 个字符频率分别是 1、1、2、2。按哈夫曼算法第一步需要从两个频率为 1 的节点里选出两个合并得到一个频率为 2 的新节点。这个新节点和原有的两个频率为 2 的节点是“平级”的接下来第二步到底选哪两个进行合并选原有的那个 2还是选新生成的那个 2不同的选择会生成不同形态的树。无论选哪种最终 WPL 保持不变还是最小的那个值但树的形状和每个字符的具体编码会不一样。这就导致了一个刷题时必须特别注意的现象如果题目只给了字符频率让你输出每个字符的哈夫曼编码那么题目给出的频率表里一旦存在“频率相同”的字符答案就不唯一。遇到这种题题目一般会额外规定一条规则例如“频率相同的情况下按字符字典序优先”或者“频率相同的情况下先合并先出现的节点”。没有这种规则的题目是不严谨的。4.3 唯一的东西是什么WPL 和最小代价所以回到“哈夫曼编码唯一吗”这个问题标准答案应该是哈夫曼树和每个字符的编码串不一定唯一因为左右子树互换和同频节点的不同取舍都会导致不同的树但所有合法哈夫曼树计算出来的 WPL 是同一个值也就是该频率分布下的最小带权路径长度。这个结论对你的刷题策略影响很大。如果题目问的是“最短编码长度是多少”“压缩后总位数是多少”“合并的最小总代价是多少”答案一定是唯一的放心算。如果题目问的是“写出每个字符的哈夫曼编码”你就要先检查题目有没有给出同频节点的排序规则有规则按规则做没有规则就属于特殊争议题笔试里如果碰到建议直接按题干隐含约定来解释同时可以跟面试官确认一下。5. 可复现的 Python 实现建树、编码、解码的完整代码与实测5.1 数据结构怎么选为什么优先队列是自然搭档代码实现最关键的一个选择是用什么数据结构来维护“当前最小的两个节点”。如果你把所有节点放在一个数组里每轮合并都要扫一遍找最小的两个复杂度是 O(n²)节点一多用起来很吃力。更自然的选择是堆也就是优先队列。每次从堆里弹出两个最小节点合并后把新节点压回堆里每轮操作 O(log n)整体复杂度 O(n log n)。这个复杂度对于刷题和实际生产场景基本都够用了。实现语言我用 Python标准库里的heapq就能完成这个任务。节点对象需要存储四个信息频率、字符、左孩子、右孩子。为了处理“频率相同”的情况并让结果可复现我再给每个节点分配一个自增的序号order频率相同的时候按创建先后排序。这样每次跑出来的树形和编码表都是一致的也方便做测试。5.2 核心代码建树、生成编码表、解码一次跑通import heapq from collections import Counter class Node: _counter 0 def __init__(self, freq, charNone, leftNone, rightNone): self.freq freq self.char char self.left left self.right right self.order Node._counter Node._counter 1 def __lt__(self, other): if self.freq ! other.freq: return self.freq other.freq return self.order other.order def build_huffman_tree(text): freq_map Counter(text) heap [Node(freq, char) for char, freq in freq_map.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) merged Node(left.freq right.freq, leftleft, rightright) heapq.heappush(heap, merged) return heap[0] def make_encoding_table(root, prefix, tableNone): if table is None: table {} if root.char is not None: table[root.char] prefix else: if root.left: make_encoding_table(root.left, prefix 0, table) if root.right: make_encoding_table(root.right, prefix 1, table) return table def encode(text, table): return .join(table[ch] for ch in text) def decode(encoded, root): result [] node root for bit in encoded: if bit 0: node node.left else: node node.right if node.char is not None: result.append(node.char) node root return .join(result)这段代码有几个值得注意的小设计。第一make_encoding_table里我判断叶子节点的条件是root.char is not None因为只有原始字符才会挂在叶子节点上内部节点的char保持默认的None。第二如果文本里所有字符都相同比如text AAAAA构建出来的哈夫曼树只有一个叶子节点没有任何内部节点这时候编码表会变成{A: }编码结果为空字符串。编码没问题但解码时会因为encoded为空而直接返回空字符串导致原文无法还原。实际使用时必须对这种单字符输入做特殊处理最简单的做法是单独约定当编码表长度为 1 时编码串用0表示解码时如果发现整个编码串只有0就直接还原成那个唯一字符。第三Node._counter这个类变量会在多次调用build_huffman_tree后一直累加。如果你在同一个进程里反复构建多棵哈夫曼树节点的order会持续递增这不影响比较结果但如果你希望“每次构建都从 0 开始”可以在build_huffman_tree开头重置Node._counter。刷题环境通常不会反复构建几百棵树影响不大但做单元测试的时候要留意。5.3 实测用第 2 章的频率表验证 WPL 和压缩率我用代码模拟第 2 章手算过的频率分布构造一个长度为 100 的字符串A 出现 5 次、B 出现 9 次、C 出现 12 次、D 出现 13 次、E 出现 16 次、F 出现 45 次。text A * 5 B * 9 C * 12 D * 13 E * 16 F * 45 root build_huffman_tree(text) table make_encoding_table(root) print(table) # 输出{F: 0, C: 100, D: 101, A: 1100, B: 1101, E: 111} encoded encode(text, table) print(len(encoded)) # 输出224 decoded decode(encoded, root) print(decoded text) # 输出True运行结果与我手算的编码表完全一致总位数是 224解码后能还原成原始文本。注意如果同样的频率分布但Node.__lt__里没有order这个 tie-breaker堆在遇到相同频率节点时的弹出顺序可能不稳定编码表偶尔会左右互换但码长分布不变WPL 仍然是 224不会变成别的值。这正是第 4 章“不唯一但 WPL 唯一”在实践里的直接体现。6. 刷题实战中的哈夫曼题眼四种出法、两个坑和一个延伸6.1 四种常见出题方式第一种直接给字符频率表求哈夫曼编码或 WPL。这种题考的是建树的熟练度手算时建议在纸上先写频率每次圈出最小的两个合并别跳步。第二种给一段文本求压缩后的二进制串总长度。这种题隐含了一个前置步骤先自己统计每个字符在文本里出现的频率再做哈夫曼树。思路没变只是多了一个统计环节。第三种给你一棵现成的二叉树判断它是不是一棵合法的哈夫曼树或者判断某个编码方案是不是合法的哈夫曼编码。这里核心就是两条一是编码必须满足前缀性质不能有任何一个编码是另一个编码的前缀二是这棵树加权后的 WPL 必须等于理论最小值。如果题目给的编码是等长的那显然没有利用哈夫曼的压缩优势除非每个字符频率真的都一样否则不可能是哈夫曼编码。第四种很多人一开始没意识到——经典的“合并果子”问题洛谷 P1090、各种OJ 上的石子合并本质就是哈夫曼树。给定若干堆果子的重量每次合并两堆消耗的体力等于两堆重量之和求把所有果子合并成一堆的最小体力消耗。你根本不用关心编码表只需要按哈夫曼的方式反复合并最小的两堆“合并代价的总和”就是答案。6.2 两个容易踩的坑第一个坑是在合并完两个最小节点后直接拿这个新节点跟“原序列里下一个频率”继续合并而不是把所有节点放回堆里重新比较。比如第 2 章的例子里12 和 13 合并出 25 后25 在集合里的位置不是固定的它后面还要跟 14、16 竞争。很多人手算时容易按已排序的列表顺序线性往下推结果算出来一个错误的树。正确做法是每轮都回到“找当前最小值”这一步这会让你对“为什么要用堆”这件事理解得更深。第二个坑是关于 WPL 的统计时机。常规做法是先建树再遍历所有叶子节点计算“权 × 深度”之和。但更简洁的做法是在每一步合并时把新节点的频率值累加到一个变量里当建树完成时这个累加值就是 WPL。这是因为哈夫曼树有一个很妙的等价性质所有内部节点的频率之和恰好等于所有叶子节点的带权路径长度之和。合并果子题里“每次合并代价的累加和”就是 WPL很多代码实现里直接用一个ans left.freq right.freq就搞定了不用最后再遍历一次树。6.3 一个延伸哈夫曼编码在后端和压缩协议里的位置刷完这道题有兴趣的话可以顺手看下 DEFLATE 算法它是 gzip、zlib 和大部分网络压缩传输的底层核心。DEFLATE 第一步是用 LZ77 做字典匹配第二步就是对匹配后的结果做哈夫曼编码其中动态哈夫曼编码还要把编码表也存进压缩文件里供解压端使用。JPEG 图片压缩的流程里也在用哈夫曼编码表PNG 图片数据块同样离不开它。所以你在刷题时写的那棵二叉树并不只是教科书的玩具它会被压缩器一行一行地写到全世界每天流转的数据包里。我个人在实际操作中的体会是哈夫曼这道题最好在纸上完整推演一次再用代码跑一次最后去看一眼 DEFLATE 的原理。这样一轮下来你对“高频短码、低频长码”这句话的理解就不再是背概念而是真的能解释为什么你的手机里存了那么多照片文件大小还能控制在几个 MB 以内。至于做题时的编码表不唯一记住一个原则就好参考答案永远以 WPL 最小为基准如果题目让你输出编码表先找题目里有没有同频节点排序规则有就按规则写没有就大胆说明这是多解问题。