Constant-time $\psi$ queries in $O \left( r \log \fracnr + r \log \sigma \right)$ bits
<|reference_start|>Constant-time $\psi$ queries in $O \left( r \log \fracnr + r \log \sigma \right)$ bits: Given a text $T [1..n]$ over an alphabet of size $\sigma$ whose BWT has $r$ runs, we can store $T$ in $O \left( r \log \frac{n}{r} + r \log \sigma \right)$ bits such that we can answer $\psi$ queries in constant time.<|reference_end|>
@article{gagie2024constant-time,
    title={Constant-time $\psi$ queries in $O \left( r \log \frac{n}{r} + r \log
  \sigma \right)$ bits},
    author={Travis Gagie, Giovanni Manzini, Gonzalo Navarro and Marinella
  Sciortino},
    journal={arXiv preprint arXiv:2408.04537},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04537},
    primaryClass={cs.DS}
}