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

다국어 초록 (Multilingual Abstract)

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 O((1+logσloglogn)logn) worst-case time rank/select and O((1+logσloglogn)logn) 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<SUP>'</SUP>-length RLE of an n-length text, our static version provides O(1) time select and O(loglogσ) time rank using n<SUP>'</SUP>logσ+O(n) bits and our dynamic version gives O((1+logσloglogn)logn) time operations in n<SUP>'</SUP>logσ+o(n<SUP>'</SUP>logσ)+O(n) bits.