Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts

摘要

Given an n-length text over a σ-size alphabet, we propose a dynamic rank-select structure that supports O((1+ (log σ)/(log log n)) log n) time operations in n log σ + o(n log σ) bits space. If σ ＜ log n, then the operation time is O(log n). In addition, we consider both static and dynamic rank-select structures on the run-length encoding (RLE) of a text. For an n'-length RLE of an n′-length text, we present a static structure that gives O(1) time select and O(log log σ) time rank using n′ log σ + O(n) bits and a dynamic structure that provides O((1 + (log σ)/(log log n)) log n) time operations in n′ log σ + o(n′ log σ) + O(n) bits.