一份英文文档里字母E出现十万次，字母Z只出现三十次，如果两种字母都占8个比特，等于给E付了巨额浪费。霍夫曼编码的思路就一句话：出现多的字符用短编码，出现少的用长编码。同样十万字符的文档，按频率分配后平均码长能压到5个比特上下，具体看频率分布。

这个方法是1952年霍夫曼在麻省理工读书时提出的课程作业，后来成了信息论里公认最优雅的算法之一。

构建步骤只有四步

  • 统计每个字符的出现频率，全部放进优先队列。
  • 每次取出频率最小的两个节点，合并成一棵子树，新节点频率取两者之和，放回队列。
  • 重复上一步，直到队列里只剩一棵树，这就是霍夫曼树。
  • 从根往下走，左分支记0，右分支记1，走到叶子的路径就是该字符的编码。

这套贪心策略能保证构造出带权路径长度最短的二叉树，也就是平均编码长度最短。直觉上理解：频率低的字符被合并得早，离根远，编码自然长，正好符合短码给高频字符的原则。整个过程不需要两两比较所有组合，复杂度只有O(n log n)。

为什么解码不会错

关键在霍夫曼编码里任意一个编码都不是另一个编码的前缀，解码时从左到右逐位读，读到能匹配的叶子就能确定字符，不存在歧义。比如A是0，B是10，C是110，D是111，读0110111就能唯一还原成ABCD。

实际用的时候还有两个细节：第一，频率分布越悬殊压缩率越高，所有字符等频率时收益很有限；第二，解码方需要拿到频率表或者树结构本身，这部分开销也要算进压缩结果里。小文件场景收益更明显，大文件一般会配合字典变换、游程编码先做一轮预处理。

它的身影到处都是：ZIP和JPEG里用的DEFLATE算法，熵编码阶段就是霍夫曼编码的变体。理解它之后再看算术编码这类进阶方案会顺很多，本质都是在跟字符频率分布打交道。