4、XZ算法原理：LZMA2、区间编码、字典大小、高压缩率代价

XZ 是当前 Linux 发行版与嵌入式系统中广泛使用的压缩格式，其核心压缩器为 LZMA2（Lempel-Ziv-Markov chain Algorithm 2）。与 LZ4 追求极速不同，XZ 的设计目标是在可接受的解压速度下，尽可能逼近压缩率上限。理解 XZ 的算法原理，是判断“何时该用 XZ、何时该避开 XZ”的前提。本章将拆解 LZMA2 的匹配引擎、区间编码器、字典配置对内存与压缩率的影响，并量化高压缩率背后的时间与资源代价。

上图展示了 XZ 压缩与解压的核心数据流。压缩时，LZMA2 匹配引擎在字典中查找重复字符串，输出“长度+距离”对或字面量；随后区间编码器基于上下文概率模型将这些符号压缩为比特流。解压时，区间解码器先还原符号序列，再由 LZMA2 按字典窗口复制数据。整个过程环环相扣，任何一环的参数配置都会直接影响最终压缩率与资源消耗。

4.1 LZMA2 匹配引擎：从 LZ77 到马尔可夫链

LZMA2 并非全新的算法，而是对经典 LZ77 的深度优化。LZ77 的核心思想是：用“距离+长度”对替代重复出现的字符串。例如，文本中第二次出现“compression”时，只需记录“向前 120 字节，长度 11”。LZMA2 在此基础上引入了两个关键改进：哈希链匹配与马尔可夫链状态建模。

哈希链匹配器维护一个哈希表，将每 3~4 字节的序列映射到最近出现的位置链表。查找时，沿着链表向前搜索，直到找到最长匹配或达到搜索深度限制。搜索深度（通常为 32~128）直接决定了压缩率与压缩时间的平衡：深度越大，找到更长匹配的概率越高，但 CPU 消耗也线性增长。

马尔可夫链状态则体现在“字面量”与“匹配”的交替模式中。LZMA2 维护了 12 种状态（从状态 0 到状态 11），每种状态对应不同的概率模型。例如，连续出现多个匹配后，算法会倾向于预测下一个符号仍是匹配；而连续出现字面量时，则倾向于预测字面量。这种状态感知机制让区间编码器能更精准地分配比特，从而提升压缩率。

4.2 区间编码器：比 Huffman 更精细的熵编码

区间编码器是算术编码的一种变体，它将整个消息映射为 [0,1) 区间内的一个实数。与 Huffman 编码必须为每个符号分配整数比特不同，区间编码可以为符号分配“小数比特”。例如，一个出现概率为 90% 的符号，理论上只需约 0.15 比特，而 Huffman 至少需要 1 比特。这种差异在大量低频符号的场景下尤为明显。

XZ 使用的区间编码器基于 32 位或 64 位无符号整数运算，通过不断缩小区间来编码每个符号。编码器维护两个关键变量：low（区间下界）和 range（区间宽度）。每编码一个符号，区间按概率比例缩小；当 range 低于阈值时，输出高位字节并重新归一化。解码器则反向操作，根据当前区间位置反推符号。

LZMA2 的区间编码器还引入了自适应概率更新机制。每个上下文（由状态、匹配长度位、距离位等组合而成）都维护一个 11 位的概率值。每处理一个符号，概率值会向实际出现的方向微调（例如，概率 += (2048 - 概率) >> 5）。这种自适应特性让编码器能快速适应数据分布的变化，无需预先统计整个文件。

4.3 字典大小：压缩率与内存的博弈

字典大小是 XZ 压缩中最直观的调优参数。它决定了匹配查找窗口的最大距离。在 xz 命令行中，通过 --dict-size 或预设级别（-6 默认 8MB，-9 默认 64MB）控制。字典越大，能匹配到的重复串距离越远，压缩率越高，但代价也极其明显：

• 压缩内存：LZMA2 编码器需要为字典分配内存，且哈希链表的大小与字典大小成正比。64MB 字典大约需要 64MB（字典）+ 64MB（哈希表）+ 若干开销，总计约 140MB 内存。
• 解压内存：解压器同样需要分配与字典等大的窗口缓冲区。在嵌入式设备上，64MB 字典可能直接导致内存不足。
• 压缩速度：字典越大，哈希链的平均搜索长度越长，CPU 缓存命中率下降，压缩速度显著降低。

