---
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 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 character of $s$, which we denote $s [i]$; $s.{\ensuremath{\mathsf{rank}}}_a (i)$ returns the number of occurrences of the character $a$ up to position $i$; and $s.{\ensuremath{\mathsf{select}}}_a (i)$ returns the position of the $i$th occurrence of $a$ in $s$. Initial results [@highOrderEntropyCompressedTextIndexes] provided data structures using $n\lg\sigma+o(n\lg\sigma)$ bits, where $n$ and $\sigma$ are the sizes of the text and its alphabet, respectively, and $\lg$ denotes the logarithm in base two. The indexing space in $o(n\lg\sigma)$ is considered asymptotically “negligible” compared to the space required to hold the main data, while providing support for the operators in time ${\ensuremath{\mathcal{O}\left( {\lg\sigma} \right)}}$ (and ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ in later results [@GMR06]), a clear improvement on naive data structures.

Regularities in the string permit further reductions in the space, from $n\lg\sigma$ bits down to $nH_k(s)$ bits where $H_k (s)$ denotes the $k$th-order empirical entropy of $s$ (i.e., the minimum self-information of $s$ with respect to a $k$th-order Markov source; see Manzini [@Man01] for a definition and discussion). The challenge of compressing the string [*while still supporting the operators efficiently*]{} was solved through various alternative data structures, using as little as $nH_k(s)+o(n\lg\sigma)$ bits while still supporting the operators in the same times [@highOrderEntropyCompressedTextIndexes; @BHMR07].

One problem with such space is that, on highly compressible practical data, the $o(n\lg\sigma)$ bits of the index are no longer negligible compared to the space used to encode the compressed data. Hence the challenge is to retain the efficient support for the operators while compressing the index redundancy as well. In this paper we solve this challenge in the case of zero-order entropy compression, that is, the redundancy of our data structure is proportional to the zero-order entropy of the text, plus $o(n)$ bits. Moreover, our data structure not only still supports the operators in good time, but in some cases it supports them in better time than less compressed ones (e.g. in ${\ensuremath{\mathcal{O}\left( {\lg \lg \min (\sigma, n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})} \right)}}$ time, where $a$ is the character concerned): see Table \[tab:previous\] for a systematic comparison.

For example, the representation by Golynski et al. [@GMR06] does not compress $s$[^2] and uses additional ${\ensuremath{\mathcal{O}\left( {\frac{n\lg\sigma}{\lg\lg\sigma}} \right)}}=n\,o(\lg\sigma)$ bits, but offers log-logarithmic times for the operations (see rows 2 and 3 of Table \[tab:previous\]); Ferragina et al. [@FMMN07] achieve zero-order compression plus ${\ensuremath{\mathcal{O}\left( {\frac{n\lg\sigma\lg\lg n}{\lg n}} \right)}} = o(n)\lg\sigma$ bits, supporting the operations in ${\ensuremath{\mathcal{O}\left( {1+\frac{\lg\sigma}{\lg\lg n}} \right)}}$ time (see row 1 of Table \[tab:previous\]). In Section \[sec:partitioning\] we show how to combine the strengths of these data structures [@GMR06; @FMMN07], obtaining the best from both plus compressed redundancy. The technique can be summarized as partitioning the alphabet into sub-alphabets according to the characters’ frequencies in $s$, storing in a multiary wavelet tree [@FMMN07] the string that results from replacing the characters in $s$ by identifiers of their sub-alphabets, and storing separate strings, each the projection of $s$ to the characters of $s$ belonging to each sub-alphabet, this time using Golynski [et al.]{}’s [@GMR06] structure for large alphabets. We achieve a data structure that stores a string $s[1..n]$ in $n H_0 (s) + o(n) (H_0 (s) + 1)$ bits, thus guaranteeing that the redundancy stays negligible even when the text is very compressible. It supports queries in the times shown in Table \[tab:previous\] (rows 5 and 6 give two alternatives).

Then we consider various extensions and applications of our main result. In Section \[sec:higher-order\] we show how to achieve compression in terms of the $k$th-order empirical entropy $H_k (s)$ of $s$, by giving up or slowing down [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries (thus giving a simpler construction to achieve row 4 in Table \[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 alphabet partitioning scheme. Let $t$ be the string in which each character $s [i]$ is replaced by the number $$t[i] = \lceil \lg (n / {\ensuremath{\mathsf{occ}\left( {s [i]}, {s} \right)}}) \lg n \rceil
\leq \left\lceil \lg^2 n \right\rceil\,.$$ For $0 \leq \ell \leq \lceil \lg^2 n\rceil$, let $s_\ell$ be the string consisting of those characters $s [i]$ that were replaced by $\ell$ in $t$, and let $\sigma_\ell$ be the number of distinct characters in $s_\ell$. More precisely, $s_\ell$ will be a sequence over alphabet $[1..\sigma_\ell]$. The mapping with $[1..\sigma]$ will be done by storing another sequence ${\ensuremath{{m}}}[1..\sigma]$ so that ${\ensuremath{{m}}}[a]$ will be the sub-alphabet number assigned to character $a$. Hence character $a$ is mapped to character ${\ensuremath{{m}}}.{\ensuremath{\mathsf{rank}}}_{{\ensuremath{{m}}}[a]}(a)$ in string $s_{{\ensuremath{{m}}}[a]}$, and symbol $x \in [1..\sigma_\ell]$ in $s_\ell$ corresponds to character ${\ensuremath{{m}}}.{\ensuremath{\mathsf{select}}}_\ell(x)$.

Notice that, if both $a$ and $b$ are replaced by the same number in $t$, then $\lg (n / {\ensuremath{\mathsf{occ}\left( {b}, {s} \right)}}) - \lg (n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) < 1 / \lg n$ and so ${\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} / {\ensuremath{\mathsf{occ}\left( {b}, {s} \right)}} < 2^{1 / \lg n}$. It follows that, if $a$ is replaced by $\ell$ in $t$, then $\sigma_\ell < 2^{1 / \lg n} |s_\ell| /
$ and so [$\mathsf{occ}\left( {a}, {s} \right)$]{} (by fixing $a$ and summing over all those $b$ replaced by $\ell$). Since $$\sum_{\lceil \lg (n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) \lg n \rceil = \ell} {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}
= |s_\ell|
\hspace{5ex} \mbox{and} \hspace{5ex}
\sum_a {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}
= \sum_\ell |s_\ell|
= n\,,$$ we have $$\begin{aligned}
& & \lefteqn{n H_0 (t) + \sum_\ell |s_\ell| \lg \sigma_\ell} \\[1ex]
& < & \sum_\ell |s_\ell| \lg (n / |s_\ell|) + \sum_\ell \sum_{\lceil \lg (n
/ {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) \lg n \rceil = \ell} {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} \lg \left( 2^\frac{1}
{\lg n} |s_\ell| / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} \right)\\[1ex]
& = & \sum_a {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} \lg (n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) + n / \lg n \\[1ex]
& = & n H_0 (s) + o(n)\,.
$$

In other words, if we represent $t$ with $H_0 (t)$ bits per symbol and each $s_\ell$ with $\lg \sigma_\ell$ bits per symbol, then we achieve a good overall compression. Thus we can obtain a very compact representation of a string $s$ by storing a compact representation of $t$ and storing each $s_{\ell}$ as an “uncompressed” string over an alphabet of size $\sigma_{\ell}$.

Now we show how our approach can be used to obtain a fast and compact rank/select data structure. Suppose we have a data structure $T$ that supports [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries on $t$; another structure ${\ensuremath{{M}}}$ that supports the same queries on ${\ensuremath{{m}}}$; and data structures $S_1, \ldots, S_{\left\lceil \lg^2 n
\right\rceil}$ that support the same queries on $s_1, \ldots, s_{\left\lceil
\lg^2 n \right\rceil}$. With these data structures we can implement $$\begin{aligned}
s.{\ensuremath{\mathsf{access}}}(i) & ~=~ & l.{\ensuremath{\mathsf{select}}}_\ell(s_\ell.{\ensuremath{\mathsf{access}}}(t.{\ensuremath{\mathsf{rank}}}_\ell(i))),
                        ~\textrm{where}~\ell = t.{\ensuremath{\mathsf{access}}}(i); \\[1ex]
s.{\ensuremath{\mathsf{rank}}}_a (i) & ~=~ & s_\ell.{\ensuremath{\mathsf{rank}}}_c (t.{\ensuremath{\mathsf{rank}}}_\ell (i)),
                        ~\textrm{where}~\ell = {\ensuremath{{m}}}.{\ensuremath{\mathsf{access}}}(a)
                        ~\textrm{and}~ c = {\ensuremath{{m}}}.{\ensuremath{\mathsf{rank}}}_\ell(a); \\[1ex]
s.{\ensuremath{\mathsf{select}}}_a (i) & ~=~ & t.{\ensuremath{\mathsf{select}}}_\ell (s_\ell.{\ensuremath{\mathsf{select}}}_c (i))
                        ~\textrm{where}~\ell = {\ensuremath{{m}}}.{\ensuremath{\mathsf{access}}}(a)
                        ~\textrm{and}~ c = {\ensuremath{{m}}}.{\ensuremath{\mathsf{rank}}}_\ell(a).\end{aligned}$$

We implement $T$ and ${\ensuremath{{M}}}$ as multiary wavelet trees [@FMMN07]; we implement each $S_\ell$ as either a multiary wavelet tree or an instance of Golynski et al.’s [@GMR06] [$\mathsf{access}$]{}/[$\mathsf{rank}$]{}/[$\mathsf{select}$]{} data structure, depending on whether $\sigma_\ell \leq \lg n$ or not. The wavelet tree for $T$ uses at most $n H_0 (t) + o (n)$ bits and operates in constant time, because its alphabet size is polylogarithmic. If $S_\ell$ is implemented as a wavelet tree, it uses at most $|s_\ell| H_0 (s_\ell) + o (|s_\ell|)$ bits and operates in constant time for the same reason; otherwise it uses at most $|s_\ell| \lg \sigma_\ell
     + {\ensuremath{\mathcal{O}\left( {\frac{|s_\ell| \lg \sigma_\ell}{\lg \lg \sigma_\ell}} \right)}}
\leq |s_\ell| \lg \sigma_\ell
     + {\ensuremath{\mathcal{O}\left( {\frac{|s_\ell| \lg \sigma_\ell}{\lg \lg \lg n}} \right)}}$ bits (the latter because $\sigma_\ell > \lg n$). Thus in all cases the space for $s_\ell$ is bounded by $|s_\ell| \lg \sigma_\ell + o(|s_\ell| \lg \sigma_\ell)$ bits.[^3] Finally, since ${\ensuremath{{M}}}$ is a sequence of length $\sigma$ over an alphabet of size $\lceil \lg^2 n \rceil$, the wavelet tree for ${\ensuremath{{M}}}$ takes at most ${\ensuremath{\mathcal{O}\left( {\sigma \lg \lg n} \right)}}$ bits. Because of the property we referred to in the beginning of this section, $nH_0(s) \ge (\sigma-1)\lg n$, this space is also $o(nH_0(s))$. By these calculations, the space for $T$, ${\ensuremath{{M}}}$ and the $S_\ell$’s adds up to $nH_0(s) + o(nH_0(s)) + o(n)$. Depending on which time tradeoff we use for Golynski et al.’s data structure, we obtain the results of Table \[tab:previous\]. We can refine the time complexity by noticing that the only non-constant times are due to operating on some string $s_\ell$, where the alphabet is of size $\sigma_\ell < 2^{1/\lg n}|s_\ell|/{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}$, where $a$ is the character in question. Thus the actual times are, for example, ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma_\ell} \right)}} = {\ensuremath{\mathcal{O}\left( {\lg\lg\min(\sigma,n/{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})} \right)}}$.

