企业官网建设流程全解析

哈夫曼编码与游程编码（RLE）：从无损压缩原理到 LeetCode 实战

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

本文以 leetcode 仓库 thinkings/run-length-encode-and-huffman-encode.en.md 中的算法专题为骨架，系统讲解两类经典无损压缩算法：哈夫曼编码（Huffman Coding）与游程编码（Run-Length Encoding）。读完本文，你将掌握哈夫曼树的最小堆构建流程、前缀码的编解码约定、RLE 的适用场景与权衡，并能独立完成配套实战题 LeetCode 900. RLE 迭代器 的求解。本文属于仓库《第一章 - 算法专题》内容，目录入口见 SUMMARY.md 与 thinkings/README.md。

哈夫曼编码：可变长编码压缩的核心思想

哈夫曼编码的基本思想是：用短的编码表示出现频率高的字符，用长的编码表示出现频率低的字符。这样一来，编码后整个字符串的平均长度与长度期望值都会下降，从而实现压缩的目的。因此哈夫曼编码被广泛地应用于无损压缩领域。

需要特别强调的是，哈夫曼编码是一种可变长编码（Variable-Length Code），而不是固定长度编码（Fixed-Length Code）。固定长度编码给每个符号分配相同位数的码字（例如 8 位 ASCII 或 3 位定长码），而哈夫曼编码允许高频符号用更短的码字，从而在整体上压缩数据量。

哈夫曼编码的过程包含两个主要部分：

1. 根据输入字符构建哈夫曼树：首先要统计字符的出现频率，然后依据统计频率构建哈夫曼树（又称最优二叉树 / Optimal Binary Tree）。频率统计是后续一切的基础。
2. 遍历哈夫曼树，并将树中节点的路径分配给字符：编码时类似字典树（Trie），节点本身不参与编码，节点的路径才是最终的编码串。

哈夫曼树的结构约定

如图，哈夫曼树是一棵二叉树：

• 节点左子节点的路径用0表示，右子节点的路径用1表示；
• 节点的值表示其权重，权重越大深度越小，而深度实际上就是编码的长度；
• 通常使用字符出现的频率作为权重；
• 真正执行编码时，类似字典树，节点本身不用于编码，节点到根的路径才用于编码。

扩展思考：如果计算机使用三进制而不是二进制，那么哈夫曼树就应是一棵三叉树。这一约定说明哈夫曼编码的形态与底层进制直接相关——0/1只是二进制世界的路径标注方式。

前缀码特性

由于每个字符都对应哈夫曼树上的一个叶子节点，任何字符的编码都不会是另一个字符编码的前缀（即满足前缀码 / Prefix-Free性质）。这一特性保证了一段连续的比特流可以被唯一地、无歧义地解码，解码器只需从根节点出发，按比特位沿0/1分支下行，遇到叶子即输出一个字符，然后回到根节点继续。这正是哈夫曼编码能够作为无损压缩方案的关键前提。

实例：从频率统计到哈夫曼树与编码表

假设我们对某个字符串进行频率统计，得到如下结果：

用最小堆作为优先队列逐步构建

构建过程的核心是反复合并两个权值最小的节点，并需要一个能够高效取出最小元素的数据结构。仓库专题给出的做法是：使用最小堆（Min-Heap）作为优先队列。最小堆的基础知识可参见仓库 thinkings/heap.md 与 thinkings/heap-2.md 两个专题。

具体步骤如下：

1. 初始化：将每个元素构造成一个节点，即只含一个元素的树；然后构建一个包含所有节点的最小堆。此时堆中有 6 个节点，权值分别为 5、9、12、13、16、45。
2. 第一次合并：选取两个权值最小的节点（权值 5 和 9），添加一个权值为5 + 9 = 14的新节点作为它们的父节点；随后更新最小堆。此时堆中剩下 5 个节点：4 棵仍然是原始单节点树（12、13、16、45），另一棵是权值 14 的合并树。
3. 重复合并：继续取出堆中两个最小节点并合并，直到堆中只剩一个节点（根节点）。完整的合并序列为：
   • 合并5 + 9 = 14
   • 合并12 + 13 = 25
   • 合并14 + 16 = 30
   • 合并25 + 30 = 55
   • 合并45 + 55 = 100（根节点）

最终构建出的哈夫曼树如下图所示（内部节点的权值恒等于其两个子节点权值之和，根节点权值 100 即字符总频次）：

编码结果表

沿根节点到各叶子节点的路径读出编码（左0右1），得到如下编码表：

验证：最高频的字符f（45 次）只用了 1 位编码0，而低频的a、b用了 4 位编码，完全符合"高频短码、低频长码"的设计原则。

