Applications'
---

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 access and rank in time O(lg lg sigma), and the 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 relatively simple, based on combining previous results through an ingenious partitioning of the alphabet. It applies not only to strings, but also to permutations, functions, binary relations, and to dynamically maintaining a collection of disjoint sets and its index.

Introduction {#sec:introduction}
============

Search operators on strings have many important applications, to the point that one is willing to sacrifice some additional space to index the string in order to support the operators in less time. The most important operators serve as primitives to implement many others, in particular pattern matching in full-text databases (see, e.g., [@NM07; @CN08; @MN07; @RR08] for recent discussions): given a string $s$, $s.{\ensuremath{\mathsf{access}}}(i)$ returns the $i$th 