企业官网建设流程全解析

无损压缩算法完整教程：哈夫曼编码与游程编码从原理到实战

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

你有没有遇到过这种尴尬：一张手机截图动辄好几 MB，邮件附件传半天还是转圈；一个满是重复字段的日志文件，把服务器磁盘塞得满满当当。想要压缩，却担心数据丢失——这时候，无损压缩算法就是你的救星。它能在解压后 100% 还原原始数据，是 PNG、GIF、PDF、ZIP 等格式共同的基石。这篇文章专为新手设计，不堆公式、不绕弯子，带你用一个下午的时间，把无损压缩里最经典的两招——游程编码（RLE）和哈夫曼编码（Huffman）从原理到实战彻底吃透。

一个真实场景：传不出去的大文件

假设你在运营一个"每日一图"项目，每天要上传几百张 BMP 格式的截图。BMP 是未经压缩的原始位图，一张 1920×1080 的纯色界面截图就能轻松突破 5 MB。服务器快满了，用户打开图片也卡。你想压缩，但截图里的文字、数字一个都不能少——这就是典型的无损需求。

先分清两种压缩：有损压缩（如 JPEG）通过丢弃人眼不易察觉的细节换体积，适合照片；无损压缩则保证解压后与原数据分毫不差，适合文字、程序、图纸等不允许失真的内容。我们这篇文章讨论的，全部属于后者。

那么问题来了：无损压缩算法到底靠什么把数据"变瘦"？观察真实数据，你会发现冗余通常来自两个地方：

• 空间冗余：字符紧挨着连续重复，比如AAAAA；
• 频率冗余：某些字符出现极多、某些极少，比如英文文本里e远多于z。

两个问题，两把武器——对应游程编码和哈夫曼编码。我们逐个来拆。

第一件武器：游程编码——把"紧挨着的重复"折叠起来

先想一个生活场景：旅行打包行李时，你绝不会把 5 双白袜散着丢进箱子，而是叠成一摞，心里记着"这里有 5 双"。游程编码的思路完全一样——与其写下 5 个相同的字符，不如只写"次数 + 字符"。

原始数据：AAAAABBBBCCC 压缩结果：5A4B3C

5A表示连续 5 个 A，4B表示连续 4 个 B，3C表示连续 3 个 C。原来的 12 个字符被压缩到 6 个，体积直接砍半。是不是很简单？

哪些场景最适合游程压缩

游程编码的压缩效果，完全取决于"连续重复"的密度。下面这些数据是它的天然主场：

这里有个易错点：它也有"失灵"的时候

如果数据根本不连续重复，比如ABABABAB，压缩后会变成1A1B1A1B1A1B1A1B，反而膨胀了一倍。所以游程编码适合"成串重复"，不适合"交替排列"。判断标准很简单：先看数据里连续重复的部分占比高不高。

第二件武器：哈夫曼编码——给高频字符"开小灶"

如果说游程编码靠"折叠重复"省钱，那哈夫曼编码靠的是**"按需分配"**。请想象你的书架：最常读的书，你会放在伸手就够到的那一层；一年才翻一次的旧书，就塞进最高处。哈夫曼编码的原理一模一样——高频字符用最短的编码，低频字符用最长的编码，从而把整段数据的平均编码长度压到最低。它是一种可变长度编码，而 ASCII 之类的固定长度编码，无论字符多常见都一视同仁地占 8 位，浪费了大量空间。

3步构建最优编码树

哈夫曼编码的实现可以拆成清晰的三步：

1. 统计频率：数一遍每个字符在数据里出现了多少次；
2. 反复合并最小节点：把每个字符当成一棵只有一个节点的"树"，每次挑出权值最小的两棵合并成一棵新树（父节点权值=两者之和），重复直到只剩一棵树。为了高效取出最小值，通常用最小堆（优先队列）来做；
3. 遍历生成编码：从根出发，走左子树记 0、走右子树记 1，走到某个字符所在的叶节点时，这条路径就是它的二进制编码。

下面举个具体例子。假设我们统计出某段文本中字符频率如下：

按上面的步骤反复合并最小的两棵节点，就能得到一棵"最优二叉树"（哈夫曼树），最终每个字符被分配到的编码是：