压缩收益的量化验证

用编码表可以精确计算压缩效果。所有字符总频次为5+9+12+13+16+45 = 100。

• 定长编码开销：6 种字符至少需要⌈log₂6⌉ = 3位，共需100 × 3 = 300位；
• 哈夫曼编码开销（加权路径长度 WPL）：5×4 + 9×4 + 12×3 + 13×3 + 16×3 + 45×1 = 224位；
• 压缩率：224 / 300 ≈ 74.7%，即节省约 25.3% 的存储空间。

从公式可以看出，哈夫曼编码的压缩率本质上取决于字符频率分布的均匀程度：频率越悬殊，短码集中给高频字符带来的收益越大；频率接近均匀时，压缩空间则相对有限。

游程编码（RLE）：将连续重复折叠为计数

游程编码（Run-Length Encoding）是一种相对简单的压缩算法，其基本思想是：将重复且连续出现多次的字符，用（连续出现次数，某个字符）这一二元组来描述。

例如字符串：

AAAAABBBBCCC

使用游程编码可以将其描述为：

5A4B3C

其中5A表示这个地方有 5 个连续的 A，同理4B表示有 4 个连续的 B，3C表示有 3 个连续的 C，其它情况以此类推。

子序列划分的复杂性

但实际情况可能非常复杂：我们既可以对单个字符进行编码，也可以对多个字符进行编码。因此如何提取子序列本身就是个问题，并没有看上去那么简单。

还是以上面的例子来说，我们也可以把AAAAABBBBCCC整体看成一个子序列，这样编码的长度就有所改变（例如编码为1AAAAABBBBCCC）。究竟使用哪种划分方法，取决于压缩的时间和压缩的比例等因素的权衡。更复杂的情况还有很多，仓库原文在此不做扩展——理解"RLE 的编码结果依赖于子序列划分策略"这一点，是正确使用该算法的关键。

适用场景

RLE 对文件内存在大量连续重复的二进制数据的场景压缩效果最好。一个经典的例子就是具有大面积色块的 BMP 图像：BMP 因为没有压缩，看到的是什么样子，存储时二进制就是什么样子，因此大块纯色区域会呈现为大量连续相同的字节，非常适合 RLE 处理。

这也是为什么图片越是纯色，压缩效果越好的原因——连续的相同字节越多，RLE 折叠成"计数 + 字符"后节省的空间就越大。

思考题：如果我们在 CDN 上存储两张几乎完全一样的图片，是否可以进行优化？这虽然是 CDN 厂商更应该关心的问题，但对我们的系统设计、带宽成本与用户体验影响依然很大，值得深入思考（例如基于 RLE/哈夫曼思想的增量存储、去重与差量传输方案）。

实战：LeetCode 900. RLE 迭代器

RLE 不仅在文件格式中广泛应用，也是算法面试的常客。仓库 problems/900.rle-iterator.md 将游程编码包装成了一个经典的迭代器设计题，完整题解如下。

题目描述

编写一个遍历游程编码序列的迭代器。迭代器由RLEIterator(int[] A)初始化，其中A是某个序列的游程编码：对于所有偶数下标i，A[i]告诉我们在序列中重复非负整数值A[i + 1]的次数。

例如以A = [3,8,0,9,2,5]开始，它对应序列[8,8,8,5,5]（可以读作"三个八，零个九，两个五"）。

调用next(int n)会耗尽接下来的n个元素（n >= 1），并返回以这种方式耗去的最后一个元素；如果没有剩余元素可供耗尽，则返回-1。

