{\ensuremath{\mathcal{O}\left( {\sigma n^\epsilon + (n / t)
\lg n} \right)}}$ bits and supports $\pi^k()$ and $\pi^{- k}()$ queries in $O(1/\epsilon +
t)$ time; these queries are useful when working on compressed suffix arrays and trees.

Compressing functions and dynamic collections of disjoint sets {#sec:functions}
==============================================================

Hreinsson, Kr[ø]{}yer and Pagh [@HKP09] recently showed how, given $X = \{x_1, \ldots, x_n\} \subseteq [U]$ and $f: [U] \rightarrow [1..\sigma]$, where $[U]$ is the set of numbers whose binary representations fit in a machine word, they can store $f$ restricted to $X$ in compressed form with constant-time evaluation. Their representation occupies at most $(1 + \delta) n H_0 (f) + n \min (p_{\max} + 0.086, 1.82 (1 - p_{\max})) + o (\sigma)$ bits, where $\delta > 0$ is a given constant and $p_{\max}$ is the relative frequency of the most common function value. We note that this bound holds even when $\sigma \gg n$.

Notice that, in the special case where $X = [1..n]$ and $\sigma \leq n$, we can achieve constant-time evaluation and a better space bound using either Theorems \[thm:partitioning\] or \[thm:index\]. With Theorem \[thm:partitioning\] we can also find all the elements in $[1..n]$ that $f$ maps to a given element in 