看到没？出现频率最高的f只用了 1 位，而最罕见的a用了 4 位。我们来算一笔账：如果固定用 3 位编码表示这 6 个字符，100 个字符要 300 位；用哈夫曼编码，平均每个字符只需(5×4 + 9×4 + 12×3 + 13×3 + 16×3 + 45×1) ÷ 100 = 2.24位，整体节省约 25%。频率分布越悬殊，收益越明显。

为什么编码不会"串台"？前缀编码来保证

你可能好奇：f的编码是0，c的编码是100，解码时遇到连续的100，怎么确定该读成f+ 别的东西，还是c？答案是：哈夫曼树把每个字符都放在叶节点上，所以任何一个字符的编码都不可能是另一个字符编码的前缀。这种"前缀编码"保证了解码结果唯一，不会有歧义——这也是莫尔斯电码需要停顿符而哈夫曼不需要的根本原因。

两把武器如何选？一张表看懂差异

一句话总结：看到"成串重复"想游程，看到"有的字符特别多"想哈夫曼。但真实世界的数据往往两种冗余同时存在，于是就有了第三招——组合拳。

组合拳：先游程、后哈夫曼的双重压缩

实战中，成熟的无损压缩算法几乎从不单打独斗，而是采用"双重压缩"流水线：

1. 第一遍：游程编码，先把AAAAABBBBCCC变成5A4B3C，消除空间冗余；
2. 第二遍：哈夫曼编码，再对游程编码的结果按频率重新分配编码长度，消除频率冗余。

两道工序处理的是不同层面的冗余，所以效果可以叠加。几乎所有主流无损格式都在走这条路线：PNG 使用 Deflate（其内部就包含哈夫曼编码思想，并对扫描线做了类似游程的预处理）、GIF 使用 LZW、PDF 和 ZIP 也内嵌了哈夫曼变体。这也是为什么它们被称为"无损压缩的黄金组合"。

动手练：LeetCode 900 题"RLE 迭代器"

纸上得来终觉浅，我们用一道真实题目来巩固游程编码。LeetCode 第 900 题"RLE 迭代器"要求你实现一个遍历游程编码序列的迭代器：数组A中成对存放数据，偶数下标记录重复次数，相邻下标记录数值本身。比如：

A = [3, 8, 0, 9, 2, 5]

它表示的原始序列是[8, 8, 8, 5, 5]——三个 8，零个 9，两个 5。迭代器每次调用next(n)要消耗接下来的n个元素并返回最后一个被消耗的值，不够就返回-1。所以：

• next(2)→ 8
• next(1)→ 8
• next(1)→ 5
• next(2)→ -1

这道题的巧妙之处在于：不要真的把序列展开，而是维护一个指针在A上跳跃移动。这样哪怕原始序列长达百万级，内存占用也恒定，真正体现了游程编码"用元数据代替数据"的威力。完整的题目分析和参考代码都在 problems/900.rle-iterator.md 里。

总结与下一步行动

回顾一下我们今天掌握的要点：无损压缩算法靠识别数据冗余来瘦身，两大主力分别是——游程编码用"次数+字符"折叠连续重复，简单高效但怕交替数据；哈夫曼编码用短码配高频、长码配低频，通过最优二叉树实现前缀编码、无歧义解码；两者组合成"先游程、后哈夫曼"的双重压缩，正是 PNG、GIF、ZIP 等格式背后的通用配方。

学完之后，你可以立刻做这几件事来巩固：

1. 通读 thinkings/run-length-encode-and-huffman-encode.md，这里有更完整的算法分析与扩展讨论；
2. 在本地把 LeetCode 900 题独立做一遍，体验迭代器写法；
3. 动手写一个迷你版"文件压缩器"：先用游程编码处理你的日志文件，再对结果做哈夫曼编码，亲手对比压缩前后的字节数；
4. 拿一个 PNG 文件，用查看器拆开它的数据块，验证一下"先游程、后哈夫曼"的压缩链路。

做完这些，你就不仅能看懂压缩工具的工作原理，还能为实际场景挑选合适的压缩策略——甚至在面试中，把"什么是哈夫曼树""游程编码适合什么数据"这类问题答得头头是道。现在就打开编辑器，开始你的压缩算法实战吧！

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode