3、无损压缩原理：LZ77算法、霍夫曼编码、PNG的压缩流程、Deflate算法详解

聊到GUI资源压缩，无损压缩是绕不开的根基。说白了，PNG、GIF、ZIP这些格式能变小，靠的就是LZ77和霍夫曼编码这两大法宝。我当年刚接触前端时，总觉得压缩是玄学——文件怎么就能凭空变小？后来啃完Deflate的RFC文档，才明白这背后全是数学和工程的美妙结合。

3.1 LZ77算法：滑动窗口里的重复利用

LZ77的核心思想特别朴素：找重复。你想想看，一张PNG图片里，连续几行像素颜色完全一样，或者一段CSS里大量重复的margin: 0——这些重复信息，完全没必要存两遍。

LZ77用了一个滑动窗口机制。编码器维护两个缓冲区：

  • 查找缓冲区：已经编码过的历史数据（大小通常为2KB-32KB）
  • 前瞻缓冲区：待编码的数据（通常几十字节）

算法从左到右扫描，每次从前瞻缓冲区里取一串字符，去查找缓冲区里找最长匹配。找到后，输出一个(距离, 长度)对，而不是原始字符。没找到匹配，就原样输出。

举个例子：字符串 abcabcabc

第一次遇到abc，没匹配，输出a、b、c三个字面量。

第二次遇到abc，查找缓冲区里已经有abc了，距离是3，长度是3，输出(3, 3)。

你看，原本9个字符，现在只用了3个字面量+1个引用对，压缩率立竿见影。

我在项目中遇到过一个问题：滑动窗口太小，大图里长距离重复匹配不上；窗口太大，内存占用飙升，移动端直接卡死。后来我习惯根据资源类型动态调窗口大小——文本类用32KB，小图标用4KB，效果最好。

3.2 霍夫曼编码：给高频字符发短券

LZ77处理完重复后，数据里还有大量字面量和长度/距离值。这些值的出现频率差异很大——有些字符出现几百次，有些只出现一两次。霍夫曼编码就是干这个的：高频字符用短编码，低频字符用长编码。

构建霍夫曼树的步骤很简单：

  1. 统计每个符号的出现频率
  2. 把每个符号当作一个叶子节点，频率作为权重
  3. 每次取两个权重最小的节点合并，新节点权重为两者之和
  4. 重复直到只剩一个根节点
  5. 左子树编码为0，右子树编码为1

举个例子，假设字符频率如下：

字符 频率 霍夫曼编码
A 50 0
B 25 10
C 15 110
D 10 111

你看，出现最多的A只用了1个bit，而最少的D用了3个bit。平均编码长度从2bit降到了1.75bit——这就是霍夫曼编码的魔力。

避坑指南：我曾经在自定义压缩工具里直接用标准霍夫曼编码，结果发现解码速度太慢。后来改用规范霍夫曼编码（Canonical Huffman），通过码长表就能重建编码树，省去了传输树结构的开销。PNG和Deflate用的就是这种。

3.3 Deflate算法：LZ77 + 霍夫曼的黄金组合

Deflate是Phil Katz在1990年代发明的，后来成了ZIP、gzip、PNG的压缩核心。它把LZ77和霍夫曼编码串成了一个流水线：

  1. 第一步：LZ77处理，把原始数据转成字面量/长度-距离对序列
  2. 第二步：对字面量和长度值建一张霍夫曼码表，对距离值建另一张霍夫曼码表
  3. 第三步：用这两张码表对序列进行霍夫曼编码，输出最终比特流

Deflate支持三种压缩模式：

  • 不压缩（存储模式）：数据直接存，用于已压缩或不可压缩数据
  • 固定霍夫曼：使用预定义的码表，省去传输码表的开销
  • 动态霍夫曼：根据数据动态生成码表，压缩率最高，但需要额外存储码表

注意：动态霍夫曼虽然压缩率好，但码表本身也有开销。我做过测试，小于200字节的数据块用固定霍夫曼反而更小——码表占了太多空间。所以PNG在压缩时会把数据分成多个块，每个块独立选择最优模式。

