压缩着还能改：一个动态压缩自索引的论文

理化学研究所 AIP 的压缩信息处理团队有一篇论文被 ESA 2026 接收：

Dynamic Grammar-Compressed Self-Index in δ-Optimal Space 西本崇晃、田部井靖生

标题里的三个词各自代表一个约束：动态（能改）、文法压缩（压得小）、δ-最优空间（压到理论下界附近）。问题在于，以前这三件事只能同时做到两件。

问题长什么样

有一类数据天然高度重复：

• 基因组序列集合（许多个体的同一段序列几乎一样）
• Web 存档（同一个站点的几百个快照）
• 版本控制里的文档集合（相邻版本只差几行）

重复性意味着可以压得非常小。压缩自索引（compressed self-index）更进一步：压着存，但不需要解压就能在上面做模式匹配 —— 这是「压缩」和「索引」原本互相冲突的两件事被合到了一起。

麻烦在于，现实里的字符串数据不是静态的。基因组库在加新样本，存档在加新快照，仓库在提交。

• 高性能的压缩自索引方法，绝大多数是为静态数据设计的 —— 数据一变，整体重建
• 支持更新的方法则很难同时做到高压缩率、快速检索、高效更新

dynamic RR-index 的取舍

论文提出的结构叫 dynamic RR-index，基于文法压缩：把字符串里反复出现的结构用一组文法规则表示，规则集本身就是压缩形式。

它的关键做法是：把检索需要的信息，用可更新的形式管理起来。于是压缩、检索、插入删除可以同时存在。

理论结果是在期望意义上达到 δ-最优空间（δ-optimal space）。δ 这个量衡量的是「数据的重复性有多高」——重复性越高，理论下界越低。所谓 δ-最优，就是「在利用重复性这件事上，存储空间已经接近理论下界」。

作者的说法是：据他们所知，这是第一个达到 δ-最优空间的动态压缩数据结构。

论文摘要里还提到用 37 GB 规模的 Wikipedia 数据做了验证（我拿到的摘要在这里被截断，具体数字没看到，所以不引用）。

为什么这件事难

这里有一个很多人低估的张力：

压缩利用的是「重复」，而「重复」在数据被修改时会变化。

举个简单的例子：如果一个串里 abc 出现了 100 万次，压缩器会把它抽成一条规则，于是 100 万次出现只存一次。现在你删掉其中 10 万次出现 —— 那条规则还有意义吗？如果那条规则里嵌着另一条规则，牵连面有多大？

静态算法可以先看完整个数据再决定文法，然后一切冻结。动态算法必须在每次修改后局部地修文法，同时保证：

• 文法规模不膨胀（否则压缩率慢慢退化）
• 索引仍然有效（否则查询要退化成扫描）
• 修文法的代价是次线性的（否则一次插入就和重建一样贵）

这三个要求互相拉扯，而 δ-最优空间这个目标意味着连常数因子都卡得很紧。

这件事离日常有多远

诚实地说：很远。你不会明天就在业务代码里用上它。

但这类结果的受众不是应用开发者，而是：

• 基因组数据库（数据量巨大、重复度高、持续增长，三个条件全中）
• Web 存档（Internet Archive 那种规模）
• 版本控制系统的底层索引（如果你想让 git log -S 这类历史检索更快）

这些场景的共同点是：数据大到「重建一次索引」是几小时到几天的事，而数据又一直在变。对它们来说，「能改」不是锦上添花，是能不能用的分界线。

我的判断

理论论文的价值往往不在「现在能用」，而在它证明了哪一对约束其实不矛盾。

在这之前，工程上的常识是「压缩和可更新，挑一个」。这篇论文说的是：在 δ-最优空间这个明确的指标下，两者可以同时成立。至于常数因子和实现难度是不是让它在实践中可用，那是后续几年的事 —— 但**「不可能」这个判断已经被推翻了**，而这正是理论该做的事。