Dynamic Grammar-Compressed Self-Index in δ \delta -Optimal Space

Takaaki Nishimoto, Yasuo Tabei · 2026

Read Dynamic Grammar-Compressed Self-Index in δ \delta -Optimal Space by Takaaki Nishimoto, Yasuo Tabei (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24080.txt.

Introduction

Nishimoto and Tabei present the dynamic RR-index, the first dynamic self-index to reach delta-optimal space for repetitive strings. Static indexes already meet the bound, but dynamic versions missed it, paid logarithmic time per hit, or slowed with the longest common prefix maximum. Built on restricted recompression run-length programs, it stores delta-optimal bits in expectation, answers locate queries fast, and updates without longest-prefix dependence. On eleven corpora it runs up to 77 times faster on updates and up to 11 times faster on locate queries than rivals.

Catalog record

CREATORTakaaki Nishimoto, Yasuo Tabei
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111935
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.24080

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Grammar-Compressed Self-Index in δ \delta -Optimal Space Takaaki Nishimoto, Yasuo Tabei Abstract A compressed self-index stores a string in compressed form while supporting locate queries without decompression. For highly repetitive strings—arising in web crawls, versioned documents, and genomic collections—static self-indexes can match the δ \delta -optimal lower bound of Ω ⁡ ( δ ​ log ⁡ ( n ​ log ⁡ σ / ( δ ​ log ​ n ) ) ​ log ​ n ) \Omega(\delta\log(n\log\sigma/(\delta\log n))\log n) bits up to constant factors, where n n is the string length, σ \sigma is the alphabet size, and δ \delta is the substring complexity. Their dynamic counterparts, however, remain scarce: every existing dynamic self-index either fails to attain δ \delta -optimal space, pays at least Θ ⁡ ( log ⁡ n ) \Theta(\log n) time per reported occurrence during locate, or exposes the longest common prefix (LCP) of the text inside its update time. We present the dynamic RR-index , a dynamic grammar-compressed self-index built on the restricted recompression run-length straight-line program (RLSLP). To our knowledge, it is the first dynamic self-index to attain δ \delta -optimal space. The index occupies expected 𝒪 ⁡ ( δ ​ log ⁡ ( n ​ log ⁡ σ / ( δ ​ log ​ n ) ) ​ log ​ n ) \mathcal{O}(\delta\log(n\log\sigma/(\delta\log n))\log n) bits, answers locate queries in expected 𝒪 ⁡ ( m + log ⁡ m ​ log 2 ​ n + 𝗈𝖼𝖼 ⁡ ( log ⁡ n / log ⁡ log ⁡ n ) ) \mathcal{O}(m+\log m\log^{2}n+\mathsf{occ}(\log n/\log\log n)) time—where m m is the pattern length and 𝗈𝖼𝖼 \mathsf{occ} is the number of occurrences—and supports insertions and deletions of a length- m ′ m^{\prime} substring in expected amortized 𝒪 ⁡ ( m ′ ​ log 2 ​ n + log 3 ⁡ n ) \mathcal{O}(m^{\prime}\log^{2}n+\log^{3}n) time, with no dependence on the LCP. On eleven highly repetitive corpora, including a 37 37 GB Wikipedia dump and a 59 59 GB human-chromosome collection, the dynamic RR-index is up to 77 × 77\times faster than the dynamic r-index on updates and up to 11 × 11\times faster than other dynamic indexes on locate. RIKEN Center for Advanced Intelligence Project, [email protected] Center for Advanced Intelligence Project, [email protected] ccs Theory of computation Pattern matching keywords Compressed string indexes; grammar-compression, dynamic data structures † † runningauthor: T. Nishimoto and Y. Tabei † † copyright: T. Nishimoto and Y. Tabei † † funding: This work was supported by JST, ACT-X Grant Number JPMJAX24CL, Japan. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Datasets composed of highly repetitive strings—those with many repeated substrings—have grown rapidly in recent years. Typical examples include web pages collected by crawlers [ 14 ] , version-controlled documents such as Wikipedia with its complete edit history [ 46 ] , and, perhaps most notably, biological sequences such as collections of human genomes [ 42 , 45 ] . These datasets are not static: edits, deletions, and new releases arrive continuously. Yet the methods practitioners rely on most heavily, such as the r-index [ 15 ] , a compressed index supporting locate queries, are static : reflecting even a single edit requires rebuilding the index from scratch. There is therefore a strong and growing need to develop dynamic compressed self-indexes for highly repetitive strings, which can be updated efficiently without rebuilding. A practical solution must simultaneously (i) use space proportional to the repetitiveness of the string, (ii) answer locate queries quickly, and (iii) support string insertions and deletions without rebuilding. The third requirement has proven difficult: while compressed self-indexes —data structures that represent the string in compressed form while answering locate queries directly—are well understood in the static case, their dynamic counterparts remain challenging to develop. For highly repetitive strings, compressed self-indexes aim to approach the \delta -optimal space of \mathcal{O}(\delta\log(n\log\sigma/(\delta\log n))\log n) bits established by Kociumaka et al. [ 27 ] , where n is the string length, \sigma is the alphabet size, and \delta is the substring complexity of the string—a repetitiveness measure satisfying \delta\ll n on genomic and versioned corpora. A line of specialized self-indexes—grammar-based [ 7 , 27 , 26 ] , LZ-based [ 8 ] , block-tree–based [ 2 , 29 , 27 ] , and run-length BWT (RLBWT)–based such as the r-index [ 15 ] and OptBWTR [ 36 , 3 ] —has closed much of this gap, with several attaining \delta -optimal space up to constant factors. None, however, supports updates. Only a handful of dynamic self-indexes have been proposed, and each sacrifices at least one of the three requirements (Table 1 in Appendix A gives the full comparison). The dynamic FM-index [ 44 , 31 ] extends the Burrows–Wheeler Transform (BWT) [ 5 ] but uses \mathcal{O}(n\log\sigma) bits, oblivious to repetitiveness, with an \mathcal{O}(\log^{2+\epsilon}n) per-occurrence locate factor. Grammar-based dynamic indexes—the SE-index [ 35 ] , TST-index-d [ 40 ] , and Gawrychowski et al. [ 16 ] —either pay (\log n\log^{*}n)^{2} -type factors in locate/update or require \Omega(n\log n) bits. A recent dynamic r-index [ 38 , 39 ] uses \mathcal{O}(r\log n) bits ( r the number of BWT runs), but its update time \mathcal{O}((m^{\prime}+L_{\max})\log n) depends on the maximum value L_{\max}\leq n of the longest common prefix (LCP) array—the length of the longest repeated substring—which can grow independently of \delta and r as versioned copies accumulate. In short, every existing dynamic self-index either fails to compress to \delta -optimal space, pays at least \Theta(\log n) time per reported occurrence during locate, or exposes the LCP inside update time. We address this gap. Our contributions. We present the dynamic RR-index , a dynamic grammar-compressed self-index built on the restricted recompression RLSLP of Jeż [ 19 ] and Kociumaka et al. [ 28 , 27 ] . Our starting observation is that the derivation tree of a restricted recompression admits a compact DAG representation whose explicit-node count is tied to \delta rather than to r or g . Moreover, insertions and deletions perturb this DAG only along two short popped sequences [ 35 , 18 ] , independently of the maximum LCP value. Combined with two-dimensional range reporting [ 4 , 33 ] and with a path-cached ancestor field that accelerates locate ( \cref sec:improvement), this design simultaneously achieves \delta -optimal space and a sub-logarithmic per-occurrence locate bound. To our knowledge, the dynamic RR-index is the first dynamic self-index to attain \delta -optimal space. Concretely, it occupies expected \delta -optimal space— \mathcal{O}(\delta\log(n\log\sigma/(\delta\log n))\log n) bits—and answers locate queries in expected \mathcal{O}(m+\log m\log^{2}n+\mathsf{occ}(\log n/\log\log n)) time, where m is the pattern length and \mathsf{occ} is the number of occurrences. Insertions and deletions of a length- m^{\prime} substring are supported in expected amortized \mathcal{O}(m^{\prime}\log^{2}n+\log^{3}n) time. We implement and evaluate the dynamic RR-index on eleven highly repetitive corpora, including the 37 GB enwiki Wikipedia dump and the 59 GB chr19 genomic collection, and we show that it is up to

Read the complete text