---
abstract: 'We present a data structure that stores a string $s[1..n]$ over the alphabet $[1..\sigma]$ in $nH_0(s) + o(n)(H_0(s){+}1)$ bits, where $H_0(s)$ is the zero-order entropy of $s$. This data structure supports the operators [$\mathsf{access}$]{} and [$\mathsf{rank}$]{} in time ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$, and the [$\mathsf{select}$]{} operator in constant time. This result improves on previously known data structures using $nH_0(s)+o(n\lg\sigma)$ bits, where on highly compressible instances the redundancy $o(n\lg\sigma)$ can cease to be negligible compared to the $nH_0(s)$ bits that encode the data. The technique is based on combining previous results through an ingenious partitioning of the alphabet, and practical enough to be implementable. It applies not only to strings, but also to several other compact data structures. For example, we achieve $(i)$ the first representation of a string $s$ using $nH_k(s)+o(n)\lg\sigma$ bits and supporting [$\mathsf{access}$]{}, [$\mathsf{rank}$]{}, and [$\mathsf{select}$]{} in poly-loglog time; $(ii)$ faster search times for the smallest existing full-text self-index; $(iii)$ compressed permutations $\pi$ with times for $\pi()$ and $\pi^{-1}()$ improved to log-logarithmic; and $(iv)$ the first compressed representation of dynamic collections of disjoint sets.'
author:
- Jérémy Barbay
- 'Travis Gagie[^1]'
- 'Gonzalo Navarro$^\star$'
- Yakov Nekrich
bibliography:
- 'paper.bib'
title: 'Alphabet Partitioning for Compressed Rank/Select and 