1951年麻省理工学院。一个叫大卫·霍夫曼的研究生正面临一个选择要么参加期末考试要么写一篇学期论文。论文的题目是导师罗伯特·法诺给的——“找到最优的二进制编码方法。”法诺自己研究这个问题多年没有找到最优解。他把这个问题抛给学生大概也没指望谁能解出来。霍夫曼在垃圾桶边上正准备把写满草稿的纸扔掉放弃论文去复习考试。就在那一刻他想到了一个绝妙的思路。从最不重要的元素开始自底向上构建编码树。他不知道的是这个在垃圾桶边上诞生的想法将成为信息论历史上最优雅的算法之一。今天它藏在你手机里的每一张JPEG图片中藏在你看的每一个MP3音乐文件中藏在你发送的每一条压缩消息中。它叫霍夫曼编码Huffman Coding。第一章为什么需要编码在理解霍夫曼编码之前我们先搞清楚一个基本问题计算机是怎么存储文字的计算机只认识0和1。 要存储字母就必须给每个字母分配一个二进制编码。 最常见的方案ASCII编码 A 010000018位 B 010000108位 C 010000118位 ... 每个字符固定占8位1个字节。 存储 ABCABC 01000001 01000010 01000011 01000001 01000010 01000011 6个字符 × 8位 48位ASCII是一种等长编码——每个字符占用相同的位数。简单。公平。但浪费。为什么浪费 想象你在发电报。每个字母都要花钱。 英语中字母E出现的频率是12.7%。 字母Z出现的频率是0.07%。 E比Z常见180倍。 但在ASCII中E和Z都占8位。 这就像 你每天都要坐地铁上班高频事件 你一年才坐一次飞机低频事件。 但有人规定 无论坐地铁还是坐飞机 你都必须提前3小时到达 都必须经过安检、托运行李、登机。 对飞机来说这些流程合理。 对地铁来说这些流程就是浪费。 高频事件应该更简单。 低频事件可以更复杂。 同理 高频字符应该用更短的编码。 低频字符可以用更长的编码。 这样总的编码长度就会更短。这就是变长编码的核心思想出现频率高的字符用短编码出现频率低的字符用长编码。第二章变长编码的陷阱变长编码听起来很美好。但它有一个致命的陷阱。假设我们给4个字母这样编码 A 0 B 1 C 01 D 10 现在收到一串编码0110 这是什么意思 解读方式一0 | 1 | 10 → A B D 解读方式二01 | 10 → C D 解读方式三0 | 1 | 1 | 0 → A B B A 解读方式四01 | 1 | 0 → C B A 四种完全不同的解读。 哪个是对的 不知道。无法确定。 因为编码之间存在歧义。 A的编码0是C的编码01的前缀。 B的编码1是D的编码10的前缀。 当你读到0时你不知道它是完整的A 还是C的开头。你必须继续往后看。 但看了下一位之后你还是不确定。 这就是前缀冲突。要让变长编码可用必须满足一个条件任何一个字符的编码都不能是另一个字符编码的前缀。这叫做前缀码Prefix Code。前缀码的例子 A 0 B 10 C 110 D 111 验证 A(0) 不是 B(10) 的前缀 ✓ A(0) 不是 C(110) 的前缀 ✓0不是110的前缀 等等0确实是10的前缀吗 不是。前缀的意思是开头部分。 0 是 0xx 的前缀。 10 以 1 开头不以 0 开头。 所以 0 不是 10 的前缀。✓ 同理 B(10) 不是 C(110) 的前缀 ✓10 ≠ 11 B(10) 不是 D(111) 的前缀 ✓ C(110) 不是 D(111) 的前缀 ✓110 ≠ 111 全部通过。这是一个合法的前缀码。 解码 01011100111 读到 0 → 匹配A输出A。 读到 1 → 不匹配任何完整编码继续。 读到 10 → 匹配B输出B。 读到 1 → 继续。 读到 11 → 继续。 读到 110 → 匹配C输出C。 读到 0 → 匹配A输出A。 读到 1 → 继续。 读到 11 → 继续。 读到 111 → 匹配D输出D。 结果A B C A D 唯一的解读。没有歧义。前缀码保证了解码的唯一性。你从左到右逐位读取每当匹配到一个完整的编码就输出对应的字符然后继续。永远不会出错。第三章编码树——前缀码的可视化前缀码有一个非常优美的可视化方式——二叉树。把前面的编码画成一棵树 A 0 B 10 C 110 D 111 (根) / \ A(0) ● / \ B(10) ● / \ C(110) D(111) 规则 ├── 从根节点出发 ├── 向左走 读到0 ├── 向右走 读到1 └── 到达叶子节点 解码出一个字符 解码 110 根 →(1)→ 右 →(1)→ 右 →(0)→ 左 → 到达叶子C 解码 0 根 →(0)→ 左 → 到达叶子A 关键观察 所有字符都在叶子节点上。 没有字符在内部节点上。 这就是前缀码的本质—— 因为字符都在叶子上 所以没有任何编码是另一个编码的前缀。 如果A在内部节点上比如根的左子节点 那么A的编码0就会是所有左子树中字符编码的前缀。 叶子节点没有子节点 所以不可能有其他编码以它为前缀。 前缀码 所有字符都在叶子上的二叉树。现在问题变成了怎么构建一棵最优的编码树最优的意思是编码后的总位数最少。高频字符应该离根近编码短低频字符可以离根远编码长。这就是霍夫曼要解决的问题。第四章霍夫曼的天才思路让我们用一个具体的例子来展示霍夫曼算法。要编码的文本ABRACADABRA 第一步统计每个字符的出现频率。 A: 5次 B: 2次 R: 2次 C: 1次 D: 1次 总共11个字符。霍夫曼的核心思路从最不重要的开始。第二步把每个字符看作一个独立的节点放入一个优先队列。 按频率从小到大排列。 优先队列频率从小到大 [D:1] [C:1] [B:2] [R:2] [A:5] 每个节点都是一棵只有一个叶子的迷你树。第三步取出频率最小的两个节点合并成一棵新树。 取出 D(1) 和 C(1)。 创建一个新的内部节点频率 1 1 2。 D和C分别作为它的左右子节点。 [DC:2] / \ D(1) C(1) 把新节点放回队列 [B:2] [R:2] [DC:2] [A:5]第四步重复。取出最小的两个合并。 取出 B(2) 和 R(2)。 [BR:4] / \ B(2) R(2) 放回队列 [DC:2] [A:5] [BR:4] 等等顺序变了。DC(2)现在是最小的。 取出 DC(2) 和 A(5)。 等等不对。应该取最小的两个。 DC(2) 和 BR(4)还是 DC(2) 和 A(5) DC(2) BR(4) A(5) 最小的两个是 DC(2) 和 BR(4)。 取出 DC(2) 和 BR(4)。 [DCBR:6] / \ [DC:2] [BR:4] / \ / \ D(1) C(1) B(2) R(2) 放回队列 [A:5] [DCBR:6]第五步继续。取出最后两个合并。 取出 A(5) 和 DCBR(6)。 [根:11] / \ A(5) [DCBR:6] / \ [DC:2] [BR:4] / \ / \ D(1) C(1) B(2) R(2) 队列为空。树构建完成。第六步从树中读取编码。 从根到每个叶子的路径就是该字符的编码。 左走 0右走 1。 [根:11] / \ A(5) [DCBR:6] ↑ / \ 0 [DC:2] [BR:4] / \ / \ D(1) C(1) B(2) R(2) A: 左 → 0 1位 D: 右→左→左 → 100 3位 C: 右→左→右 → 101 3位 B: 右→右→左 → 110 3位 R: 右→右→右 → 111 3位 编码表 ┌────────┬────────┬────────┬──────────────┐ │ 字符 │ 频率 │ 编码 │ 总位数 │ ├────────┼────────┼────────┼──────────────┤ │ A │ 5 │ 0 │ 5×1 5 │ │ B │ 2 │ 110 │ 2×3 6 │ │ R │ 2 │ 111 │ 2×3 6 │ │ C │ 1 │ 101 │ 1×3 3 │ │ D │ 1 │ 100 │ 1×3 3 │ ├────────┼────────┼────────┼──────────────┤ │ 总计 │ 11 │ │ 23位 │ └────────┴────────┴────────┴──────────────┘ 对比等长编码 5个不同字符至少需要3位2³8≥5。 11个字符 × 3位 33位。 霍夫曼编码23位。 节省了 (33-23)/33 30% 的空间。 A出现最频繁5次编码最短1位。 C和D出现最少各1次编码最长3位。 完美符合高频短码低频长码的原则。第五章为什么这是最优的霍夫曼编码不只是一种变长编码。它是最优的前缀码。没有任何其他前缀码能比霍夫曼编码产生更短的总编码长度。为什么直觉上的理解 想象你在安排一场淘汰赛。 有5个选手A(实力5), B(实力2), R(实力2), C(实力1), D(实力1) 淘汰赛的规则 每轮两个选手对决输的被淘汰。 最后剩下的是冠军。 每个选手参加的比赛场数 他在树中的深度 编码长度。 你希望总比赛场数最少。 总比赛场数 Σ 每个选手的比赛场数 × 选手的权重 最优策略是什么 让最强的选手A权重5尽早获得轮空—— 也就是让他在树中的深度最浅。 让最弱的选手C和D权重1在最底层—— 他们要打最多的比赛但因为权重小 对总场数的贡献也小。 霍夫曼算法恰好做到了这一点 1. 每次合并最小的两个 → 最弱的选手最先被淘汰 2. 最弱的选手在树的最底层 → 编码最长 3. 最强的选手在树的最顶层 → 编码最短 这是一个贪心策略。 而且可以严格证明这个贪心策略是全局最优的。 严格证明的核心思路简化版 1. 在最优编码树中频率最低的两个字符 一定在树的最深层而且是兄弟节点。 反证如果不是交换它们到最深层 总编码长度只会更短或不变。 2. 把这两个最深的兄弟合并成一个节点 得到一个更小的问题。 3. 对更小的问题递归应用同样的论证。 4. 霍夫曼算法恰好就是这个过程的实现。 所以霍夫曼编码是最优的。证毕。第六章完整的编码和解码过程编码过程原文ABRACADABRA 第一步统计频率 A:5, B:2, R:2, C:1, D:1 第二步构建霍夫曼树如前所述 第三步生成编码表 A0, B110, R111, C101, D100 第四步逐字符替换 A B R A C A D A B R A 0 110 111 0 101 0 100 0 110 111 0 第五步拼接成比特流 0 110 111 0 101 0 100 0 110 111 0 去掉空格 01101110101010001101110 总共23位。 第六步存储 需要存储两样东西 1. 编码后的比特流01101110101010001101110 2. 霍夫曼树或频率表用于解码 没有霍夫曼树接收方无法解码。 树的存储方式有很多种 ├── 直接存储频率表接收方重建树 ├── 用前序遍历序列化树结构 └── 用规范霍夫曼编码只需存储编码长度解码过程收到比特流01101110101010001101110 收到霍夫曼树如前所述的那棵树 解码过程从根节点开始逐位读取。 [根] / \ A(叶) ● / \ ● ● / \ / \ D C B R 读取比特流0 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 位置0: 读到0 → 左走 → 到达叶子A → 输出A回到根 位置1: 读到1 → 右走 位置2: 读到1 → 右走 位置3: 读到0 → 左走 → 到达叶子B → 输出B回到根 等等这和前面的编码表不一致。让我重新检查。 前面的编码表 A0, B110, R111, C101, D100 树的结构 [根] / \ A ● / \ ● ● / \ / \ D C B R 左0右1 A: 0 ✓ D: 1→0→0 100 ✓ C: 1→0→1 101 ✓ B: 1→1→0 110 ✓ R: 1→1→1 111 ✓ 重新解码01101110101010001101110 0 → A 110 → B 111 → R 0 → A 101 → C 0 → A 100 → D 0 → A 110 → B 111 → R 0 → A 结果ABRACADABRA ✓ 完美还原。一个字符都不差。第七章代码实现// 霍夫曼树的节点classHuffmanNode:IComparableHuffmanNode{publiccharCharacter;// 字符只有叶子节点有publicintFrequency;// 频率publicHuffmanNodeLeft;// 左子节点publicHuffmanNodeRight;// 右子节点publicboolIsLeafLeftnullRightnull;publicintCompareTo(HuffmanNodeother){returnFrequency.CompareTo(other.Frequency);}}// 构建霍夫曼树HuffmanNodeBuildTree(stringtext){// 第一步统计频率Dictionarychar,intfreqnewDictionarychar,int();foreach(charcintext){if(!freq.ContainsKey(c))freq[c]0;freq[c];}// 第二步创建优先队列最小堆PriorityQueueHuffmanNode,intpqnew();foreach(varpairinfreq){varnodenewHuffmanNode{Characterpair.Key,Frequencypair.Value};pq.Enqueue(node,node.Frequency);}// 第三步反复合并最小的两个节点while(pq.Count1){varleftpq.Dequeue();// 取出最小的varrightpq.Dequeue();// 取出第二小的// 合并成新节点varparentnewHuffmanNode{Frequencyleft.Frequencyright.Frequency,Leftleft,Rightright};pq.Enqueue(parent,parent.Frequency);// 放回队列}// 第四步队列中剩下的唯一节点就是根returnpq.Dequeue();}// 从树中生成编码表Dictionarychar,stringGenerateCodes(HuffmanNoderoot){varcodesnewDictionarychar,string();GenerateCodesHelper(root,,codes);returncodes;}voidGenerateCodesHelper(HuffmanNodenode,stringcode,Dictionarychar,stringcodes){if(nodenull)return;if(node.IsLeaf){codes[node.Character]code;return;}GenerateCodesHelper(node.Left,code0,codes);// 左走加0GenerateCodesHelper(node.Right,code1,codes);// 右走加1}// 编码stringEncode(stringtext,Dictionarychar,stringcodes){StringBuildersbnewStringBuilder();foreach(charcintext){sb.Append(codes[c]);}returnsb.ToString();}// 解码stringDecode(stringbits,HuffmanNoderoot){StringBuildersbnewStringBuilder();HuffmanNodecurrentroot;foreach(charbitinbits){if(bit0)currentcurrent.Left;elsecurrentcurrent.Right;if(current.IsLeaf){sb.Append(current.Character);currentroot;// 回到根开始解码下一个字符}}returnsb.ToString();}使用示例 string text ABRACADABRA; HuffmanNode tree BuildTree(text); var codes GenerateCodes(tree); // codes: A0, B110, R111, C101, D100 string encoded Encode(text, codes); // encoded: 01101110101010001101110 string decoded Decode(encoded, tree); // decoded: ABRACADABRA 原文11个字符 × 8位 88位ASCII 编码后23位 压缩率23/88 26% 节省了74%的空间第八章霍夫曼编码在真实世界中的应用霍夫曼编码不是一个教科书上的玩具。 它是真实世界中最广泛使用的压缩算法之一。 JPEG图片压缩 ├── 图片经过DCT变换和量化后 ├── 产生大量的数值数据。 ├── 这些数值的分布不均匀小值多大值少。 └── 用霍夫曼编码压缩这些数值。 MP3音频压缩 ├── 音频经过频域变换和心理声学模型处理后 ├── 产生需要编码的频率系数。 └── 用霍夫曼编码压缩这些系数。 ZIP/GZIP文件压缩 ├── 先用LZ77算法找到重复的字符串模式 ├── 然后用霍夫曼编码压缩LZ77的输出。 └── 两种算法配合效果更好。 HTTP/2协议 ├── 用HPACK算法压缩HTTP头部。 └── HPACK中使用了静态霍夫曼表来压缩字符串。 传真机Fax ├── 传真图像大部分是白色空白区域。 ├── 白色像素的连续长度出现频率远高于黑色。 └── 用霍夫曼编码压缩这些长度值。第九章霍夫曼编码的局限局限一需要两次扫描 第一次扫描统计频率。 第二次扫描用编码表进行编码。 对于流式数据边接收边处理 你不知道后面还有什么字符 无法提前统计频率。 解决方案自适应霍夫曼编码 ├── 边读取边更新频率表和编码树 ├── 编码器和解码器同步更新 └── 不需要预先知道全部数据 局限二编码长度必须是整数位 假设某个字符的理论最优编码长度是2.3位。 霍夫曼编码只能给它分配2位或3位。 不能是2.3位。 这意味着霍夫曼编码不一定能达到理论最优 信息熵给出的下限。 解决方案算术编码Arithmetic Coding ├── 可以用非整数位来编码 ├── 能更接近信息熵的理论下限 ├── 但实现更复杂 └── 在JPEG 2000、H.265等新标准中使用 局限三必须传输编码树 解码方需要知道编码树才能解码。 编码树本身也占空间。 对于很短的文本编码树的开销 可能比节省的空间还大。得不偿失。 例文本 AB2个字符 ASCII编码2 × 8 16位 霍夫曼编码A0, B1 → 编码后2位 但编码树需要额外存储至少几十位 总大小 2位数据 几十位树 16位ASCII 反而更大了。 所以霍夫曼编码适合较长的文本。 文本越长频率统计越准确 编码树的开销占比越小 压缩效果越好。 解决方案规范霍夫曼编码Canonical Huffman Code ├── 对编码施加额外的排列规则 ├── 只需要存储每个字符的编码长度而非完整的树 ├── 接收方可以从编码长度重建编码表 └── 大幅减少编码树的存储开销 └── DEFLATEZIP/GZIP使用的算法就用了这个技巧 局限四逐字符编码的天花板 霍夫曼编码是对单个字符进行编码的。 它没有利用字符之间的关联性。 例英语中字母Q后面几乎总是跟着U。 如果把QU当作一个整体来编码 效率会更高。 解决方案 ├── 高阶霍夫曼编码对字符组合二元组、三元组编码 ├── LZ系列算法先找重复模式再用霍夫曼压缩 └── 现代压缩算法通常是多种技术的组合第十章一个直觉——信息熵霍夫曼编码的压缩效果有一个理论上限。这个上限由信息熵决定。信息熵是克劳德·香农在1948年提出的概念。 它衡量的是一条消息中 平均每个字符携带多少信息量。 公式H -Σ p(x) × log₂(p(x)) 其中 p(x) 是字符x出现的概率。 用 ABRACADABRA 来算 p(A) 5/11 ≈ 0.4545 p(B) 2/11 ≈ 0.1818 p(R) 2/11 ≈ 0.1818 p(C) 1/11 ≈ 0.0909 p(D) 1/11 ≈ 0.0909 H -(0.4545×log₂(0.4545) 0.1818×log₂(0.1818) 0.1818×log₂(0.1818) 0.0909×log₂(0.0909) 0.0909×log₂(0.0909)) -(0.4545×(-1.138) 0.1818×(-2.459) 0.1818×(-2.459) 0.0909×(-3.459) 0.0909×(-3.459)) -((-0.517) (-0.447) (-0.447) (-0.314) (-0.314)) -(-2.040) 2.040 位/字符 理论下限每个字符平均需要 2.040 位。 11个字符 × 2.040 22.44位。 霍夫曼编码的结果23位。 非常接近理论下限了只多了0.56位。 直觉理解信息熵 如果所有字符出现频率相同完全随机 信息熵最大压缩空间最小。 如果某些字符出现频率远高于其他字符分布不均匀 信息熵较小压缩空间很大。 极端情况如果文本全是AAAAAAAAA p(A) 1H -1×log₂(1) 0。 信息熵为0。意味着这条消息不携带任何惊喜。 你完全可以用0位来编码—— 因为接收方已经知道每个字符都是A了。 霍夫曼编码的压缩效果 ├── 最好情况当所有频率恰好是2的幂次时 │ 霍夫曼编码恰好达到信息熵下限。完美。 │ ├── 一般情况比信息熵多不超过1位/字符。 │ 已经非常好了。 │ └── 算术编码可以更接近信息熵 但实现复杂度更高。尾声垃圾桶边上的灵感让我们回到1951年的那个时刻。大卫·霍夫曼站在垃圾桶边上手里攥着写满草稿的纸。他的导师法诺用的是自顶向下的方法——先把所有字符分成两组让两组的频率之和尽量相等然后对每组递归地继续分。这个方法直觉上很合理但无法保证最优。法诺的方法自顶向下 A:5, B:2, R:2, C:1, D:1 第一刀把它们分成两组频率之和尽量相等 {A:5, D:1} 6 vs {B:2, R:2, C:1} 5 差距为1还算均匀。 左组编码以0开头右组编码以1开头。 然后对每组继续分…… 问题第一刀怎么切会影响后面所有的结果。 而且没有办法保证第一刀是最优的。 这是一个全局优化问题贪心地切第一刀不一定对。霍夫曼的灵感是反过来——不从顶部开始分而是从底部开始合。霍夫曼的方法自底向上 不是把大问题分成小问题 而是把小问题合成大问题。 每次合并频率最小的两个。 为什么这样是对的 因为频率最小的两个字符 无论在哪棵最优树中 它们一定在最深层而且是兄弟。 如果不是交换它们到最深层总编码长度只会更短。 所以先把它们合并是安全的。 合并之后问题规模减小了一个。 对更小的问题重复同样的操作。 每一步都是安全的。 每一步都不会错过最优解。 所有步骤加起来就是全局最优。 这就是贪心算法的精髓—— 局部最优 → 全局最优。 但只有在能证明局部最优不会破坏全局最优时 贪心才是正确的。 霍夫曼证明了这一点。法诺从上往下切找不到最优解。霍夫曼从下往上合找到了。有时候解决问题的关键不是更努力地往前冲而是转过身来从另一个方向出发。霍夫曼把那些写满草稿的纸从垃圾桶边上捡了回来。他没有去参加期末考试。他写了那篇论文。那篇论文发表于1952年题为《一种构造最小冗余编码的方法》A Method for the Construction of Minimum-Redundancy Codes。七十多年后的今天——你打开手机拍了一张照片。JPEG压缩启动霍夫曼编码在后台默默工作把几十兆的原始数据压缩成几兆。你打开音乐App播放一首歌。MP3解码器读取文件霍夫曼解码在毫秒间完成音乐流淌出来。你打开浏览器访问一个网页。HTTP/2协议用HPACK压缩请求头霍夫曼编码把冗余的文本头部压缩成紧凑的比特流。你不知道这一切正在发生。就像你不知道这一切始于一个研究生在垃圾桶边上的犹豫。他差一点就放弃了。幸好他没有。