\[tab:previous\], and with lower space redundancy on small alphabets). We also show how our result can be used to improve an existing text index that achieves $k$-th order entropy [@FMMN07]. In Sections \[sec:permutations\] and \[sec:functions\], respectively, we show how to apply our data structure to store a compressed permutation, a compressed function and a compressed dynamic collection of disjoint sets, while supporting a rich set of operations on those. This improves or gives alternatives to the best previous results [@BN09; @MRRR03; @HKP09]. We have approached these applications in such a way that an improvement to our main result, however achieved, translates into improved bounds for them as well.

Alphabet partitioning {#sec:partitioning}
=====================

Let $s$ be a sequence over effective alphabet $[1..\sigma]$, that is, every character appears in $s$, thus $\sigma \le n$ (at the end of the section we handle this issue). The zero-order entropy of $s$ is $H_0(s) = \sum_{a\in[1..\sigma]}
\frac{{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}}{n}\lg\frac{n}{{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}}$, where ${\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}$ is the number of occurrences of the character $a$ in $s$. Note that by convexity we have $nH_0(s) \ge (\sigma-1)\lg n +
(n-\sigma+1)\lg (n/(n-\sigma+1))$, a property we will use later.

Our results are based on the following 