示例：输入["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]，输出[null,8,8,5,-1]。

数据规模约束：0 <= A.length <= 1000，A.length为偶数，0 <= A[i] <= 10^9，每个测试用例最多调用 1000 次next，且每次调用满足1 <= n <= 10^9。

思路与关键点

这是一个游程编码的典型题目，算法分为初始化和调用next(n)两个部分。

初始化的任务很简单：记住A本身即可。每次调用next(n)时，只需要判断n与当前游程剩余计数A[i]（i从 0 开始）的大小关系：

• 如果n > A[i]，说明当前游程不够耗尽，需要移除数组前两项（把剩余需求n减去该游程计数，下标i后移两位），然后重复判断；
• 如果n <= A[i]，说明当前游程足够，直接更新A[i]并返回该游程对应的元素A[i + 1]。

值得强调的是关键点：伪更新。一种朴素做法是每次next(n)都真的修改数组A（如移除已耗尽的前两项），但这样会破坏原始编码数据。更优的做法是不更新A，而是用一个变量记录当前访问到的数组位置（下标游标）。仓库题解明确指出"很多时候我们需要原始的，那么就必须这种用法"——保留原始数组对后续调用与数据复用非常重要。

参考代码（JavaScript）

/** * @param {number[]} A */ var RLEIterator = function(A) { this.A = A; this.current = 0; }; /** * @param {number} n * @return {number} */ RLEIterator.prototype.next = function(n) { const A = this.A; while(this.current < A.length && A[this.current] < n){ n = n - A[this.current]; this.current += 2; } if(this.current >= A.length){ return -1; } A[this.current] = A[this.current] - n; // 更新 Count return A[this.current + 1]; // 返回 element };

复杂度分析

• 时间复杂度：next(n)最坏情况下需要跳过多个游程，单次调用为O(k)（k为本次耗尽的游程段数量），但由于游标current只前进不回溯，所有next调用累计只需遍历数组一次，均摊复杂度为O(1)；
• 空间复杂度：只使用游标等常量辅助空间，为O(1)（不复制原始数组）。

该题在仓库中的目录定位见 README.md 与 collections/medium.md，属于中等难度高频考题，其前置知识正是本文讲解的"哈夫曼编码和游程编码"。

组合使用与实际应用：从无损到有损

RLE + 哈夫曼的级联组合

游程编码和哈夫曼编码都是无损压缩算法，即解压缩过程不会损失原数据的任何内容。实际工程中，通常的做法是先用游程编码压缩一遍，再用哈夫曼编码再次压缩一次：RLE 先把连续重复折叠成"计数 + 字符"，使符号频率分布更集中，随后哈夫曼编码再对这些符号做一次熵编码，进一步压低平均码长。

几乎所有的无损压缩格式都用到了这两种算法，例如PNG、GIF、PDF、ZIP等。其中：

• PNG：使用 Deflate 算法（LZ77 + 哈夫曼编码）做压缩，而 Deflate 与 LZ77 家族正是以"将重复内容引用化"为出发点，与 RLE 的"连续重复折叠"思想一脉相承；
• ZIP：同样基于 Deflate 的哈夫曼编码部分（含距离-长度编码）；
• GIF：在 LZW 编码之前同样会做 RLE 预处理。

有损压缩与"感知编码"

与无损相对的是有损压缩，它通常是去除了人类无法识别的颜色、超出听力频率范围的信息等。也就是说，损失了部分原始数据，但由于人类无法感知这部分信息，在很多场景下这种取舍是值得的。

这种删除了人类无法感知内容的编码，仓库原文称之为**"感知编码"（Perceptual Encoding，也许是一个自创的新名词）**，典型代表是JPEG、MP3等。有损压缩不是本文的讨论范围，感兴趣的读者可以自行检索相关资料深入了解。

视频压缩的"时间冗余"

实际上，视频压缩的原理与上述思路类似，只不过视频压缩还会用到一些额外的算法，例如**"时间冗余"（Temporal Redundancy）**：对于连续帧画面，仅存储变化的部分，而对于不变的部分，存储一次就足够了。这一思想与 RLE"连续重复只需记录一次"的折叠思路在本质上一脉相承——都是利用数据中的重复性来消除冗余。

小结

本文围绕仓库 thinkings/run-length-encode-and-huffman-encode.en.md 专题，完整梳理了两类无损压缩算法：

1. 哈夫曼编码：通过最小堆优先队列反复合并最小权值节点构建最优二叉树，用"高频短码、低频长码"的可变长、前缀码完成熵编码，实例压缩率约 74.7%；
2. 游程编码（RLE）：将连续重复折叠为"计数 + 字符"，实现简单，适合二进制连续重复密集的数据（如大色块 BMP 图片），但编码效果高度依赖子序列划分策略；
3. 组合实践：RLE 与哈夫曼常级联使用，构成 PNG、GIF、PDF、ZIP 等主流无损压缩格式的基石；有损压缩则通过"感知编码"丢弃人眼/人耳不可感知的信息（JPEG、MP3），视频压缩还额外利用"时间冗余"只存变化部分。

在仓库中，本专题归属于 thinkings/README.md 算法专题体系，并与 thinkings/string-problems.md（字符串算法总览）相互呼应。

相关题目与延伸阅读

• 实战题：LeetCode 900. RLE 迭代器——游程编码的典型迭代器设计题；
• 堆专题（最小堆优先队列实现基础）：thinkings/heap.md、thinkings/heap-2.md；
• 树专题（含哈夫曼树相关说明）：thinkings/tree.md；
• 字符串算法总览（提及游程编码与哈夫曼树）：thinkings/string-problems.md。

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