the actual times are, for example, ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma_\ell} \right)}} = {\ensuremath{\mathcal{O}\left( {\lg\lg\min(\sigma,n/{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})} \right)}}$.

\[thm:partitioning\] We can store $s[1..n]$ over effective alphabet $[1..\sigma]$ in $n H_0 (s) + o(n)(H_0 (s) + 1)$ bits and support [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$, ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$, and ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time, respectively (variant $(i)$). Alternatively, we can support [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$, ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma \lg \lg \lg \sigma} \right)}}$ and ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$ time, respectively (variant $(ii)$). All the $\sigma$ terms in the time complexities are actually $\min(\sigma,n/{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})$, where $a=s[i]$ for [$\mathsf{access}$]{}, and $a$ is the character argument for [$\mathsf{rank}$]{} and [$\mathsf{select}$]{}.

In the most general case, $s$ is a sequence over an alphabet $\Sigma$ which is not an effective alphabet, and $\sigma$ symbols from $\Sigma$ occur in $s$. Let $\Sigma'$ be the set of elements that occur in $s$; we can map characters from $\Sigma'$ to elements of $[1..\sigma]$ by replacing each $a\in \Sigma'$ with its rank in $\Sigma'$. All elements of $\Sigma'$ are stored in the indexed dictionary data structure described by Raman et al. [@RRR02], so that the 