Run Compressed Rank/Select for Large Alphabets

Given a string of length $n$ that is composed of $r$ runs of letters from the alphabet $\{0,1,\dots ,\sigma -1\}$ such that $2\le \sigma \le r$, we describe a data structure that, provided $r\le n\mathrm{/}{\log }^{\omega (1)}n$, stores the string in $r\log \frac{n\sigma }{r}+o(r\log \frac{n\sigma }{r})$ bits and supports select and access queries in $O(\log \frac{\log (n\mathrm{/}r)}{\log \log n})$ time and rank queries in $O(\log \frac{\log (n\sigma \mathrm{/}r)}{\log \log n})$ time. We show that $r\log \frac{n(\sigma -1)}{r}-O(\log \frac{n}{r})$ bits are necessary for any such data structure and, thus, our solution is succinct. We also describe a data structure that uses $(1 + \epsilon)r\log\frac{n\sigma}{r} + O®$bits,where$\epsilon > 0$ is an arbitrary constant, with the same query times but without the restriction $r\le n\mathrm{/}{\log }^{\omega (1)}n$. By simple reductions to the colored predecessor problem, we show that the query times are optimal in the important case $r\ge 2^{{\log }^{\delta }n}$, for an arbitrary constant $\delta >0$. We implement our solution and compare it with the state of the art, showing that the closest competitors consume 31-46% more space.