跳到正文
ZLIB × LEAN / 算法精读与验证

窗口与匹配

重复片段的长度与距离从哪里来,以及为什么只需保留近期字节。

这一环节的任务

重复片段可以用“回退距离、复制长度”描述。压缩器保留近期历史,寻找可以复用的内容;滑动窗口限制保留的历史范围,哈希链减少需要逐字节比较的候选。

在全局图中定位 ↗

前 2 章先展开算法、数据布局与优化,最后一章连接证明思路。可以按顺序读,也可以从已经熟悉的阶段进入。

  1. 01
    算法精读

    滑动窗口与哈希链

    理解保留哪些旧字节,怎样在有限内存里持续寻找重复。

    ↗
  2. 02
    算法精读

    匹配搜索与延迟决策

    从已处理字节中找出可引用的片段,权衡比较次数和匹配长度。

    ↗
  3. 03
    证明思路

    匹配搜索的证明思路

    说明搬移位置和提前停止搜索后,引用为什么仍能还原输入。

    ↗
ZLIB × LEAN

全局目录

当前位置窗口与匹配