Dynamic rank/select structures with applications to run-length encoded texts

Given an n-length text over a σ-size alphabet, we propose a framework for dynamic rank/select structures on the text and some of its applications. For a small alphabet with σ≤logn, we propose a two-level structure consisting of a counting scheme and a storing scheme that supports O(logn) worst-case time rank/select operations and O(logn) amortized time insert/delete operations. For a large alphabet with logn<σ≤n, we extend it to obtain worst-case time rank/select and amortized time insert/delete. Our structure provides a simple representation of an index for a collection of texts. In addition, we present rank/select structures on run-length encoding (RLE) of a text. For the n′-length RLE of an n-length text, our static version provides O(1) time select and O(loglogσ) time rank using n′logσ+O(n) bits and our dynamic version gives time operations in n′logσ+o(n′logσ)+O(n) bits.