理化学研究所 革新知能統合研究センター（RIKEN AIP）圧縮情報処理チームの西本崇晃研究員と田部井靖生チームディレクターによる論文 “Dynamic Grammar-Compressed Self-Index in δ-Optimal Space” が、アルゴリズム分野の主要な国際会議 European Symposium on Algorithms（ESA 2026） に採択されました。
概要
本研究は、大規模な文字列データを「圧縮したまま」高速に検索し、さらにデータの挿入や削除にも対応できる新しい圧縮データ構造を提案するものです。
近年、ゲノム配列の集合、Web アーカイブ、バージョン管理された文書集合など、似た部分文字列が何度も現れる大規模な文字列データが急速に増えています。このような文字列データは高い反復性を持つため、適切に圧縮することで少ない記憶領域で保存できます。一方で、実際の文字列データは静的ではなく、日々更新されます。そのため、データを小さく保持するだけでなく、圧縮した状態のまま高速に検索し、更新にも効率的に対応することが重要になります。
文字列検索のための圧縮データ構造は、文字列を圧縮して保存しながら、元のデータ全体を復元することなく検索できる技術です。しかし、多くの高性能な手法は静的なデータを対象としており、データが変更されると全体を作り直す必要がありました。一方、更新に対応した従来手法では、高い圧縮率、高速な検索、効率的な更新を同時に実現することが難しいという課題がありました。
研究の手法と成果
本研究では、この課題を解決するために、文法圧縮に基づく新しい圧縮データ構造dynamic RR-indexを提案しました。
dynamic RR-index は、文字列中の繰り返し構造を文法圧縮で小さく表現し、検索に必要な情報を更新可能な形で管理することで、圧縮したまま検索と挿入・削除を行うことを可能にします。
理論的には、提案手法は期待値の意味で δ-最適な記憶領域（δ-optimal space）を達成します。これは、反復性の高い文字列に対して、理論的にほぼ最適な記憶領域でデータを保持しながら、検索と更新を行えることを意味します。著者らの知る限り、このような δ-最適な記憶領域を達成する初めての動的な圧縮データ構造です。
37 GB の Wikipedia 編集履歴データや 59 GB のヒト染色体データなどを用いたベンチマーク実験では、dynamic RR-index が、更新操作で既存の dynamic r-index より最大 77 倍、検索処理で他の動的手法より最大 11 倍高速であることが確認されました。
今後の展望
本成果は、ゲノムデータベース、Web アーカイブ、バージョン管理された文書集合など、継続的に更新される大規模な文字列データを効率よく扱うための基盤技術として期待されます。圧縮データ構造の理論的発展に加え、大規模データ管理や検索システムへの応用にもつながる成果です。
