such space is that, on highly compressible practical data, the $o(n\lg\sigma)$ bits of the index are no longer negligible compared to the space used to encode the compressed data. Hence the challenge is to retain the efficient support for the operators while compressing the index redundancy as well. In this paper we solve this challenge in the case of zero-order entropy compression, that is, the redundancy of our data structure is proportional to the zero-order entropy of the text, plus $o(n)$ bits. Moreover, our data structure not only still supports the operators in good time, but in some cases it supports them in better time than less compressed ones (e.g. in ${\ensuremath{\mathcal{O}\left( {\lg \lg \min (\sigma, n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})} \right)}}$ time, where $a$ is the character concerned): see Table \[tab:previous\] for a systematic comparison.

For example, the representation by Golynski et al. [@GMR06] does not compress $s$[^2] and uses additional ${\ensuremath{\mathcal{O}\left( {\frac{n\lg\sigma}{\lg\lg\sigma}} \right)}}=n\,o(\lg\sigma)$ bits, but offers log-logarithmic times for the operations (see rows 2 and 3 of Table \[tab:previous\]); Ferragina et al. [@FMMN07] achieve zero-order compression plus ${\ensuremath{\mathcal{O}\left( {\frac{n\lg\sigma\lg\lg n}{\lg n}} \right)}} = o(n)\lg\sigma$ bits, supporting the operations in ${\ensuremath{\mathcal{O}\left( {1+\frac{\lg\sigma}{\lg\lg n}} \right)}}$ time (see row 1 