character of $s$, which we denote $s [i]$; $s.{\ensuremath{\mathsf{rank}}}_a (i)$ returns the number of occurrences of the character $a$ up to position $i$; and $s.{\ensuremath{\mathsf{select}}}_a (i)$ returns the position of the $i$th occurrence of $a$ in $s$. Initial results [@highOrderEntropyCompressedTextIndexes] provided data structures using $n\lg\sigma+o(n\lg\sigma)$ bits, where $n$ and $\sigma$ are the sizes of the text and its alphabet, respectively, and $\lg$ denotes the logarithm in base two. The indexing space in $o(n\lg\sigma)$ is considered asymptotically “negligible” compared to the space required to hold the main data, while providing support for the operators in time ${\ensuremath{\mathcal{O}\left( {\lg\sigma} \right)}}$ (and ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ in later results [@GMR06]), a clear improvement on naive data structures.

Regularities in the string permit further reductions in the space, from $n\lg\sigma$ bits down to $nH_k(s)$ bits where $H_k (s)$ denotes the $k$th-order empirical entropy of $s$ (i.e., the minimum self-information of $s$ with respect to a $k$th-order Markov source; see Manzini [@Man01] for a definition and discussion). The challenge of compressing the string [*while still supporting the operators efficiently*]{} was solved through various alternative data structures, using as little as $nH_k(s)+o(n\lg\sigma)$ bits while still supporting the operators in the same times [@highOrderEntropyCompressedTextIndexes; @BHMR07].

One problem with 