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

Given an n-length text over a sigma-size alphabet, we propose a framework for dynamic rank/select structures on the text and some of its applications. For a small alphabet with a <= log n, we propose a two-level structure consisting of a counting scheme and a storing scheme that supports O(log n) worst-case time rank/select operations and O(log n) amortized time insert/delete operations. For a large alphabet with log n < sigma <= n, we extend it to obtain O((1+ log sigma/log log n) worst-case time rank/select and O((1 + log sigma/log log n) log n) 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(log log sigma) time rank using n' log sigma + O(n) bits and our dynamic version gives O((1 + log sigma/log log n) log n) time operations in n' log sigma + o(n' log sigma ) + O(n) bits. (C) 2009 Elsevier B.V. All rights reserved.