\[thm:partitioning\] We can store $s[1..n]$ over effective alphabet $[1..\sigma]$ in $n H_0 (s) + o(n)(H_0 (s) + 1)$ bits and support [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$, ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$, and ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time, respectively (variant $(i)$). Alternatively, we can support [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$, ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma \lg \lg \lg \sigma} \right)}}$ and ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$ time, respectively (variant $(ii)$). All the $\sigma$ terms in the time complexities are actually $\min(\sigma,n/{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})$, where $a=s[i]$ for [$\mathsf{access}$]{}, and $a$ is the character argument for [$\mathsf{rank}$]{} and [$\mathsf{select}$]{}.

In the most general case, $s$ is a sequence over an alphabet $\Sigma$ which is not an effective alphabet, and $\sigma$ symbols from $\Sigma$ occur in $s$. Let $\Sigma'$ be the set of elements that occur in $s$; we can map characters from $\Sigma'$ to elements of $[1..\sigma]$ by replacing each $a\in \Sigma'$ with its rank in $\Sigma'$. All elements of $\Sigma'$ are stored in the indexed dictionary data structure described by Raman et al. [@RRR02], so that the following queries are supported in constant time: for any $a\in\Sigma'$ its rank in $\Sigma'$ can be found (for any $a\not\in \Sigma'$ the answer is $-1$); for any $i\in [1..\sigma]$ the $i$-th smallest element in $\Sigma'$ can be found. The indexed dictionary of Raman [[*et al.*]{}]{} [@RRR02] uses $\sigma\lg(em/\sigma)+o(\sigma)+O(\lg \lg m)$ bits of space, where $e$ is the base of the natural logarithm and $m$ is the maximal element in $\Sigma'$; the value of $m$ can be specified with additional $O(\lg m)$ bits. We replace every element in $s$ by its rank in $\Sigma'$; the resulting string can be stored using Theorem \[thm:partitioning\]. Hence, in the general case the space usage is increased by $\sigma\lg(em/\sigma)+o(\sigma)+O(\lg m)$ bits and the asymptotic time complexity of queries remains unchanged.

Higher-order entropies {#sec:higher-order}
======================

Sadakane and Grossi [@SG06] showed how to store $s$ in $n H_k (s) + o (n) \lg \sigma$ bits, for $k = o (\log_\sigma n)$, and still support ${\ensuremath{\mathcal{O}\left( {1} \right)}}$-time access (and, moreover, retrieving any ${\ensuremath{\mathcal{O}\left( {\log_\sigma n} \right)}}$ contiguous symbols in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time). Their scheme was simplified by González and Navarro [@GN06] and then further simplified by Ferragina and Venturini [@FV07]. The main idea is to break $s$ into $n'$ blocks of length $b = \frac{\log_\sigma n}{2}$ and store the sequence $s'$ of blocks in $n' H_0 (s') + {\ensuremath{\mathcal{O}\left( {n'} \right)}}$ bits while still supporting ${\ensuremath{\mathcal{O}\left( {1} \right)}}$-time access to the blocks; with ${\ensuremath{\mathcal{O}\left( {\sigma^b b \lg \sigma} \right)}} = o (n)$ more bits, we can support ${\ensuremath{\mathcal{O}\left( {1} \right)}}$-time access to the individual characters. Ferragina and Venturini showed that $n' H_0 (s') \leq n H_k (s) + {\ensuremath{\mathcal{O}\left( {(n / b) k \lg \sigma} \right)}}$ for $k \leq b$, so for $k = o (\log_\sigma n)$ we use a total of at most $n H_k (s) + o (n) \lg \sigma$ bits. Notice that, with Theorem \[thm:partitioning\]$(ii)$, we need only $n' H_0 (s') + o (n') (H_0 (s') + 1)$ bits to store $s'$ (although sadly this does not improve the final bound).[^4]

Barbay, He, Munro and Rao [@BHMR07] showed how, given a data structure that supports only [$\mathsf{access}$]{} queries, it is possible to build a succinct index of size $n\,o (\lg \sigma)$ bits that supports [$\mathsf{rank}$]{} and [$\mathsf{select}$]{}. For example, building a succinct index on top of Ferragina and Venturini’s data structure — whose size is bounded in terms of $H_k (s)$ — gives them the bounds shown in the fourth row of Table \[tab:previous\]. We now show how to reduce the size of the succinct index to $o (n) \lg \sigma$ bits, giving us the bounds in the last row of the table.

\[thm:index\] We can store $s[1..n]$ in $n H_k (s) + o(n) \lg \sigma$ bits, for $k = o (\log_\sigma n)$, and support [$\mathsf{access}$]{}, [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$, ${\ensuremath{\mathcal{O}\left( {(\lg \lg \sigma)^2 \lg \lg \lg \sigma} \right)}}$, and ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma \lg \lg \lg \sigma} \right)}}$ time, respectively.

We use Ferragina and Venturini’s data structure [@FV07] to store the sequence $s'$ of blocks in $n H_k (s) + o (n) \lg \sigma$ bits such that we can access any block or character in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. We then store the distinct blocks that occur in $s'$ in a data structure $B$ such that we can perform [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries on the contents of any block in ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma} \right)}}$ time; since there are $\sigma^b = {\ensuremath{\mathcal{O}\left( {\sqrt{n}} \right)}}$ possible distinct blocks, this takes ${\ensuremath{\mathcal{O}\left( {\sqrt{n} (b \lg \sigma)} \right)}} = o (n)$ bits.

We build a binary relation $R$ in $[1..\sigma] \times [1..n']$, so that $R (a, j)$ if and only if character $a$ appears in block $s' [j]$. Rather than storing $R$ explicitly, we store only its succinct index [@BHMR07 Theorem 3.2], which uses Ferragina and Venturini’s data structure and takes ${\ensuremath{\mathcal{O}\left( {p \lg \sigma / \lg \lg \sigma} \right)}}$ more bits, where $p \leq \min (n, n' \sigma)$ is the number of pairs in $R$. If $\sigma = {\ensuremath{\mathcal{O}\left( {1} \right)}}$ then ${\ensuremath{\mathcal{O}\left( {p \lg \sigma / \lg \lg \sigma} \right)}} = {\ensuremath{\mathcal{O}\left( {n'} \right)}} = o (n)$; otherwise, ${\ensuremath{\mathcal{O}\left( {p \lg \sigma / \lg \lg \sigma} \right)}} = {\ensuremath{\mathcal{O}\left( {n \lg \sigma / \lg \lg \lg n} \right)}} = o (n) \lg \sigma$. This succinct index allows us to find the number of blocks in $s' [1..j]$ containing $a$’s in ${\ensuremath{\mathcal{O}\left( {(\lg \lg \sigma)^2 \lg \lg \lg \sigma} \right)}}$ time, and to find the $r$th block containing $a$’s in time ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma \lg \lg \lg \sigma} \right)}}$.

