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

哈夫曼编码与游程编码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 位定长码而哈夫曼编码允许高频符号用更短的码字从而在整体上压缩数据量。哈夫曼编码的过程包含两个主要部分根据输入字符构建哈夫曼树首先要统计字符的出现频率然后依据统计频率构建哈夫曼树又称最优二叉树 / Optimal Binary Tree。频率统计是后续一切的基础。遍历哈夫曼树并将树中节点的路径分配给字符编码时类似字典树Trie节点本身不参与编码节点的路径才是最终的编码串。哈夫曼树的结构约定如图哈夫曼树是一棵二叉树节点左子节点的路径用0表示右子节点的路径用1表示节点的值表示其权重权重越大深度越小而深度实际上就是编码的长度通常使用字符出现的频率作为权重真正执行编码时类似字典树节点本身不用于编码节点到根的路径才用于编码。扩展思考如果计算机使用三进制而不是二进制那么哈夫曼树就应是一棵三叉树。这一约定说明哈夫曼编码的形态与底层进制直接相关——0/1只是二进制世界的路径标注方式。前缀码特性由于每个字符都对应哈夫曼树上的一个叶子节点任何字符的编码都不会是另一个字符编码的前缀即满足前缀码 / Prefix-Free性质。这一特性保证了一段连续的比特流可以被唯一地、无歧义地解码解码器只需从根节点出发按比特位沿0/1分支下行遇到叶子即输出一个字符然后回到根节点继续。这正是哈夫曼编码能够作为无损压缩方案的关键前提。实例从频率统计到哈夫曼树与编码表假设我们对某个字符串进行频率统计得到如下结果characterfrequencya5b9c12d13e16f45用最小堆作为优先队列逐步构建构建过程的核心是反复合并两个权值最小的节点并需要一个能够高效取出最小元素的数据结构。仓库专题给出的做法是使用最小堆Min-Heap作为优先队列。最小堆的基础知识可参见仓库 thinkings/heap.md 与 thinkings/heap-2.md 两个专题。具体步骤如下初始化将每个元素构造成一个节点即只含一个元素的树然后构建一个包含所有节点的最小堆。此时堆中有 6 个节点权值分别为 5、9、12、13、16、45。第一次合并选取两个权值最小的节点权值 5 和 9添加一个权值为5 9 14的新节点作为它们的父节点随后更新最小堆。此时堆中剩下 5 个节点4 棵仍然是原始单节点树12、13、16、45另一棵是权值 14 的合并树。重复合并继续取出堆中两个最小节点并合并直到堆中只剩一个节点根节点。完整的合并序列为合并5 9 14合并12 13 25合并14 16 30合并25 30 55合并45 55 100根节点最终构建出的哈夫曼树如下图所示内部节点的权值恒等于其两个子节点权值之和根节点权值 100 即字符总频次编码结果表沿根节点到各叶子节点的路径读出编码左0右1得到如下编码表characterfrequencyencodinga51100b91101c12100d13101e16111f450验证最高频的字符f45 次只用了 1 位编码0而低频的a、b用了 4 位编码完全符合高频短码、低频长码的设计原则。压缩收益的量化验证用编码表可以精确计算压缩效果。所有字符总频次为5912131645 100。定长编码开销6 种字符至少需要⌈log₂6⌉ 3位共需100 × 3 300位哈夫曼编码开销加权路径长度 WPL5×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 个连续的 B3C表示有 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是某个序列的游程编码对于所有偶数下标iA[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 1000A.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 专题完整梳理了两类无损压缩算法哈夫曼编码通过最小堆优先队列反复合并最小权值节点构建最优二叉树用高频短码、低频长码的可变长、前缀码完成熵编码实例压缩率约 74.7%游程编码RLE将连续重复折叠为计数 字符实现简单适合二进制连续重复密集的数据如大色块 BMP 图片但编码效果高度依赖子序列划分策略组合实践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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考