圧縮したまま変更できる：動的圧縮自己索引の論文

理化学研究所 AIP の圧縮情報処理チームの論文が ESA 2026 に採択されました。

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

タイトルの三つの語は三つの制約です。動的（変更できる）、文法圧縮（小さく保つ）、δ-最適空間（理論的下界の近くに収まる）。問題は、この三つが同時には二つしか成立しなかったことです。

問題の形

世の中には本質的に極めて反復性の高いデータがあります。

• ゲノム配列の集合（多数の個体で同じ領域はほぼ同一）
• ウェブアーカイブ（同一サイトの数百のスナップショット）
• バージョン管理下の文書集合（隣接する版は数行しか違わない）

反復性は極めてよく圧縮できることを意味します。圧縮自己索引はさらに進み、圧縮した形で保存しつつ、展開せずにパターン照合を行います。かつて相反していた二つを融合したものです。

厄介なのは、現実の文字列データが静的でないことです。ゲノムリポジトリは標本を増やし、アーカイブはスナップショットを増やし、リポジトリはコミットを増やします。

• 高性能な圧縮自己索引のほとんどは静的データ向けに設計されており、変更すれば全体を再構築します
• 更新に対応する手法は、高い圧縮率・高速な検索・効率的な更新を同時に実現するのが困難でした

dynamic RR-index の取引

提案された構造は dynamic RR-index で、文法圧縮に基づきます。文字列に繰り返し現れる構造を文法規則の集合として表し、その規則集合自体が圧縮表現になります。

要点は、検索に必要な情報を更新可能な形で管理することです。これにより圧縮・検索・挿入削除が共存します。

理論的成果は期待値の意味で δ-最適空間を達成することです。δ はデータの反復性の高さを測る量で、反復性が高いほど理論的下界は低くなります。δ-最適であるとは、反復性を活用しつつ記憶領域がその下界に近いことを意味します。

著者らの主張では、δ-最適空間を達成する初めての動的圧縮データ構造です。

抄録では 37 GB 規模の Wikipedia データでの検証にも触れられています。手元の抄録はそこで切れているため、具体的な数値は引用しません。

なぜ難しいのか

過小評価されがちな緊張関係があります。

圧縮は「繰り返し」を利用し、その繰り返しはデータが変わると変化します。

小さな例を挙げます。abc が百万回現れるなら、圧縮器はそれを一つの規則に括り出し、百万回の出現が一回分のコストになります。ここで十万回を削除したら、その規則はまだ価値があるでしょうか。その規則が別の規則を内包していたら、影響はどこまで及びますか。

静的アルゴリズムは入力を最後まで読んでから文法を決め、凍結できます。動的アルゴリズムは編集のたびに文法を局所的に修復しつつ、次を保証しなければなりません。

• 文法が膨張しない（さもなくば圧縮率が静かに劣化する）
• 索引が有効なまま（さもなくば検索が走査に退化する）
• 修復が劣線形（さもなくば一回の挿入が再構築と同じ費用になる）

この三つは互いに引き合い、δ-最適空間という目標は定数因子まで厳しく縛ります。

日常からどれだけ遠いか

正直に言えば遠いです。明日アプリケーションコードで使うことはありません。

この種の成果の受け手はアプリ開発者ではなく：

• ゲノムデータベース（巨大・高反復・増え続ける。三条件が揃う）
• ウェブアーカイブ（Internet Archive 規模）
• バージョン管理の下位索引（git log -S のような履歴検索を速くしたい場合）

共通するのは、データが「索引の再構築に数時間から数日かかる」規模であり、しかも変わり続けることです。彼らにとって変更可能性は付け足しではなく、使えるかどうかの分岐点です。

私の結論

理論論文の価値は通常「今使える」ことではなく、どの制約の組が実は矛盾していないかを証明することにあります。

これ以前、工学の常識は「圧縮と更新性、どちらかを選べ」でした。この論文は、δ-最適空間という明確な尺度のもとで両者が同時に成立すると述べています。定数因子と実装難度が実用性を許すかは今後数年の話です。しかし**「不可能」という判断はすでに覆されました**。それこそが理論の仕事です。