For each of the $p$ pairs $(a,j)$ in $R$, we store the number of times $a$ appears in $S'[j]$. Assume we store these numbers $x$ as $x+1$ bits $1^x0$ and concatenate them all, row-wise, into a bitmap $P$ with $n$ 1s and $p$ 0s. Calculations similar to those above show we can store $P$ in $o (n) \lg \sigma$ bits and support [$\mathsf{rank}$]{} and [$\mathsf{select}$]{} queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time [@RRR02]. With $P$ we can compute, in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time, the total number of $a$’s across the first $r$ blocks containing $a$’s, and the smallest $r$ such that the first $r$ blocks containing $a$’s contain at least $j$ of them.

To perform $s.{\ensuremath{\mathsf{rank}}}_a (j)$, we compute the index $j' = \lceil j / b \rceil$ in $s'$ of the block containing the $j$th character of $s$; use Ferragina and Venturini’s data structure and $B$ to find number of $a$’s within $s' [j']$ up to position $j \bmod b$; use $R$ to find the number of blocks in $s' [1.. j' - 1]$ that contain $a$’s; and use $P$ to find the total number of $a$’s in those preceding blocks. To perform $s.{\ensuremath{\mathsf{select}}}_a (j)$, we use $P$ to find the smallest $r$ such that the first $r$ blocks containing $a$’s contain at least $j$ of them; use $P$ again to find the total number $t$ of $a$’s in the first $r - 1$ blocks containing $a$’s; use $R$ to find the $r$th block $s' [j']$ containing $a$’s; and use Ferragina and Venturini’s data structure and $B$ to find the position of the $(j - t)$th $a$ in $s' [j']$.

Alternatively, we can achieve $k$-th order entropy by partitioning the Burrows-Wheeler transform of the sequence and encoding each partition to zero-order entropy [@FMMN07]. This representation, however, is more useful for [*self-indexing*]{} than for supporting [$\mathsf{access}$]{}, [$\mathsf{rank}$]{}, and [$\mathsf{select}$]{} on the sequence. Self-indexes also represent a sequence, but they support other operations related to text searching. By using Theorem \[thm:partitioning\]$(i)$ to represent the partitions of Ferragina et al. [@FMMN07], on which we need to carry out [$\mathsf{access}$]{} and [$\mathsf{rank}$]{}, we achieve the following result, improving previous ones [@FMMN07; @GMR06].

Let $t[1..n]$ be a text string over alphabet $[1..\sigma]$, such that $\sigma=o(n)$.[^5] Then we can represent $s$ using $nH_k(s) + o(n)\lg\sigma$ bits of space, for any $k \le \alpha \log_\sigma n$ and constant $0<\alpha<1$. The following operations can be carried out: $(i)$ count the number of occurrences of a pattern $p[1..m]$ in $t$, in time ${\ensuremath{\mathcal{O}\left( {m\lg\lg\sigma} \right)}}$; $(ii)$ locate any such occurrence in time ${\ensuremath{\mathcal{O}\left( {\log_\sigma n \lg\lg n
\lg\lg\sigma} \right)}}$; $(iii)$ extract $t[l,r]$ in time ${\ensuremath{\mathcal{O}\left( {(r-l+\log_\sigma n \lg\lg n)\lg\lg\sigma} \right)}}$.

For this particular locating time we are sampling one out of $\log_\sigma n \lg\lg n$ text positions.

Compressing permutations {#sec:permutations}
========================

We now show how to use [$\mathsf{access}$]{}/[$\mathsf{rank}$]{}/[$\mathsf{select}$]{} data structures to store a compressed permutation. We follow Barbay and Navarro’s notation [@BN09] and improve their space and, especially, their time performance. They measure the compressibility of a permutation $\pi$ in terms of the entropy of the distribution of the lengths of [*runs*]{} of different kinds. Let $\pi$ be covered by $\rho$ runs (using any of the previous definitions of runs [@sortingShuffledMonotoneSequences; @BN09; @sortingPresortedFiles]) of lengths ${\ensuremath{\mathsf{runs}}}(\pi) = \langle n_1, \ldots, n_\rho\rangle$. Then $H({\ensuremath{\mathsf{runs}}}(\pi)) = \sum \frac{n_i}{n}\lg\frac{n}{n_i} \le
\lg\rho$ is called the [*entropy*]{} of the runs (and, because $n_i
\ge 1$, it also holds $nH({\ensuremath{\mathsf{runs}}}(\pi)) \ge (\rho-1)\lg n$). We first consider permutations which are interleaved sequences of increasing or decreasing values as first defined by Levcopoulos [[*et al.*]{}]{} [@sortingShuffledMonotoneSequences] for adaptive sorting, and later on for compression [@BN09], and then give improved results for more specific classes of runs. In both cases we consider first the application of the permutation $\pi()$ and its inverse, ${\ensuremath{\pi^{-1}}}()$, to show later how to extend the support to the iterated applications of the permutation, $\pi^k()$, extending and improving the previous results of Munro [[*et al.*]{}]{} [@MRRR03].

\[thm:runs\] Let $\pi$ be a permutation on $n$ elements that consists of $\rho$ interleaved increasing or decreasing runs. We can store $\pi$ in $2 n H ({\ensuremath{\mathsf{runs}}}(\pi)) + o(n)(H ({\ensuremath{\mathsf{runs}}}(\pi)) + 1)$ bits and perform $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \rho} \right)}}$ time.

We first replace all the elements of the $r$th run by $r$, for $1\le r\le\rho$. Let $s$ be the resulting string and let $s'$ be $s$ permuted according to $\pi$. We store $s$ and $s'$ using Theorem \[thm:partitioning\]$(i)$ and store $\rho$ bits indicating whether each run is increasing or decreasing. Notice $s' [\pi (i)] = s [i]$ and, if $\pi (i)$ is part of an increasing run, then $s'.{\ensuremath{\mathsf{rank}}}_{s [i]} (\pi (i)) = s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i)$, so $$\pi (i) = s'.{\ensuremath{\mathsf{select}}}_{s [i]} \left( s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i) \right)\,;$$ if $\pi (i)$ is part of a decreasing run, then $s'.{\ensuremath{\mathsf{rank}}}_{s [i]} (\pi (i))
= s.{\ensuremath{\mathsf{rank}}}_{s [i]} (n) +1 - s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i)$, so $$\pi (i) = s'.{\ensuremath{\mathsf{select}}}_{s [i]} \left( s.{\ensuremath{\mathsf{rank}}}_{s [i]} (n) +1 - s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i) \right)\,.$$ A ${\ensuremath{\pi^{-1}}}()$ query is symmetric. The space of the bitmap is $\rho = o(nH({\ensuremath{\mathsf{runs}}}(\pi)))$ because $nH({\ensuremath{\mathsf{runs}}}(\pi)) \ge (\rho-1)\lg n$.

We now consider the case of runs restricted to be strictly incrementing ($+1$) or decrementing ($-1$), while still letting them be interleaved: such runs were not directly considered before.

\[thm:strict runs\] Let $\pi$ be a permutation on $n$ elements that consists of $\rho$ interleaved incrementing or decrementing runs. For any constant $\epsilon >
0$, we can store $\pi$ in $n H ({\ensuremath{\mathsf{runs}}}(\pi)) + o(n)(H({\ensuremath{\mathsf{runs}}}(\pi)) + 1)
+ {\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}}$ bits and perform $\pi()$ queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \rho} \right)}}$ time and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {1/\epsilon} \right)}}$ time.

Due to space constrains, we leave the proof of this theorem to the appendix.

Notice that, if $\pi$ consists of $\rho$ contiguous increasing or decreasing runs, then ${\ensuremath{\pi^{-1}}}$ consists of $\rho$ interleaved incrementing or decrementing runs. Therefore, Theorem \[thm:strict runs\] applies to such permutations as well, with the time bounds for $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries reversed.

\[thm:contiguous runs\] Let $\pi$ be a permutation on $n$ elements that consists of $\rho$ contiguous increasing or decreasing runs. For any constant $\epsilon >
0$, we can store $\pi$ in $n H ({\ensuremath{\mathsf{runs}}}(\pi)) + o(n)(H ({\ensuremath{\mathsf{runs}}}(\pi)) + 1)+
{\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}} $ bits and perform $\pi()$ queries in ${\ensuremath{\mathcal{O}\left( {1/\epsilon} \right)}}$ time and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {\lg \lg \rho} \right)}}$ time.

If $\pi$’s runs are both contiguous and incrementing or decrementing, then so are the runs of ${\ensuremath{\pi^{-1}}}$. In this case we can store $\pi$ in ${\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}}$ bits and answer $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. To do this, we use two predecessor data structures: for each run, in one of the data structures we store the position $j$ in $\pi$ of the first element of the run, with $\pi (j)$ as auxiliary information; in the other, we store $\pi (j)$, with $j$ as auxiliary information. To perform a query $\pi (i)$, we use the first predecessor data structure to find the starting position $j$ of the run containing $i$, and return $\pi (j) + i - j$. A ${\ensuremath{\pi^{-1}}}()$ query is symmetric. Decreasing runs are handled as before.

\[thm:contiguous strict runs\] Let $\pi$ be a permutation on $n$ elements that consists of $\rho$ contiguous incrementing or decrementing runs. For any constant $\epsilon >
0$, we can store $\pi$ in ${\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}}$ bits and perform $\pi()$ and ${\ensuremath{\pi^{-1}}}()$ queries in ${\ensuremath{\mathcal{O}\left( {1/\epsilon} \right)}}$ time.

We now show how to achieve exponentiation ($\pi^k(i)$, $\pi^{-k}(i)$) within compressed space. Munro [[*et al.*]{}]{} [@MRRR03] reduced the problem of supporting exponentiation on a permutation $\pi$ to the support of the direct and inverse application of another permutation, related but with quite distinct runs than $\pi$. Combining any of our results (Theorem \[thm:runs\] to \[thm:contiguous strict runs\]) with this technique does yield a compression, but without any relation to the runs of $\pi$. The following construction, extending the technique from Munro [[*et al.*]{}]{} [@MRRR03], retains the compressibility properties of $\pi$ by building a companion data structure that uses small space to support the exponentiation, thus allowing the compression of the main data structure with any of Theorems \[thm:runs\] to \[thm:contiguous strict runs\].

\[thm:exponent\] Suppose we have a data structure $D$ that stores a permutation $\pi$ on $n$ elements and supports queries $\pi()$ in time $g (\pi)$. Then for any $t \leq n$, we can build a succinct index that takes ${\ensuremath{\mathcal{O}\left( {(n / t) \lg n} \right)}}$ bits and, when used in conjunction with $D$, supports $\pi^k()$ and $\pi^{-k}()$ queries in ${\ensuremath{\mathcal{O}\left( {t\,g (\pi)} \right)}}$ time.

We decompose $\pi$ into its cycles and, for every cycle of length at least $t$, store the cycle’s length and an array containing pointers to every $t$th element in the cycle, which we call ‘marked’. We also store a compressed binary string, aligned to $\pi$, indicating the marked elements. For each marked element, we record to which cycle it belongs and its position in the array of that cycle.

To compute $\pi^k (i)$, we repeatedly apply $\pi()$ at most $t$ times until we either loop (in which case we need apply $\pi()$ at most $t$ more times to find $\pi^k (i)$ in the loop) or we find a marked element. Once we have reached a marked element, we use its array position and cycle length to find the pointer to the last marked element in the cycle before $\pi^k (i)$, and the number of applications of $\pi()$ needed to map that to $\pi^k (i)$ (at most $t$). A $\pi^{- k}$ query is similar (note that it does not need to use ${\ensuremath{\pi^{-1}}}()$).

As an example, given a constant $\epsilon > 0$ and a value $t \leq n$, we can combine Theorems \[thm:contiguous runs\] and \[thm:exponent\] to obtain a data structure that stores Sadakane’s $\Psi$ function [@Sad03] for $s$ in $n H_0 (s) + o (n) (H_0 (s) + 1) + {\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 $[1..\sigma]$ (using [$\mathsf{select}$]{}), find an element’s rank among the elements with the same image, or the size of the preimage (using [$\mathsf{rank}$]{}), etc.

Let $f: [1..n] \rightarrow [1..\sigma]$ be a surjective function. We can represent $f$ using $nH_0(f) + o(n)(H_0(f)+1)$ bits so that any $f(i)$ can be computed in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. Moreover, each element of $f^{-1}(a)$ can be computed in ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ time, and $|f^{-1}(a)|$ requires time ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma\lg\lg\lg\sigma} \right)}}$. Alternatively we can compute $f(i)$ and $|f^{-1}(a)|$ in time ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ and deliver any element of $f^{-1}(a)$ in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time.

We can also achieve interesting results with our theorems from Section \[sec:permutations\], as runs arise naturally in many real-life functions. For example, suppose we decompose $f
(1), \ldots, f(n)$ into $\rho$ interleaved non-increasing or non-decreasing runs. Then we can store it as a combination of the permutation $\pi$ that stably sorts the values $f(i)$, plus a compressed [$\mathsf{rank}$]{}/[$\mathsf{select}$]{} data structure storing a binary string $b[1..n+\sigma+1]$ with $\sigma+1$ bits set to 1: if $f$ maps $i$ values in $[1..n]$ to a value $j$ in $[1..\sigma]$ then, in $b$, there are $i$ bits set to 0 between the $j$th and $(j + 1)$th bits set to 1. Therefore, $$f (i) = b.{\ensuremath{\mathsf{rank}}}_1 (b.{\ensuremath{\mathsf{select}}}_0 (\pi (i)))$$ and the theorem below follows immediately from Theorem \[thm:runs\]. Similarly, $f^{-1}(a)$ is obtained by applying ${\ensuremath{\pi^{-1}}}()$ to the area $b.{\ensuremath{\mathsf{rank}}}_0(b.{\ensuremath{\mathsf{select}}}_1(a))+1 \ldots b.{\ensuremath{\mathsf{rank}}}_0(b.{\ensuremath{\mathsf{select}}}_1$ $(a+1))$, and $|f^{-1}(a)|$ is computed in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time. Notice $H ({\ensuremath{\mathsf{runs}}}(\pi)) = H({\ensuremath{\mathsf{runs}}}(f))$ $\leq H_0(f)$, and that $b$ can be stored in ${\ensuremath{\mathcal{O}\left( {\sigma\lg\frac{n}{\sigma}} \right)}}+o(n)$ bits [@RRR02].

\[thm:function\] Let $f: [1..n] \rightarrow [1..\sigma]$ be a surjective function[^6] with $f (1), \ldots, f (n)$ consisting of $\rho$ interleaved non-increasing or non-decreasing runs. Then we can store $f$ in $2 n H ({\ensuremath{\mathsf{runs}}}(f)) + o (n)(H ({\ensuremath{\mathsf{runs}}}(f)) + 1)
+{\ensuremath{\mathcal{O}\left( {\sigma\lg\frac{n}{\sigma}} \right)}}$ bits and compute any $f(i)$, as well as retrieve any element in $f^{-1}(a)$, in ${\ensuremath{\mathcal{O}\left( {\lg \lg \rho} \right)}}$ time. The size $|f^{-1}(a)|$ can be computed in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time.

We can obtain a more competitive result if $f$ is split into contiguous runs, but their entropy is no longer bounded by the zero-order entropy of string $f$.

\[thm:contiguous function\] Let $f: [1..n] \rightarrow [1..\sigma]$ be a surjective function with $f (1), \ldots, f (n)$ consisting of $\rho$ contiguous non-increasing or non-decreasing runs. Then we can represent $f$ in $n H ({\ensuremath{\mathsf{runs}}}(f)) +
o(n)(H ({\ensuremath{\mathsf{runs}}}(f)) + 1) +{\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}} +{\ensuremath{\mathcal{O}\left( {\sigma\lg\frac{n}{\sigma}} \right)}}$ bits, for any constant $\epsilon>0$, and compute any $f(i)$ in ${\ensuremath{\mathcal{O}\left( {\lg\lg\sigma} \right)}}$ time, as well as retrieve any element in $f^{-1}(a)$ in ${\ensuremath{\mathcal{O}\left( {1/\epsilon} \right)}}$ time. The size $|f^{-1}(a)|$ can be computed in ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ time.

Finally, we now give what is, to the best of our knowledge, the first result about storing a compressed collection of disjoint sets. The key point in the next theorem is that, as the sets in the collection $C$ are merged, our space bound shrinks with the entropy of the distribution ${\ensuremath{\mathsf{sets}}}(C)$ of elements to sets.

\[thm:disjoint\] Let $C$ be a collection of disjoint sets whose union is $[1..n]$. For any constant $\epsilon > 0$, we can store $C$ in $(1 +
  \epsilon) n H ({\ensuremath{\mathsf{sets}}}(C)) + {\ensuremath{\mathcal{O}\left( {|C| \lg n} \right)}} + o (n) (H ({\ensuremath{\mathsf{sets}}}(C)) +
  1)$ bits and perform any sequence of $m$ [$\mathsf{union}$]{} and [$\mathsf{find}$]{} operations in a total of ${\ensuremath{\mathcal{O}\left( {(1/\epsilon)(m + n) \lg \lg n} \right)}}$ time.

Due to space constraints, we leave the proof of this theorem to the appendix.

Future work
===========

Assigning variable-length codes according to frequencies is a standard data compression technique, yet it complicates random access. We have introduced a so-called alphabet partitioning technique, which essentially groups all the string symbols with the same logarithm of the normalized frequency and maintains a separate string $t$ that assigns each character symbol to its group. It turns out that it suffices to compress the string $t$ and store all other data in virtually uncompressed form. Thus we reduce the problem of storing a string over an alphabet of size $\sigma$ to the problem of storing a string over an alphabet of size poly-logarithmic in $n$. This is a simple and practical method to retain compression while providing direct access to any symbol of the sequence. Actually, we go much further and show how to support not only access, but also [$\mathsf{rank}$]{}/[$\mathsf{select}$]{}operations on the compressed sequence, which opens the door to many applications of compressed data structures, where we have improved or simplified a number of the best results up to date. We have approached the applications in such a way that an improvement to our main result, however achieved, will translate into improved bounds for the applications. Nevertheless, we believe alphabet partitioning is likely to find more applications, all the more because it is practical and simple to implement.

In the full paper we will discuss other directions for research. First, we can reduce the dependence on the alphabet size from ${\ensuremath{\mathcal{O}\left( {\sigma\lg\lg n} \right)}}$ to ${\ensuremath{\mathcal{O}\left( {\sigma} \right)}}$ by storing a length-restricted Shannon code in ${\ensuremath{\mathcal{O}\left( {\sigma} \right)}}$ bits [@GNN10], replacing the data structure ${\ensuremath{{M}}}$. To avoid the ${\ensuremath{\mathcal{O}\left( {1} \right)}}$ extra redundancy per character associated with using a length-restricted prefix code, we replace each character in $s$ whose codeword length is at most $\lg \lg n$ by a distinct number in $t$. This increases the alphabet size of $t$ by at most $\lg n$; calculation shows our space bound increases by an ${\ensuremath{\mathcal{O}\left( {1 + 1 / \lg \lg n} \right)}}$-factor and, thus, remains at most $n H_0 (s) + o(n)(H_0 (s) + 1)$. Second, given any constant $c$, we can reduce the $\min (\sigma, n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}})$ in our time bounds by a factor of $(\lg n)^c$; to do this, we further partition each sub-alphabet into $(\lg n)^c$ sub-sub-alphabets. Third, our alphabet partitioning techniques yields a compressed representation of posting lists of sizes $(n_1,\ldots,n_\sigma)$ which supports access, rank and select on the rows in time ${\ensuremath{\mathcal{O}\left( {\lg \lg
  \sigma} \right)}}$, and uses total space for data and index proportional to the entropy $H(n_1,\ldots,n_\sigma)$ of the distribution of those sizes (if the posting lists refer to the words of a text, this is also the zero-order word-based entropy of the text). This is achieved by encoding the string of labels encountered during a row-first traversal, writing a special symbol (e.g. $\$$) at each change of row. This improves the space of previously known data structures [@adaptiveSearchingInSuccinctlyEncodedBinaryRelationsAndTreeStructuredDocumentsTCS], and improves the time complexity of previous compression results [@indexCompressionThroughDocumentReordering]. A more far-fetched challenge is to obtain an indexed data structure using space closer to $nH_k(s)+o(n(1+H_k(s)))$ bits than $nH_k(s)+o(n\lg \sigma)$, while still supporting the operators in reasonable time.

I described to Travis on the board how this can be applied to binary relations by simply combining it to the B+S=R reduction from the paper [@adaptiveSearchingInSuccinctlyEncodedBinaryRelationsAndTreeStructuredDocumentsTCS]. Basically, reduce the binary rank and select on the rows of a binary relation to the text rank and select, by a string $S$ composed of the row numbers of the ones encountered in the column first order traversal of the binary relation, and a bit vector $B$ counting the number of ones in each column in unary. Compressing $S$ with Theorem \[thm:partitioning\] yields a compression in function of the entropy of the length of the posting lists (which in practice is small, there is a lot of diversity in the lengths of the posting lists); same worst case time; improved average time (for the rows of the binary relation which have few ones). As observed by Travis, one can integrate $B$ into $S$ by adding $\$$ signs in $S$ at each change of column, which saves some space (while only doubling the time): instead of $(n+1)\lg\sigma$ bits in the original paper we get now $n\lg(\sigma+1)$ bits. In the compressed version I don’t know how to characterize the relations on which it will allow to compress.

