of Table \[tab:previous\]). In Section \[sec:partitioning\] we show how to combine the strengths of these data structures [@GMR06; @FMMN07], obtaining the best from both plus compressed redundancy. The technique can be summarized as partitioning the alphabet into sub-alphabets according to the characters’ frequencies in $s$, storing in a multiary wavelet tree [@FMMN07] the string that results from replacing the characters in $s$ by identifiers of their sub-alphabets, and storing separate strings, each the projection of $s$ to the characters of $s$ belonging to each sub-alphabet, this time using Golynski [et al.]{}’s [@GMR06] structure for large alphabets. We achieve a data structure that stores a string $s[1..n]$ in $n H_0 (s) + o(n) (H_0 (s) + 1)$ bits, thus guaranteeing that the redundancy stays negligible even when the text is very compressible. It supports queries in the times shown in Table \[tab:previous\] (rows 5 and 6 give two alternatives).

Then we consider various extensions and applications of our main result. In Section \[sec:higher-order\] we show how to achieve compression in terms of the $k$th-order empirical entropy $H_k (s)$ of $s$, by giving up or slowing down [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries (thus giving a simpler construction to achieve row 4 in Table 