选择字典大小的实用原则：字典应略大于数据中最长重复块的平均距离。例如，对于 4KB 大小的日志文件，使用 64KB 字典与 64MB 字典的压缩率几乎相同，但内存占用相差 1000 倍。对于固件镜像（通常 1~16MB），8MB 字典是性价比最高的选择。

4.4 高压缩率的代价：时间、内存与 CPU 的量化分析

XZ 的高压缩率并非免费午餐。以 100MB 的文本日志为例，在主流 x86 服务器上（Intel Xeon 3.0GHz），不同预设的实测数据如下：

从数据可以看出：从 -6 到 -9，压缩时间增加了近 4 倍，但压缩率仅提升 0.2x（约 5%）。而解压时间几乎不变，因为解压速度主要受限于区间解码器的逐位运算，与字典大小关系不大。这揭示了一个重要规律：XZ 的压缩时间对字典大小极其敏感，但解压时间相对稳定。

另一个常被忽略的代价是 CPU 缓存效率。当字典超过 CPU 的 L2/L3 缓存大小时（通常 8~32MB），哈希链查找会频繁访问主内存，导致缓存未命中率飙升。这也是为什么 -9 的压缩时间不是 -6 的 8 倍（字典 8 倍），而是接近 4 倍——因为内存带宽成为瓶颈。

4.5 实战案例：固件发布包压缩策略选择

某 IoT 设备厂商需要发布 32MB 的固件升级包，目标设备为 128MB RAM 的 ARM Cortex-A7 网关。初始方案直接使用 xz -9 压缩，结果在设备端解压时频繁出现内存不足（OOM）导致升级失败。

分析过程：

1. 检查设备可用内存：系统运行占用约 60MB，剩余约 68MB。
2. -9 预设的字典为 64MB，解压器需要分配 64MB 窗口 + 约 2MB 内部状态，总计约 66MB，恰好超过剩余内存。
3. 进一步分析固件内容：固件包含 20MB 的根文件系统（大量重复的小文件）和 12MB 的内核镜像（压缩率较低）。

优化方案：

• 将字典大小调整为 16MB（xz --dict-size=16MiB），解压内存降至约 18MB，远低于 68MB 限制。
• 对根文件系统使用 -6 预设（8MB 字典），对内核镜像使用 -1 预设（256KB 字典），因为内核镜像本身已是压缩数据，再压缩收益极低。
• 启用 --block-size=8MiB 分块压缩，允许解压器按块释放内存，进一步降低峰值内存。

结果对比：

优化后，固件包增大了 0.9MB（约 11%），但换来了设备端的稳定运行。这个案例说明：在资源受限环境中，压缩率并非唯一指标，内存约束往往比存储空间更关键。

4.6 常见误区与调优复盘

误区一：盲目追求最高压缩率。很多开发者习惯使用 -9 或 --extreme，却忽略了目标环境的限制。实际上，从 -6 到 -9 的压缩率提升通常不超过 5%，但压缩时间和内存可能翻倍。在 CI/CD 流水线中，这可能导致每次构建多花几分钟。

误区二：忽略数据特性。XZ 对文本、JSON、日志等高度可压缩数据效果极佳，但对已压缩格式（JPEG、PNG、MP4）几乎无效。对混合内容（如固件包），应拆分处理，而不是一刀切使用相同参数。

误区三：混淆“压缩率”与“解压速度”。XZ 的解压速度通常在 50~200MB/s，远慢于 LZ4 的 1~4GB/s。如果应用需要频繁读取压缩数据（如数据库页压缩），XZ 可能成为性能瓶颈。此时应考虑 Zstandard（Zstd）作为折中方案。

误区四：忽视多线程支持。XZ 默认单线程压缩，但通过 xz -T 0 可启用多线程。多线程会按块并行压缩，但每个块独立编码，压缩率会略有下降（约 1%~2%）。在 8 核服务器上，压缩时间可缩短 5~6 倍，值得权衡。

复盘整个 XZ 算法原理，可以提炼出三条核心决策准则：字典大小决定内存上限，匹配深度决定压缩时间，区间编码决定压缩率上限。理解这三者的关系，就能在具体场景中做出合理的参数选择，而不是盲目套用默认配置。