#### Acknowledgments. {#acknowledgments. .unnumbered}

Many thanks to Djamal Belazzougui for helpful comments on a draft of this paper.

Proof of Theorems \[thm:strict runs\] and \[thm:disjoint\]
==========================================================

We first replace all the elements of the $r$th run by $r$, for $1 \leq r \leq
\rho$, considering the runs in order by minimum element. Let $s \in \{1,
\ldots, \rho\}^n$ be the resulting string. We store $s$ using Theorem \[thm:partitioning\]$(i)$; we also store an array containing the runs’ lengths, directions (incrementing or decrementing), and minima, in order by minimum element; and we store a predecessor data structure containing the runs’ minima as keys with their positions in the array as auxiliary information. The predecessor data structure — which is based on the data structure in Lemma 4 of Andersson’s survey paper [@And96] and which we will describe in the full version of this paper — takes ${\ensuremath{\mathcal{O}\left( {\rho n^\epsilon} \right)}}$ bits and answers queries in ${\ensuremath{\mathcal{O}\left( {1/\epsilon} \right)}}$ time. With the array and the predecessor data structure, we can retrieve a run’s data given either its array index or any of its elements.

If $\pi (i)$ is the $j$th element in an incrementing run whose minimum element is $m$, then $\pi (i) = m + j - 1$; on the other hand, if $\pi
(i)$ is the $j$th element of a decrementing run of length $l$ whose minimum element is $m$, then $\pi (i) = m + l - j$. It follows that, given $i$, we can compute $\pi (i)$ by using the query $j = s.{\ensuremath{\mathsf{rank}}}_{s [i]} (i)$ and then an array lookup at position $s[i]$ to find $m$, $l$ and the direction, finally computing $\pi (i)$ from them. Also, given $\pi (i)$, we can compute $i$ by first using a predecessor query to find the run’s array position $r$, then an array lookup to find $m$, $l$ and the direction, then computing $j=\pi(i)-m+1$ (increasing) or $j=m+l-\pi(i)$ (decreasing), and finally using the query $i = s.{\ensuremath{\mathsf{select}}}_r (j)$.

We first choose an arbitrary order for the sets and use Theorem \[thm:partitioning\]$(ii)$ to store the string $s [1..n]$ in which each $s [i]$ is the identifier of the set containing $i$. We then choose an arbitrary representative for each set and store the representatives in both an array and a standard disjoint-set data structure [@TvL84]. Together, our data structures take $n H ({\ensuremath{\mathsf{sets}}}(C)) + {\ensuremath{\mathcal{O}\left( {|C| \lg n} \right)}} + o (n)(H ({\ensuremath{\mathsf{sets}}}(C)) + 1)$ bits. We can perform a query ${\ensuremath{\mathsf{find}}}(i)$ on $C$ by performing ${\ensuremath{\mathsf{find}}}(s [i])$ on the representatives, and perform a ${\ensuremath{\mathsf{union}}}(i, j)$ operation on $C$ by just performing the corresponding operation on the representatives.

In order for our data structure to shrink as we [$\mathsf{union}$]{} the sets, we keep track of $H ({\ensuremath{\mathsf{sets}}}(C))$ and, whenever it shrinks by a factor of $1 +
\epsilon$, we rebuild our entire data structure; we will show in the full version of this paper that this takes ${\ensuremath{\mathcal{O}\left( {n} \right)}}$ time. Since $H ({\ensuremath{\mathsf{sets}}}(C))$ is always less than $\lg n$, we need to rebuild only ${\ensuremath{\mathcal{O}\left( {\log_{1+\epsilon} \lg n} \right)}}={\ensuremath{\mathcal{O}\left( {(1/\epsilon)\lg\lg n} \right)}}$ times. Notice we can stop rebuilding once $n H ({\ensuremath{\mathsf{sets}}}(C)) = o (n)$ as the space bound then becomes dominated by the $o (n)(H ({\ensuremath{\mathsf{sets}}}(C)) + 1)$ term.

[^1]: Funded in part by the Millennium Institute for Cell Dynamics and Biotechnology (ICDB), Grant ICM P05-001-F, Mideplan, Chile.

[^2]: In terms of the usual entropy measures. It compresses to the $k$-th order entropy of a different sequence (A. Golynski, personal communication).

[^3]: We note that this $o(\cdot)$ expression is in all cases asymptotic in $n$: in the case of multiary wavelet trees, it is achieved by using block sizes of length $\frac{\lg n}{2}$ and not $\frac{\lg |s_\ell|}{2}$, at the price of storing universal tables of size ${\ensuremath{\mathcal{O}\left( {\sqrt{n}\lg^{{\ensuremath{\mathcal{O}\left( {1} \right)}}} n} \right)}}$.

[^4]: In this case we do not need $[1..\sigma]$ to be the effective alphabet: In order to achieve any $k > 0$, we need (at the very least) that $\sigma = o (n)$, and thus the extra space for our structure ${\ensuremath{{M}}}$ is ${\ensuremath{\mathcal{O}\left( {\sigma \lg \lg n} \right)}} = o (\sigma \lg n) = o (n \lg \sigma)$, already considered in the space formula.

[^5]: Again, $[1..\sigma]$ does not need to be the effective alphabet.

[^6]: Otherwise we proceed as usual to map the domain to the effective one.
