$s$ into $n'$ blocks of length $b = \frac{\log_\sigma n}{2}$ and store the sequence $s'$ of blocks in $n' H_0 (s') + {\ensuremath{\mathcal{O}\left( {n'} \right)}}$ bits while still supporting ${\ensuremath{\mathcal{O}\left( {1} \right)}}$-time access to the blocks; with ${\ensuremath{\mathcal{O}\left( {\sigma^b b \lg \sigma} \right)}} = o (n)$ more bits, we can support ${\ensuremath{\mathcal{O}\left( {1} \right)}}$-time access to the individual characters. Ferragina and Venturini showed that $n' H_0 (s') \leq n H_k (s) + {\ensuremath{\mathcal{O}\left( {(n / b) k \lg \sigma} \right)}}$ for $k \leq b$, so for $k = o (\log_\sigma n)$ we use a total of at most $n H_k (s) + o (n) \lg \sigma$ bits. Notice that, with Theorem \[thm:partitioning\]$(ii)$, we need only $n' H_0 (s') + o (n') (H_0 (s') + 1)$ bits to store $s'$ (although sadly this does not improve the final bound).[^4]

Barbay, He, Munro and Rao [@BHMR07] showed how, given a data structure that supports only [$\mathsf{access}$]{} queries, it is possible to build a succinct index of size $n\,o (\lg \sigma)$ bits that supports [$\mathsf{rank}$]{} and [$\mathsf{select}$]{}. For example, building a succinct index on top of Ferragina and Venturini’s data structure — whose size is bounded in terms of $H_k (s)$ — gives 