Dynamic r-Index: An Updatable Self-Index in LCP-Bounded Time

A self-index is a compressed data structure that supports locate queries-reporting all positions where a given pattern occurs in a string while maintaining the string in compressed form. While many self-indexes have been proposed, developing dynamically updatable ones supporting string insertions and deletions remains a challenge. The r-index (Gagie et al., JACM'20) is a representative static self-index based on the run-length Burrows-Wheeler transform (RLBWT), designed for highly repetitive strings. We present the dynamic r-index, a dynamic extension of the r-index that achieves updates in LCP-bounded time. The dynamic r-index supports count queries in$\mathcal{O}(m \log r / \log \log r)$time and locate queries in$\mathcal{O}(m \log r / \log \log r+$occ$\log r)$time, using$\mathcal{O}(r)$words of space, where$m$is the length of a query with occ occurrences and$r$is the number of runs in the RLBWT. Crucially, update operations are supported in$\mathcal{O}\left(\left(m+L_{\max}\right) \log n\right)$time for a substring of length$m$, where$n$is the text length and$L_{\max}$is the maximum LCP value; the average running time is$\mathcal{O}\left(\left(m+L_{\text{avg}}\right) \log n\right)$, where$L_{\text{avg}}$is the average LCP value. This LCP-bounded complexity is particularly advantageous for highly repetitive strings where LCP values are typically small. We experimentally demonstrate the practical efficiency of the dynamic r-index on various highly repetitive datasets.