Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.24080 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917442192670720 |
|---|---|
| author | Nishimoto, Takaaki Tabei, Yasuo |
| author_facet | Nishimoto, Takaaki Tabei, Yasuo |
| contents | 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 $δ$-optimal lower bound of $Ω(δ\log(n \log σ/ (δ\log n)) \log n)$ bits up to constant factors, where $n$ is the string length, $σ$ is the alphabet size, and $δ$ is the substring complexity. Their dynamic counterparts, however, remain scarce: every existing dynamic self-index either fails to attain $δ$-optimal space, pays at least $Θ(\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 $δ$-optimal space. The index occupies expected $O(δ\log(n \log σ/ (δ\log n)) \log n)$ bits, answers locate queries in expected $O(m + \log m \log^{2} n + \mathit{occ} (\log n / \log \log n))$ time (where $m$ is the pattern length and $\mathit{occ}$ is the number of occurrences), and supports insertions and deletions of a length-$m'$ substring in expected amortized $O(m' \log^{2} n + \log^{3} n)$ time, with no dependence on the LCP. On eleven highly repetitive corpora, including a $37$ GB Wikipedia dump and a $59$ GB human-chromosome collection, the dynamic RR-index is up to $77\times$ faster than the dynamic r-index on updates and up to $11\times$ faster than other dynamic indexes on locate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24080 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space Nishimoto, Takaaki Tabei, Yasuo Data Structures and Algorithms 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 $δ$-optimal lower bound of $Ω(δ\log(n \log σ/ (δ\log n)) \log n)$ bits up to constant factors, where $n$ is the string length, $σ$ is the alphabet size, and $δ$ is the substring complexity. Their dynamic counterparts, however, remain scarce: every existing dynamic self-index either fails to attain $δ$-optimal space, pays at least $Θ(\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 $δ$-optimal space. The index occupies expected $O(δ\log(n \log σ/ (δ\log n)) \log n)$ bits, answers locate queries in expected $O(m + \log m \log^{2} n + \mathit{occ} (\log n / \log \log n))$ time (where $m$ is the pattern length and $\mathit{occ}$ is the number of occurrences), and supports insertions and deletions of a length-$m'$ substring in expected amortized $O(m' \log^{2} n + \log^{3} n)$ time, with no dependence on the LCP. On eleven highly repetitive corpora, including a $37$ GB Wikipedia dump and a $59$ GB human-chromosome collection, the dynamic RR-index is up to $77\times$ faster than the dynamic r-index on updates and up to $11\times$ faster than other dynamic indexes on locate. |
| title | Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.24080 |