them the bounds shown in the fourth row of Table \[tab:previous\]. We now show how to reduce the size of the succinct index to $o (n) \lg \sigma$ bits, giving us the bounds in the last row of the table.

\[thm:index\] We can store $s[1..n]$ in $n H_k (s) + o(n) \lg \sigma$ bits, for $k = o (\log_\sigma n)$, and support [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$, ${\ensuremath{\mathcal{O}\left( {(\lg \lg \sigma)^2 \lg \lg \lg \sigma} \right)}}$, and ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma \lg \lg \lg \sigma} \right)}}$ time, respectively.

We use Ferragina and Venturini’s data structure [@FV07] to store the sequence $s'$ of blocks in $n H_k (s) + o (n) \lg \sigma$ bits such that we can access any block or character in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. We then store the distinct blocks that occur in $s'$ in a data structure $B$ such that we can perform [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries on the contents of any block in ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$ time; since there are $\sigma^b = {\ensuremath{\mathcal{O}\left( {\sqrt{n}} \right)}}$ possible distinct blocks, this takes ${\ensuremath{\mathcal{O}\left( {\sqrt{n} (b \lg \sigma)} \right)}} = o (n)$ bits.

We build a binary relation $R$ in $[1..\sigma] \times 