Dynamic Compressed Representation of Texts with Rank/Select
Sunho Lee, Kunsoo Park · Journal of Computing Science and Engineering · 2009
Given an n-length text T over a $\sigma$ -size alphabet, we present a compressed representation of T which supports retrieving queries of rank/select/access and updating queries of insert/delete. For a measure of compression, we use the empirical entropy H(T), which defines a lower bound nH(T) bits for any algorithm to compress T of n log $\sigma$ bits. Our representation takes this entropy bound of T, i.e., nH(T) $\leq$ n log $\sigma$ bits, and an additional bits less than the text size, i.e., o(n log $\sigma$ ) + O(n) bits. In compressed space of nH(T) + o(n log $\sigma$ ) + O(n) bits, our representation supports O(log n) time queries for a log n-size alphabet and its extension provides O(( $1+\frac{{\log}\;{\sigma}}{{\log}\;{\log}\;n}$ ) log n) time queries for a $\sigma$ -size alphabet.