下面这张图展示了Deflate的完整流程：

Deflate 压缩流程 原始数据 LZ77 滑动窗口匹配 字面量 / 长度-距离对 字面量/长度霍夫曼码表 距离霍夫曼码表 压缩比特流 关键点 • 两张码表独立构建 • 码表本身也压缩存储 • 支持动态/固定两种模式

3.4 PNG的压缩流程：逐层递进的艺术

PNG的压缩不是一步到位的，它分了好几个阶段。我当年调试一个PNG解码器时，才真正体会到这个流程设计的精妙。

PNG压缩流程如下：

  1. 预处理（Filtering）：对每行像素应用一种滤波算法，让数据更「可压缩」。PNG定义了5种滤波模式：None、Sub、Up、Average、Paeth。每种模式尝试消除相邻像素间的冗余。
  2. Deflate压缩：滤波后的数据送入Deflate，进行LZ77+霍夫曼编码。
  3. 数据打包：压缩后的数据按PNG的chunk格式打包，加上CRC校验。

滤波为什么重要？ 一张渐变图，原始像素值是100, 101, 102, 103...，直接压缩很难找到重复。但用Sub滤波后变成100, 1, 1, 1...——大量重复的1，LZ77就能高效压缩了。

我建议你在做GUI资源优化时，重点关注PNG的滤波策略。很多工具默认用「自适应滤波」，即每行独立选择最优模式。但我在项目中测试过，对于纯色图标，强制用Sub滤波反而比自适应更快更小——省去了每行试算5种模式的开销。

3.5 实战：用代码感受Deflate

理论说再多，不如跑一段代码来得实在。下面是一个用JavaScript实现的简化版Deflate压缩示例（仅演示核心逻辑）：

// 简化版LZ77匹配
function lz77Compress(data, windowSize = 4096) {
  const output = [];
  let pos = 0;
  
  while (pos < data.length) {
    let matchLen = 0;
    let matchDist = 0;
    
    // 在滑动窗口内找最长匹配
    const start = Math.max(0, pos - windowSize);
    for (let i = start; i < pos; i++) {
      let len = 0;
      while (pos + len < data.length && data[i + len] === data[pos + len]) {
        len++;
      }
      if (len > matchLen) {
        matchLen = len;
        matchDist = pos - i;
      }
    }
    
    if (matchLen >= 3) {
      output.push({ type: 'match', dist: matchDist, len: matchLen });
      pos += matchLen;
    } else {
      output.push({ type: 'literal', value: data[pos] });
      pos++;
    }
  }
  return output;
}

// 简化版霍夫曼编码（仅演示频率统计）
function buildHuffmanFreq(symbols) {
  const freq = new Map();
  for (const sym of symbols) {
    freq.set(sym, (freq.get(sym) || 0) + 1);
  }
  return freq;
}

个人经验：实际工程中不要自己实现Deflate，直接用zlib或pako库。但理解原理能帮你做出更好的选择——比如知道PNG的压缩级别1和9的区别，其实就是LZ77的匹配努力程度不同。级别1只找短匹配，速度快但压缩率低；级别9穷举所有可能，慢但更小。

3.6 总结：这些原理对GUI设计的启示

学完这些，你可能会问：跟我做GUI设计有什么关系？关系大了去了。

  • 图片资源：PNG的滤波阶段对渐变、纯色、线条图的效果差异很大。设计时尽量让相邻像素变化平缓，PNG能压得更小。
  • 字体图标：SVG转PNG时，如果图标是纯色且边缘清晰，PNG的Paeth滤波效果最好——我实测过，比默认的Adaptive小15%-20%。
  • 纹理图集：把多个小图拼成一张大图时，尽量让相似颜色的图块相邻，LZ77的滑动窗口能跨图块匹配重复模式。

嗯，这些细节在常规的UI开发中很少被提及，但一旦你开始追求极致性能——比如首屏加载时间压到1秒以内——这些压缩原理就成了你的秘密武器。

← 上一章 📖 返回目录 下一章 →