Practical Compressed Suffix Trees

Abstract

The suffix tree is an extremely important data structure in bioinformatics. Classical implementations require much space, which renders them useless to handle large sequence collections. Recent research has obtained various compressed representations for suffix trees, with widely different space-time tradeoffs. In this paper we show how the use of range min-max trees yields novel representations achieving practical space/time tradeoffs. In addition, we show how those trees can be modified to index highly repetitive collections, obtaining the first compressed suffix tree representation that effectively adapts to that scenario.

1. Introduction

As a result of the sharply falling costs of sequencing, large sequence databases are rapidly emerging, and they will soon grow to thousands of genomes and more. Sequencing machines are already producing terabytes of data per day, at a few thousand dollars per genome, and will cost less very soon (see, e.g., [1]). This raises a number of challenges in bioinformatics, particularly because those sequence databases are meant to be the subject of various analysis processes that require sophisticated data structures built on them.

The suffix tree [2,3,4] is probably the most important of those data structures. Many complex sequence analysis problems are solved through sophisticated traversals over the suffix tree [5]. However, a serious problem of suffix trees, aggravated on large sequence collections, is that they take much space. A naive implementation can easily require 20 bytes per character, and a very optimized one reaches 10 bytes [6]. A way to reduce this space to about 4 bytes per character is to use a simplified structure called a suffix array [7]. However, suffix arrays do not contain sufficient information to carry out all the complex tasks suffix trees are used for. Enhanced suffix arrays [8] extend suffix arrays so as to recover the full suffix tree functionality, raising the space to about 6 bytes per character in practice. Other heuristic space-saving methods [9] achieve about the same.

For example, on DNA sequences, each character could be encoded with just 2 bits, whereas the alternatives we have considered require 32 to 160 bits per character (bpc). This is an overhead of 1600% to 8000%! The situation is also a heresy in terms of Information Theory: Whereas the information contained in a sequence of n symbols over an alphabet of size σ is $nlog\sigma$ bits in the worst case, all the alternatives above require $\Theta (nlogn)$ bits. (Our logarithms are in base 2)

A solution to the large space requirements is of course resorting to secondary memory. However, using suffix trees on secondary memory makes them orders of magnitude slower, as most of the required traversals are highly non-local. A more interesting research direction, which has made much progress in recent years, is to design compressed suffix trees (CSTs). Those compressed representations of suffix trees are able to approach not only the worst-case space of the sequence, but even its information content (i.e., they approach the space of the compressed sequence). CSTs are composed of a compressed suffix array (CSA) plus some extra information that encodes the suffix tree topology and longest common prefix (LCP) information (more details later). The existing solutions can be divided into three categories:

Explicit topology. The first CST proposal was by Sadakane [10,11]. It uses $4n+o\left(n\right)$ bits to represent the suffix tree topology, plus $2n+o\left(n\right)$ bits to represent the LCP values. In addition, it uses Sadakane’s CSA [12], which requires $n{H}_0+O(nloglog\sigma )$ bits, where $H_0$ is the zero-order entropy of the sequence. This structure supports most of the tree navigation operations in constant time (except, notably, going down to a child, which is an important operation), at the price of $\Theta \left(n\right)$ bits of space on top of a CSA.

Sampling. A second proposal was by Russo et al. [13,14]. It is based on sampling some suffix tree nodes and recovering the information on any other node by moving to the nearest sample using suffix links. It requires only $o\left(n\right)$ bits on top of a CSA. By using an FM-index [15] as the CSA, one achieves $n{H}_k+o(nlog\sigma )$ bits of space, where $H_k$ is the k-th order empirical entropy of the sequence (a measure of statistical compressibility [16]), for sufficiently low $k\le \alpha {log}_{\sigma }n$, for any constant $0<\alpha <1$. The navigation operations are supported in polylogarithmic time (at best $\Theta (lognloglogn)$ in their paper).

Intervals. Yet a third proposal was by Fischer et al. [17,18,19]. It avoids the explicit representation of the tree topology by working all the time with the corresponding suffix array intervals. All the suffix tree navigation is reduced to three primitive operations on such intervals: Next/Previous smaller value and range minimum queries (more details later). The proposal achieves a space/time tradeoff that is between the two previous ones: It reduces the $\Theta \left(n\right)$ extra bits of Sadakane to $o\left(n\right)$, and the superlogarithmic operation times of Russo et al. to $O\left({log}^{ϵ}n\right)$, for any constant $0<ϵ<1$. More precisely, the space is $n{H}_k(2max(1,log(1/H_k))+1/ϵ+O\left(1\right))+o(nlog\sigma )$ bits (for the same k ranges as above).

We remark that the space figures include the storage of the sequence itself, as all modern CSAs are self-indexes, that is, they contain both the sequence and its suffix array.

For applications, the practical performance of the above schemes is more relevant than the theoretical figures. The solution based on explicit topology was implemented by Välimäki et al. [20]. As expected from theory, the structure is very fast, achieving a few tens of microseconds per operation, but uses significant space (about 25–35 bpc, close to a suffix array). This undermines its applicability. Very recently, Gog [21] showed that this implementation can be made much more space-efficient, using about 13–17 bpc. This still puts this solution in the range of the “large” CSTs in the context of this paper.

The structure based on sampling was implemented by Russo. As expected from theory again, it was shown to achieve very little space, around 4–6 bpc, which makes it extremely attractive when the sequence is large compared with the available main memory. On the other hand, the structure is much slower than the previous one: Each navigation operation takes the order of milliseconds.

In this paper we present the first implementations of the third approach, based on intervals. As predicted by theory once again, we achieve practical implementations that lie between the two previous extremes (too large or too slow) and offer attractive space/time tradeoffs. One variant shows to be superior to the original implementation of Sadakane’s CST [20] in both space and time: It uses 13–16 bpc (i.e., half the space) and requires a few microseconds per operation (i.e., several times faster). A second variant works within 8–12 bpc and requires a few hundreds of microseconds per operation, that is, smaller than our first variant and still several times faster than Russo’s implementation. We remark again that those space figures include the storage of the sequence, and that 8 bpc is the storage space of a byte-based representation of the plain sequence (although 2 bpc is easily achieved on DNA).

Achieving those good practical results is not immediate, however. We show that a direct implementation of the techniques as described in the theoretical proposal [18] does not lead to the best performance. Instead, we propose a novel solution to the previous/next smaller value and range minimum queries, based on the range min-max tree (RMM tree), a recent data structure developed for succinct tree representations [22,23]. We adapt RMM trees to speed up the desired queries on sequences of LCP values.

The resulting representation not only performs better than a verbatim implementation of the theoretical proposal, but also has a great potential to handle highly repetitive sequence collections. Those collections, formed by many similar strings, arise in version control systems, periodic publications, and software repositories. They also arise naturally in bioinformatics, for example when sequencing the genomes of many individuals of the same or related species (two human genomes share 99.9% of their sequences, for example). It is likely that the largest genome collections that will emerge in the next years will be highly repetitive, and taking advantage of that repetitiveness will be the key to handle them.

Repetitiveness is not captured by statistical compression methods nor frequency-based entropy definitions [16,24] (i.e., the frequencies of symbols do not change much if we add near-copies of an initial sequence). Rather, we need repetition aware compression methods. Although this kind of compression is well-known (e.g., grammar-based and Ziv-Lempel-based compression), only recently there have appeared CSAs and other indexes that take advantage of repetitiveness [24,25,26,27]. Yet, those indexes do not support the full suffix tree functionality. On the other hand, none of the existing CSTs is tailored to repetitive text collections.

Our second contribution is to present the first, and the only to date, fully-functional compressed suffix tree whose compression effectiveness is related to the repetitiveness of the text collection. While its operations are much slower than most existing CSTs (requiring the order of milliseconds), the space required is also much lower on repetitive collections (1.4–1.9 bpc in our mildly repetitive test collections, and 0.6 bpc on a highly repetitive one). This can make the difference between fitting the collection in main memory or having to resort to disk.

The paper is organized as follows. Section 2 gives the basis of suffix array and tree compression in general and repetitive text collections, and puts our contribution in context. Section 3 compares various LCP representations and chooses suitable ones for our CST. Section 4 proposes the novel RMM-tree based solution for $\mathit{NSV}/\mathit{PSV}/\mathit{RMQ}$ operations and shows it is superior to a verbatim implementation of the theoretical proposal. Section 5 assembles our CST using the previous pieces, and Section 6 evaluates and compares it with alternative implementations. Section 7 extends the RMM concept to design a CST that adapts to repetitive collections, and Section 8 evaluates it. Finally, Section 9 concludes and discusses various new advances [21,28] that have been made on efficiently implementing the interval-based approach since the conference publication of our results [29,30].

2. Related Work and Our Contribution in Context

Our aim is to handle a collection of texts $T_1,T_2,\dots$ over an alphabet Σ of size σ. This is customarily represented as a single text $T=T_1\$T_2\$\dots$ concatenating all the texts in the collection. The symbol “$” is an endmarker that does not appear elsewhere. Such a representation simplifies the discussion on data structures, which can consider that a single text is handled.

2.1. Suffix Arrays and CSAs

A suffix array over a text $T[1,n]$ is an array $A[1,n]$ of the positions in T, lexicographically sorted by the suffix starting at the corresponding position of T. That is, $T\left[A\right[i],n]<T\left[A\right[i+1],n]$ for all $1\le i<n$. Note that every substring of T is the prefix of a suffix, and that all the suffixes starting with a given pattern P appear consecutively in A, hence a pair of binary searches find the area $A[sp,ep]$ containing all the positions where P occurs in T.

There are several compressed suffix arrays (CSAs) [31,32], which offer essentially the following functionality: (1) Given a pattern $P[1,m]$, find the interval $A[sp,ep]$ of the suffixes starting with P; (2) Obtain $A\left[i\right]$ given i; (3) Obtain $A^{-1}\left[j\right]$ given j. An important function the CSAs implement is $\Psi \left(i\right)=A^{-1}[\left(A\left[i\right]\mathrm{mod}n\right)+1]$ and its inverse, usually much faster than computing A and $A^{-1}$. This function lets us move virtually in the text, from the suffix i that points to text position $j=A\left[i\right]$, to the one pointing to $j+1=A[\Psi (i\left)\right]$. Function Ψ is essential to support suffix tree functionality.

Most CSAs are self-indexes, meaning that they can also extract any substring of T and thus T does not need to be stored separately. Generally, one can extract any $T[i,i+\ell ]$ using $s+\ell$ applications of Ψ, where s is a sampling parameter that involves spending $O\left(\right(n/s)logn)$ extra bits of space.

2.2. Suffix Trees and CSTs

A suffix trie is a trie (or digital tree) storing all the suffixes of T. This is a labeled tree where each text suffix is read in a root-to-leaf path, and the edges toward the children of a node are labeled by different characters. The concatenation of the string labels from the root up to a node v is called the path-label of v, $\pi \left(v\right)$. A suffix tree is obtained by “compacting” unary paths in a suffix trie, which means they are converted into a single edge labeled by the string that concatenates the involved character labels. Furthermore, a node v is converted into a leaf (and the rest of its descending unary path is eliminated) as soon as $\pi \left(v\right)$ becomes unique. Such leaf is annotated with the starting position i of the only occurrence of $\pi \left(v\right)$ in T, that is, suffix $T[i,n]$ starts with $\pi \left(v\right)$. If the children of each suffix tree node are ordered lexicographically by their string label, then the sequence of leaf annotations of the suffix tree is precisely the suffix array of T. Figure 1 illustrates a suffix tree and suffix array. Several navigation operations over the nodes and leaves of the suffix tree are of interest. Table 1 lists the most common ones.

Figure 1. The suffix tree of the text “alabar a la alabarda$”, where the “$” is a terminator symbol. The white space is written as an underscore for clarity, and it is lexicographically smaller than the characters “a”–“z”.

Figure 1. The suffix tree of the text “alabar a la alabarda$”, where the “$” is a terminator symbol. The white space is written as an underscore for clarity, and it is lexicographically smaller than the characters “a”–“z”.

Table 1. Main operations over the nodes and leaves of the suffix tree.

Operation	Description
Root()	the root of the suffix tree
Locate(v)	position i such that $\pi \left(v\right)$ starts at $T\left[i\right]$, for a leaf v
Ancestor($v,w$)	true if v is an ancestor of w
SDepth(v)	string-depth of v, i.e., $\left|\pi \right(v\left)\right|$
TDepth(v)	tree-depth of v, i.e., depth of node v in the suffix tree
Count(v)	number of leaves in the subtree rooted at v
Parent(v)	parent node of v
FChild(v)	alphabetically first child of v
NSibling(v)	alphabetically next sibling of v
SLink(v)	suffix-link of v, i.e., the node w s.th. $\pi \left(w\right)=\beta$ if $\pi \left(v\right)=a\beta$ for $a\in \Sigma$
SLink${}^i$(v)	iterated suffix-link, i.e., the node w s.th. $\pi \left(w\right)=\beta$ if $\pi \left(v\right)=\alpha \beta$ for $\alpha \in {\Sigma }^i$
LCA($v,w$)	lowest common ancestor of v and w
Child($v,a$)	node w s.th. the first letter on edge $(v,w)$ is $a\in \Sigma$
Letter($v,i$)	$ith$ letter of v’s path-label, $\pi \left(v\right)\left[i\right]$
LAQ${}_S$($v,d$)	the highest ancestor of v with string-depth $\ge d$
LAQ${}_T$($v,d$)	the ancestor of v with tree-depth d

Table 1. Main operations over the nodes and leaves of the suffix tree.

Operation	Description
Root()	the root of the suffix tree
Locate(v)	position i such that $\pi \left(v\right)$ starts at $T\left[i\right]$, for a leaf v
Ancestor($v,w$)	true if v is an ancestor of w
SDepth(v)	string-depth of v, i.e., $\left|\pi \right(v\left)\right|$
TDepth(v)	tree-depth of v, i.e., depth of node v in the suffix tree
Count(v)	number of leaves in the subtree rooted at v
Parent(v)	parent node of v
FChild(v)	alphabetically first child of v
NSibling(v)	alphabetically next sibling of v
SLink(v)	suffix-link of v, i.e., the node w s.th. $\pi \left(w\right)=\beta$ if $\pi \left(v\right)=a\beta$ for $a\in \Sigma$
SLink${}^i$(v)	iterated suffix-link, i.e., the node w s.th. $\pi \left(w\right)=\beta$ if $\pi \left(v\right)=\alpha \beta$ for $\alpha \in {\Sigma }^i$
LCA($v,w$)	lowest common ancestor of v and w
Child($v,a$)	node w s.th. the first letter on edge $(v,w)$ is $a\in \Sigma$
Letter($v,i$)	$ith$ letter of v’s path-label, $\pi \left(v\right)\left[i\right]$
LAQ${}_S$($v,d$)	the highest ancestor of v with string-depth $\ge d$
LAQ${}_T$($v,d$)	the ancestor of v with tree-depth d

The suffix array alone is insufficient to efficiently emulate all the relevant suffix tree operations. To recover the full suffix tree functionality, we need two extra pieces of information: (1) The tree topology; (2) The longest common prefix (LCP) information, that is, $\mathit{LCP}\left[i\right]$ is the length of the longest common prefix between $T\left[A\right[i-1],n]$ and $T\left[A\right[i],n]$ for $i>1$ and $\mathit{LCP}\left[1\right]=0$ (or, seen another way, $\mathit{LCP}\left[i\right]$ is the length of the string labeling the path from the root to the lowest common ancestor node of the ith and $(i-1)$th suffix tree leaves). Indeed, the suffix tree topology can be implicit if we identify each suffix tree node with the suffix array interval containing the leaves that descend from it. This range uniquely identifies the node because there are no unary nodes in a suffix tree.

Consequently, a compressed suffix tree (CST) is obtained by enriching the CSA with some extra data. Sadakane [11] added the topology of the tree (using $4n$ extra bits) and the LCP data. The LCP data was compressed to $2n$ bits by noticing that, if sorted by text order rather than suffix array order, the LCP numbers decrease by at most 1: Let $\mathit{PLCP}$ be the permuted $\mathit{LCP}$ array, then $\mathit{PLCP}[j+1]\ge \mathit{PLCP}\left[j\right]-1$. Thus the numbers can be differentially encoded, $h[j+1]=\mathit{PLCP}[j+1]-\mathit{PLCP}\left[j\right]+1\ge 0$, and then represented in unary over a bitmap $H[1,2n]=0^{h\left[1\right]}{10}^{h\left[2\right]}\dots {10}^{h\left[n\right]}1$. Then, to obtain $\mathit{LCP}\left[i\right]$, we look for $\mathit{PLCP}\left[A\right[i\left]\right]$, and this is extracted from H via rank/select operations. Here $ran{k}_b(H,i)$ counts the number of bits b in $H[1,i]$ and $selec{t}_b(H,i)$ is the position of the i-th b in H. Both can be answered in constant time using $o\left(n\right)$ extra bits of space [33]. Then $\mathit{PLCP}\left[j\right]=selec{t}_1(H,j)-2j$, assuming $\mathit{PLCP}\left[0\right]=0$.

Russo et al. [14] get rid of the parentheses, by instead identifying suffix tree nodes with their corresponding suffix array interval. By sampling some suffix tree nodes, most operations can be carried out by moving, using suffix links, towards a sampled node, finding the information stored in there, and transforming it as we move back to the original node. The suffix link operation, defined in Table 1, can be computed using Ψ and the lowest common ancestor operation [11].

2.3. Re-Pair and Repetition-Aware CSAs

Re-Pair [34] is a grammar-based compression method that factors out repetitions in a sequence. It is based on the following heuristic: (1) Find the most repeated pair $ab$ in the sequence; (2) Replace all its occurrences by a new symbol s; (3) Add a rule $s\to ab$ to a dictionary R; (4) Iterate until every pair is unique.

The result of the compression of a text T, over an alphabet Σ of size σ, is the dictionary R and the remaining sequence C, containing new symbols (s) and symbols in Σ. Every sub-sequence of C can be decompressed locally by the following procedure: Check if $C\left[i\right]<\sigma$; if so the symbol is original, else look in R for rule $C\left[i\right]\to ab$, and recursively continue expanding with the same steps.

The dictionary R corresponds to a context-free grammar, and the sequence C to the initial symbols of the derivation tree that represents T. The final structure can be regarded as a sequence of binary trees with roots $C\left[i\right]$.

González and Navarro [35] used Re-Pair to compress the differentially encoded suffix array, $A^{\prime }\left[i\right]=A\left[i\right]-A[i-1]$. They showed that Re-Pair achieves $\left|R\right|+\left|C\right|=O(rlog\frac{n}{r})$ on $A^{\prime }$, r being the number of runs in Ψ. A run in Ψ is a maximal contiguous area where $\Psi (i+1)=\Psi \left(i\right)+1$. It was shown that the number of runs in Ψ is $r\le n{H}_k+{\sigma }^k$ for any k [36]. More importantly, repetitions in T induce long runs in Ψ, and hence a smaller r [25]. An exact bound has been elusive, but Mäkinen et al. [25] gave an average-case upper bound for r: If T is formed by a random base sequence of length $n^{\prime }\ll n$ and then other sequences that have m random mutations (which include indels, replacements, block moves, etc.) with respect to the base sequence, then r is at most $n^{\prime }$ + $O\left(m{log}_{\sigma }n\right)$ on average.

The RLCSA [25] is a CSA where those runs in Ψ are factored out, to achieve $O\left(r\right)$ cells of space. More precisely, the size of the RLCSA is $r(2log(n/r)+log\sigma )(1+o(1\left)\right)$ bits. It supports accesses to A in time $O(slogn)$, with $O\left(\right(n/s)logn)$ extra bits for a sampling of A.

2.4. An Interval-Based CST

Fischer et al. [18] prove that bitmap H in Sadakane’s CST is compressible as it has at most $2r$ runs of 0’s or 1’s, where r is the number of runs in Ψ as before.

Let $z_1,z_2,\dots ,z_r$ be the lengths of the runs of 0’s and $o_1,o_2,\dots ,o_r$ be the lengths of the runs of 1’s. Fischer et al. [18] create arrays $Z={10}^{z_1-1}{10}^{z_2-1}\dots$ and $O={10}^{o_1-1}{10}^{o_2-1}\dots$, with overall $2r$ 1’s out of $2n$, and thus can be compressed to $2rlog\frac{n}{r}+O\left(r\right)+o\left(n\right)$ bits while supporting constant-time rank and select [37]. When r is very small it is better to use other bitmap representations (e.g., [38]) requiring $2rlog\frac{n}{r}+O\left(r\right)$ bits, even if they do not offer constant times for rank.

Their other improvement over Sadakane’s CST is to get rid of the tree topology and replace it with suffix array ranges. Fischer et al. show that all the navigation can be simulated by means of three operations: (1) The range minimum query $\mathit{RMQ}(i,j)$ gives the position of the minimum in $\mathit{LCP}[i,j]$; (2) The previous smaller value $\mathit{PSV}\left(i\right)$ finds the last value smaller than $\mathit{LCP}\left[i\right]$ in $\mathit{LCP}[1,i-1]$; and (3) The next smaller value $\mathit{NSV}\left(i\right)$ finds the first value smaller than $\mathit{LCP}\left[i\right]$ in $\mathit{LCP}[i+1,n]$. As examples, the parent of node $[i,j]$ can be computed as $\left[\mathit{PSV}\right(i),\mathit{NSV}(i)-1]$; the LCA between nodes $[i,j]$ and $[i^{\prime },j^{\prime }]$ is $\left[\mathit{PSV}\right(p),\mathit{NSV}(p)-1]$, where $p=\mathit{RMQ}(min(i,i^{\prime }),$ $max(j,j^{\prime }))$; and the suffix link of $[i,j]$ is $\left[\mathit{PSV}\right(\Psi \left(i\right)),\mathit{NSV}(\Psi \left(j\right))-1]$.

The three primitives could easily be solved in constant time using $O\left(n\right)$ extra bits of space on top of the $\mathit{LCP}$ representation [18] (more recently Ohlebusch et al. [28] showed how to solve them in constant time using $3n+o\left(n\right)$ bits), but Fischer et al. give sublogarithmic-time algorithms to solve them with only $o\left(n\right)$ extra bits.

A final observation of interest in that article [18] is that the repetitions found in a differential encoding of the suffix array (i.e., the runs in Ψ) also show up in the differential $\mathit{LCP}$, since if A values differ by 1 in a range, the $\mathit{LCP}$ areas must also differ by 1. Therefore, Re-Pair compression of the differential $\mathit{LCP}$ should perform similarly as González and Navarro’s suffix array compression [35].

2.5. Our Contribution

In this paper we design a practical and efficient CST building on the ideas of Fischer et al. [18], and show that its space/time performance is attractive. This challenge can be divided into (1) How to represent the LCP array efficiently in practice; and (2) How to compute efficiently $\mathit{RMQ}$, $\mathit{PSV}$, and $\mathit{NSV}$ over this LCP representation. For the first sub-problem we compare various implementations, whereas for the second we adapt a data structure called range min-max tree [22], which was designed for another problem. We compare the resulting CST with previous ones and show that it offers relevant space/time tradeoffs. Finally, we design a variant of the range min-max tree that is suitable for highly repetitive collections (i.e., with low r value). This is obtained by replacing this regular tree by the (truncated) grammar tree of the Re-Pair compression of the differential LCP array. The resulting CST is the only one handling repetitive collections within space below 2 bpc.

3. Representing Array $\mathit{LCP}$

The following alternatives were considered to represent $\mathit{LCP}$:

Sad-Gon Encodes Sadakane’s [11] H bitmap in plain form, using the rank/select implementation of González [39], which takes $0.1n$ bits on top of the $2n$ used by H itself. This implementation answers rank in constant time and select in $O(logn)$ time via binary search.

Sad-OS Like the previous one, but using the dense array implementation of Okanohara and Sadakane [38] for H. This requires about the same space as the previous one and answers select in time $O({log}^{4}r/logn)$.

FMN-RRR Encodes H in compressed form as in Fischer et al. [18], that is, by encoding sparse bitmaps Z and O. We use the compressed representation by Raman et al. [37] as implemented by Claude [40]. This costs $0.54n$ extra bits on top of the entropy of the two bitmaps, $2rlog\frac{n}{r}+O\left(r\right)$. Operation rank takes constant time and select takes $O(logn)$ time.

FMN-OS Like the previous one, but instead of Raman et al.’s technique, we use the sparse array implementation by Okanohara and Sadakane [38]. This requires $2rlog\frac{n}{r}+O\left(r\right)$ bits and solves select in time $O({log}^{4}r/logn)$.

PT Inspired in an LCP construction algorithm [41], we store a particular sampling of $\mathit{LCP}$ values, and compute the others using the sampled ones. Given a parameter v, the sampling requires $n+O(n/\sqrt{v}+v)$ bytes of space and computes any $\mathit{LCP}\left[i\right]$ by comparing at most some $T[j,j+v]$ and $T[j^{\prime },j^{\prime }+v]$. As we must obtain these symbols using Ψ up to $2v$ times, the idea is slow.

PhiSpare This is inspired in another construction [42]. For a parameter q, we store in text order an array ${\mathit{PLCP}}_q$ with the $\mathit{LCP}$ values for all text positions $q·k$. Now assume $A\left[i\right]=qk+b$, with $0\le b<k$. If $b=0$, then $\mathit{LCP}\left[i\right]={\mathit{PLCP}}_q\left[k\right]$. Otherwise, $\mathit{LCP}\left[i\right]$ is computed by comparing at most $q+{\mathit{PLCP}}_q[k+1]-{\mathit{PLCP}}_q\left[k\right]$ symbols of the suffixes $T\left[A\right[i-1],n]$ and $T\left[A\right[i],n]$. The space is $n/q$ integers and the computation requires $O\left(q\right)$ applications of Ψ on average.

DAC The directly addressable codes of Ladra et al. [43]. Most $\mathit{LCP}$ values are small ($O\left({log}_{\sigma }n\right)$ on average), and thus require few bits. Yet, some can be much larger. Thus we can fix a block length b and divide each number of ℓ bits into $\lceil \ell /b\rceil$ blocks of b bits. Each block is stored using $b+1$ bits, the last one telling whether the number continues in the next block or finishes in the current one. Those blocks are then rearranged to allow for fast random access. There are two variants of this structure, both implemented by Ladra: One with fixed b ($\mathit{DAC}$), and another using different b values for the first, second, etc. blocks, so as to minimize the total space ($\mathit{DAC}-\mathit{Var}$). Note we represent $\mathit{LCP}$ and not $\mathit{PLCP}$, thus we do not need to compute $A\left[i\right]$.

RPRe-Pair As mentioned, Re-Pair can be used to compress the differential $\mathit{LCP}$ array, ${\mathit{LCP}}^{\prime }$ [18]. To obtain $\mathit{LCP}\left[i\right]$ we store sampled absolute $\mathit{LCP}$ values and decompress the nonterminals since the last sample.

3.1. Experimental Comparison

Our computer is an Intel Core2 Duo at $3.16$ GHz, with 8 GB of RAM and 6 MB cache, running Linux version $2.6.24$-24. Table 2 lists the collections used for this experiment. They were obtained from the Pizza & Chili site [44]. We also give some information on their LCP values and number of runs in Ψ, which affects their compressibility. We tested the different LCP representations by accessing 100,000 random positions of the $\mathit{LCP}$ array. Figure 2 (left) shows the space/times achieved on the four texts. Only $PT$ and PhiSpare display a space/time tradeoff; in the first we use $v=4,6,8$ and for the second $q=16,32,64$. Because in various cases we need to access a sequence of consecutive LCP values, we show in Figure 2 (right) the time per cell when accessing 32 consecutive cells. The plots also show solution Naive, which stores LCP values using the number of bits required by the maximum value in the array.

Table 2. Data files used for tests with their size in MB, plus some information on their compressibility.

Collection	Size	Description	Avg LCP	Max LCP	Runs ($r/n$)
dna	100	DNA sequences from Gutenberg Project	$28.1$	$17,772$	0.63
xml	100	XML from dblp.uni-trier.de	$44.5$	1084	0.14
proteins	100	Protein sequences from the Swissprot database	$220.6$	$35,246$	0.59
sources	100	Source code obtained by concatenating files of the Linux-2.6.11.6 and gcc-4.0.0 distributions	$625.1$	$307,871$	0.23

Table 2. Data files used for tests with their size in MB, plus some information on their compressibility.

Collection	Size	Description	Avg LCP	Max LCP	Runs ($r/n$)
dna	100	DNA sequences from Gutenberg Project	$28.1$	$17,772$	0.63
xml	100	XML from dblp.uni-trier.de	$44.5$	1084	0.14
proteins	100	Protein sequences from the Swissprot database	$220.6$	$35,246$	0.59
sources	100	Source code obtained by concatenating files of the Linux-2.6.11.6 and gcc-4.0.0 distributions	$625.1$	$307,871$	0.23

Figure 2. Space/Time for accessing array $\mathit{LCP}$. On the left for random accesses and on the right for sequential accesses.

Figure 2. Space/Time for accessing array $\mathit{LCP}$. On the left for random accesses and on the right for sequential accesses.

We use Sadakane’s CSA implementation [12], available at Pizza & Chili, as our CSA, with sampling $s=16$. This is relevant because various LCP implementations need to compute $A\left[i\right]$ from the CSA.

A first observation is that Fischer et al.’s compression techniques for bitmap H do not compress significantly in practice (on non-repetitive collections). The value of r is not small enough to make the compressed representations noticeably smaller (and at times their space overhead over the entropy makes them larger, especially variant $\mathit{FMN}-\mathit{OS}$).

These explicit representations of H require only $2.1n$ bits of space and access $\mathit{LCP}$ in about 10 microseconds. Technique PT is always dominated by them and PhiSpare can achieve less space, but at the price of an unacceptable 10-fold increase in time.

The other dominant technique is $\mathit{DAC}$/$\mathit{DAC}-\mathit{Var}$, which requires significantly more space ($6n-8n$ bits) but can access $\mathit{LCP}$ within 0.1–0.2 microseconds. This is because it does not need to compute $A\left[i\right]$ to find $\mathit{LCP}\left[i\right]$. Its time is even competitive with Naive, while using much less space. Technique $\mathit{RP}$, instead, does not perform well, doing even worse than Naive in time and space. This shows, again, that (in non-repetitive) collections the value r is not small enough: While the length of the Re-Pair compressed sequence is 30%–60% of the original one, the values require more bits than in Naive because Re-Pair creates many new symbols.

$\mathit{DAC}$, $\mathit{DAC}-\mathit{Var}$ and Naive are the only techniques that benefit from extracting consecutive values, so the former stay comparable with Naive in time even in this case. This owes to the better cache usage compared with the other representations, which must access spread text positions to decode a contiguous $\mathit{LCP}$ area.

For the sequel we will keep only $\mathit{DAC}$ and $\mathit{DAC}-\mathit{Var}$, which give the best time performance, and $\mathit{FMN}-\mathit{RRR}$ and $\mathit{Sad}-\mathit{Gon}$, which have the most robust performance at representing H.

4. Computing $\mathit{RMQ}$, $\mathit{PSV}$, and $\mathit{NSV}$

Once a representation for $\mathit{LCP}$ is chosen, one must carry out operations $\mathit{RMQ}$, $\mathit{PSV}$, and $\mathit{NSV}$ on top of it (as they require to access $\mathit{LCP}$). We first implemented verbatim the theoretical proposals of Fischer et al. [18]. For $\mathit{NSV}$, the idea is akin to the recursive findclose solution for compressed trees [45]: The array is divided into blocks and some values are chosen as pioneers so that, if a position is not a pioneer, then its $\mathit{NSV}$ answer is in the same block of that of its preceding pioneer (and thus it can be found by scanning that block). Pioneers are marked in a bitmap so as to map them to a reduced array of pioneers, where the problem is recursively solved. We experimentally verified that it is convenient to continue the recursion until the end instead of storing the explicit answers at some point. The block length L yields a space/time tradeoff since, at each level of the recursion, we must obtain $O\left(L\right)$ values from $\mathit{LCP}$. $\mathit{PSV}$ is symmetric, needing another similar structure.

For $\mathit{RMQ}$ we apply a recent implementation [46,47] on the LCP array, which does not need to access $\mathit{LCP}$ yet requires $2.44n$ bits. In the actual theoretical proposal [18] this space is reduced to $o\left(n\right)$ bits, but many accesses to $\mathit{LCP}$ are necessary; we did not implement that idea verbatim as it has little chances of being practical.

The final data structure, which we call $\mathit{FMN}-\mathit{NPR}$, is composed of the structure to answer $\mathit{NSV}$ plus the one for $\mathit{PSV}$ plus the structure to calculate $\mathit{RMQ}$.

4.1. A Novel Practical Solution

We propose now a different solution, inspired in Sadakane and Navarro’s range min-max (RMM) tree data structure [22]. We divide $\mathit{LCP}$ into blocks of length L. Now we form a hierarchy of blocks, where we store the minimum $\mathit{LCP}$ value of each block i in an array $m\left[i\right]$. The array uses $\frac{n}{L}logn$ bits. On top of array m, we construct a perfect L-$ary$ tree $T_m$ where the leaves are the elements of m and each internal node stores the minimum of the values stored in its children. The total space for $T_m$ is $\frac{n}{L}logn(1+O(1/L))$ bits, so if $L=\omega (logn)$, the space used is $o\left(n\right)$ bits.

To answer $\mathit{NSV}\left(i\right)$, we look for the first $j>i$ such that $\mathit{LCP}\left[j\right]<p=\mathit{LCP}\left[i\right]$, using $T_m$ to find it in time $O(Llog(n/L\left)\right)$. We first search sequentially for the answer in the same block of i. If it is not there, we go up to the leaf that represents the block and search the right siblings of this leaf. If some of these sibling leaves contain a minimum value smaller than p, then the answer to $\mathit{NSV}\left(i\right)$ is within their block, so we go down to their block and find sequentially the leftmost position j where $\mathit{LCP}\left[j\right]<p$. If, however, no sibling of the leaf contains a minimum smaller than p, we continue going up the tree and consider the right siblings of the parent of the current node. At some node we find a minimum smaller than p and start traversing down the tree as before, finding at each level the first child of the current node with a minimum smaller than p. $\mathit{PSV}$ is symmetric. As the minima in $T_m$ are explicitly stored, the heaviest part of the cost in practice is the $O\left(L\right)$ accesses to $\mathit{LCP}$ cells at the lowest levels.

To calculate $\mathit{RMQ}(x,y)$ we use the same $T_m$ and separate the search in three parts: (a) We calculate sequentially the minimum value in the interval $[x,L\lceil \frac{x}{L}\rceil -1]$ and its leftmost position in the interval; (b) We do the same for the interval $[L\lfloor \frac{y}{L}\rfloor ,y]$; (c) We calculate $\mathit{RMQ}(L\lceil \frac{x}{L}\rceil ,L\lfloor \frac{y}{L}\rfloor -1)$ using $T_m$. Finally we compare the results obtained in (a), (b) and (c) and the answer will be the one holding the minimum value, choosing the leftmost to break ties. For each node in $T_m$ we also store the local position in the children where the minimum occurs, so we do not need to scan the child blocks when we go down the tree. The extra space incurred is just $\frac{n}{L}logL(1+O(1/L))$ bits. The final data structure, if $L=\omega (logn)$, requires $o\left(n\right)$ bits and can compute $\mathit{NSV}$, $\mathit{PSV}$ and $\mathit{RMQ}$ all using the same auxiliary structure. We call it $\mathit{RMM}-\mathit{NPR}$.

4.2. Experimental Comparison

We tested the performance of the different $\mathit{NPR}$ implementations by performing 100,000 $\mathit{NSV}$ and $\mathit{RMQ}$ queries at random positions in the $\mathit{LCP}$ array. Figure 3 shows the space/time achieved for each implementation on dna and proteins (the others texts gave very similar results). We consider the four selected LCP representations, which affect the performance because the algorithms have to access the array. The space we plot is additional to that to store the $\mathit{LCP}$ array. We obtained space/time tradeoffs by using different block sizes $L=8,16,32$. Note that $\mathit{RMQ}$ on $\mathit{FMN}-\mathit{RMQ}$ does not access $\mathit{LCP}$, so the value of L does not affect it.

Figure 3. Space/Time for the operations $\mathit{NSV}$ and $\mathit{RMQ}$. Times for $\mathit{PSV}$ are identical to those for $\mathit{NSV}$.

Figure 3. Space/Time for the operations $\mathit{NSV}$ and $\mathit{RMQ}$. Times for $\mathit{PSV}$ are identical to those for $\mathit{NSV}$.

First, it can be seen that $\mathit{RMM}-\mathit{NPR}$ performs well using much less space than $\mathit{FMN}-\mathit{NPR}$. In addition, solving $\mathit{NSV}$ (and thus $\mathit{PSV}$) with $\mathit{RMM}-\mathit{NPR}$ structure is significantly faster than with $\mathit{FMN}-\mathit{NPR}$. This holds under all the $\mathit{LCP}$ representations, regardless that times are one order of magnitude higher with representations $\mathit{Sad}-\mathit{Gon}$ and $\mathit{FMN}-\mathit{RRR}$.

On the other hand, $\mathit{RMQ}$ is way faster on $\mathit{FMN}$ because it does not need to access $\mathit{LCP}$ at all. It is 2–3 times faster than $\mathit{RMM}$ using $\mathit{DAC}$ or $\mathit{DAC}-\mathit{Var}$ and two orders of magnitude faster than $\mathit{RMM}$ using $\mathit{Sad}-\mathit{Gon}$ or $\mathit{FMN}-\mathit{RRR}$. This operation, however, is far less common than $\mathit{NSV}$ and $\mathit{PSV}$ when implementing the CST operations, so its impact is not so high. Another reason to prefer $\mathit{RMM}-\mathit{NPR}$ is that it can support a generalized version of $\mathit{NSV}$ and $\mathit{PSV}$, which allows us to solve operation ${\mathit{LAQ}}_T$ on suffix trees without adding more memory, as opposed to $\mathit{FMN}-\mathit{NPR}$. In the next section we show how a fully-functional CST can be implemented on top of the $\mathit{RMM}-\mathit{NPR}$ representation.

5. Our Compressed Suffix Tree

Our CST implementation applies our $\mathit{RMM}-\mathit{NPR}$ algorithms of Section 4 on top of some $\mathit{LCP}$ representation from those chosen in Section 3. This solves most of the tree traversal operations by using the formulas provided by Fischer et al. [18], which we do not repeat here. In some cases, however, we have deviated from the theoretical algorithms for practical considerations.

TDepth: We proceed by brute force using Parent, as there is no practical solution in the theoretical proposal.

NSibling: There is a bug in the original formula [18] in the case v is the next-to-last child of its parent. According to them, $\mathit{NSibling}\left([v_l,v_r]\right)$ first obtains its parent $[w_l,w_r]$, then checks whether $v_r=w_r$ (in which case there is no next sibling), then checks whether $w_r=v_r+1$ (in which case the next sibling is leaf $[w_r,w_r]$), and finally answers $[v_r+1,z-1]$, where $z=\mathit{RMQ}(v_r+2,w_r)$. This $\mathit{RMQ}$ is aimed at finding the end of the next sibling of the next sibling, but it fails if we are near the end. Instead, we replace it by the faster $z={\mathit{NSV}}^{\prime }(v_r+1,\mathit{LCP}[v_r+1])$. ${\mathit{NSV}}^{\prime }(i,d)$ generalizes $\mathit{NSV}$ by finding the next value smaller or equal to d, and is implemented almost like $\mathit{NSV}$ using $T_m$.

Child: The children are ordered by letter. We need to extract the children sequentially using $\mathit{FChild}$ and $\mathit{NSibling}$, to find the one descending by the correct letter, yet extracting the $\mathit{Letter}$ of each is expensive. Thus we first find all the children sequentially and then binary search the correct letter among them, thus reducing the use of $\mathit{Letter}$ as much as possible.

LAQ${}_S(v,d)$: Instead of the slow complex formula given in the original paper, we use ${\mathit{NSV}}^{\prime }$ (and ${\mathit{PSV}}^{\prime }$): ${\mathit{LAQ}}_S([v_l,v_r],d)=[{\mathit{PSV}}^{\prime }(v_l+1,d),{\mathit{NSV}}^{\prime }(v_r,d)-1]$. This is a complex operation we are supporting with extreme simplicity.

LAQ${}_T(v,d)$: There is no practical solution in the original proposal. We proceed as follows to achieve the cost of dParent operations, plus some ${\mathit{LAQ}}_S$ ones, all of which are reasonably cheap. Since $\mathit{SDepth}\left(v\right)\ge \mathit{TDepth}\left(v\right)$, we first try $v^{\prime }={\mathit{LAQ}}_S(v,d)$, which is an ancestor of our answer; let $d^{\prime }=\mathit{TDepth}\left(v^{\prime }\right)$. If $d^{\prime }=d$ we are done; else $d^{\prime }<d$ and we try $v^{\prime \prime }={\mathit{LAQ}}_S(v,d+(d-d^{\prime }))$. We compute $d^{\prime \prime }=\mathit{TDepth}\left(v^{\prime \prime }\right)$ (which is measured by using $d^{\prime \prime }-d^{\prime }$ $\mathit{Parent}$ operations until reaching $v^{\prime }$) and iterate until finding the right node.

Table 3 gives a space breakdown for our CST. We give the space in bpc of Sadakane’s CSA, the 4 alternatives we consider for the LCP representation, and the space of our RMM tree (using $L=32$ for a “slow” variant and $L=16$ for a “fast” variant). The last column gives the total bpc considering the smallest “slow” (using $\mathit{Sad}-\mathit{Gon}$ or $\mathit{FMN}-\mathit{RRR}$ for $\mathit{LCP}$) and the smallest “fast” (using $\mathit{DAC}$ or $\mathit{DAC}-\mathit{Var}$) alternatives.

Table 3. Space breakdown of our compressed suffix tree.

Collection	CSA bpc	LCP bpc				RMM bpc		Total bpc
		${Sad}-{Gon}$	${FMN}-{RRR}$	${DAC}$	${DAC}-{Var}$	Slow	Fast	Slow	Fast
dna	$5.88$	$2.10$	$3.06$	$6.29$	$5.79$	1.23	$2.47$	$9.21$	$14.14$
xml	$4.47$	$2.10$	$2.03$	$9.30$	$7.77$	1.23	$2.47$	$7.73$	$14.71$
proteins	$7.91$	$2.10$	$2.59$	$7.43$	$6.97$	1.23	$2.47$	$11.24$	$17.35$
sources	$5.20$	$2.10$	$2.29$	$8.23$	$7.50$	1.23	$2.47$	$8.53$	$15.17$

Table 3. Space breakdown of our compressed suffix tree.

Collection	CSA bpc	LCP bpc				RMM bpc		Total bpc
		${Sad}-{Gon}$	${FMN}-{RRR}$	${DAC}$	${DAC}-{Var}$	Slow	Fast	Slow	Fast
dna	$5.88$	$2.10$	$3.06$	$6.29$	$5.79$	1.23	$2.47$	$9.21$	$14.14$
xml	$4.47$	$2.10$	$2.03$	$9.30$	$7.77$	1.23	$2.47$	$7.73$	$14.71$
proteins	$7.91$	$2.10$	$2.59$	$7.43$	$6.97$	1.23	$2.47$	$11.24$	$17.35$
sources	$5.20$	$2.10$	$2.29$	$8.23$	$7.50$	1.23	$2.47$	$8.53$	$15.17$

6. Comparing the CST Implementations

We compare the following CST implementations: Välimäki et al.’s [20] implementation of Sadakane’s compressed suffix tree [11] (CST-Sadakane); Russo’s implementation of Russo et al.’s “fully-compressed” suffix tree [14] (FCST); and our best variants. These are called Our CST in the plots. Depending on their $\mathit{LCP}$ representation, they are suffixed with $\mathit{Sad}-\mathit{Gon}$, $\mathit{FMN}-\mathit{RRR}$, $\mathit{DAC}$, and $\mathit{DAC}-\mathit{Var}$. We do not compare some operations like Root and Ancestor because they are trivial in all the implementations; Locate and Count because they depend only on the underlying CSA (which is mostly orthogonal, thus Letter is sufficient to study it); SLink ${}^i$ because it is usually better to do SLink i times; and ${\mathit{LAQ}}_S$ and ${\mathit{LAQ}}_T$ because they are not implemented in the alternative CSTs (these two are shown only for ours).

We typically show space/time tradeoffs for all the structures, where the space is measured in bpc (recall that these CSTs replace the text, so this is the overall space required). The times are averaged over a number of queries on random nodes. We use four types of node samplings, which make sense in different typical suffix tree traversal scenarios: (a) Collecting the nodes visited over 10,000 traversals from a random leaf to the root (used for Parent, SDepth, and Child operations); (b) Same but keeping only nodes with at least 5 children (for Letter); (c) Collecting the nodes visited over 10,000 traversals from the parent of a random leaf towards the root via suffix links (used for SLink and TDepth); and (d) Taking 10,000 random leaf pairs (for LCA). The standard deviation divided by the average is in the range [0.21, 2.56] for CST-Sadakane, [0.97, 2.68] for FCST, [0.65, 1.78] for Our CST Sad-Gon, [0.64, 2.50] for Our CST $\mathit{FMN}-\mathit{RRR}$, [0.59, 0.75] for Our CST DAC, and [0.63, 0.91] for Our CST $\mathit{DAC}-\mathit{Var}$. The standard deviation of the estimator is thus at most 1/100th of that.

Parent and TDepth. Figure 4 shows the performance of operations Parent and TDepth. As can be seen, CST-Sadakane is about 5 to 10 times faster than our best results for Parent and 100 times faster for TDepth. This is not surprising given that CST-Sadakane stores the topology explicitly and thus these operations are among the easiest ones. In addition, our implementation computes TDepth by brute force. Note, on the other hand, that FCST is about 10 times slower than our slowest implementation.

Figure 4. Space/Time trade-off performance for operations Parent and TDepth. Note the log scale.

Figure 4. Space/Time trade-off performance for operations Parent and TDepth. Note the log scale.

SLink, LCA, and SDepth. Figure 5 shows the performance of operations SLink and LCA, which are the ones most specific of suffix trees. Figure 6 (left) shows operation SDepth. Those operations happen to be among the most natural ones in Russo’s FCST, which displays a better performance compared with the previous ones. CST-Sadakane, instead, is not anymore the fastest. Indeed, our implementations based on $\mathit{DAC}$ and $\mathit{DAC}-\mathit{Var}$ are by far the fastest ones for these operations, 10 times faster than CST-Sadakane and 100 to 1000 times faster than FCST. Even our slower implementations are way faster than FCST and close to CST-Sadakane times.

Figure 5. Space/Time trade-off performance for operations SLink and LCA. Note the log scale.

Figure 5. Space/Time trade-off performance for operations SLink and LCA. Note the log scale.

Child. Figure 6 (right) shows operation Child, where we descend by a random child from the current node. Our times are significantly higher than for other operations, as expected, and the same happens to CST-Sadakane, which becomes comparable with our “large and fast” variants. FCST, on the other hand, is not much affected and becomes comparable with our “small and slow” variant. We note that, unlike other operations, the differences in performance depend markedly on the type of text.

Figure 6. Space/Time trade-off performance for operations SDepth and Child. Note the log scale.

Figure 6. Space/Time trade-off performance for operations SDepth and Child. Note the log scale.

Letter. Figure 7 (left) shows operation Letter $(v,i)$, as a function of i. This operation depends only on the CSA structure, and requires either applying $i-1$ times Ψ, or applying once A and $A^{-1}$. The former choice is preferred for FCST and the latter in CST-Sadakane. For our CST, using Ψ iteratively was better for these i values, as the alternative takes around 70 microseconds (recall we use Sadakane’s CSA [12]).

Figure 7. Space/Time trade-off performance for operation Letter and for a full tree traversal. Note the log scale.

Figure 7. Space/Time trade-off performance for operation Letter and for a full tree traversal. Note the log scale.

A full traversal. Figure 7 (right) shows a basic suffix tree traversal algorithm: the classical one to detect the longest repetition in a text. This traverses all of the internal nodes using FChild and NSibling and reports the maximum SDepth. Although CST-Sadakane takes advantage of locality, our “large and fast” variants are better while using half the space. Our “small and slow” variant, instead, requires a few hundred microseconds, as expected, yet FCST has a special implementation for full traversals and it is competitive with our slow variant.

LAQ${}_S$ and LAQ${}_T$. Figure 8 shows the performance of the operations ${\mathit{LAQ}}_S(v,d)$ and ${\mathit{LAQ}}_T(v,d)$. The times are presented as a function of parameter d, where we use $d=4,8,16,32,64$. We query the nodes visited over 10,000 traversals from a random leaf to the root (excluding the root). As expected, the performance of ${\mathit{LAQ}}_S$ is similar to that of Parent, and the performance of ${\mathit{LAQ}}_T$ is close to that of doing Parent d times. Note that, as we increase the value of d, the times tend to a constant. This is because, as we increase d, a greater number of queried nodes are themselves the answer to ${\mathit{LAQ}}_S$ or ${\mathit{LAQ}}_T$ queries.

Figure 8. Space/Time trade-off performance for operation ${\mathit{LAQ}}_S\left(d\right)$ and ${\mathit{LAQ}}_T\left(d\right)$. Note the log scale.

Figure 8. Space/Time trade-off performance for operation ${\mathit{LAQ}}_S\left(d\right)$ and ${\mathit{LAQ}}_T\left(d\right)$. Note the log scale.

Discussion. The general conclusion is that our CST implementation does offer a relevant tradeoff between the two rather extreme existing variants. Our CSTs can operate within 8–12 bpc (that is, at most 50% larger than the plain byte-based representation of the text, and replacing it) while requiring a few hundred microseconds for most operations (the “small and slow” variants $\mathit{Sad}-\mathit{Gon}$ and $\mathit{FMN}-\mathit{RRR}$); or within 13–16 bpc and carrying out most operations within a few microseconds (the “large and fast” variants $\mathit{DAC}$/$\mathit{DAC}-\mathit{Var}$). In contrast, FCST requires only 4–6 bpc (which is, remarkably, as little as half the space required by the plain text representation), but takes the order of milliseconds per operation; and CST-Sadakane takes usually a few tens of microseconds per operation but requires 25–35 bpc, which is close to uncompressed suffix arrays (not to uncompressed suffix trees, though).

We remark that, for many operations, our “fast and large” variant takes half the space of CST-Sadakane and is many times faster. Exceptions are Parent and TDepth, where CST-Sadakane stores the explicit tree topology, and thus takes a fraction of a microsecond. On the other hand, our CST carries out ${\mathit{LAQ}}_S$ in the same time of Parent, whereas this is much more complicated for the alternatives (they do not even implement it). For Child, where we descend by a random letter from the current node, the times are higher than for other operations, as expected, yet the same happens to all the implementations. We note that FCST is more efficient on operations $\mathit{LCA}$ and SDepth, which are its kernel operations, yet it is still slower than our “small and slow” variant. Finally, TDepth is an operation where all but Sadakane’s CST are relatively slow, yet on most suffix tree algorithms the string depth is much more relevant than the tree depth. Our ${\mathit{LAQ}}_T(v,d)$ costs about d times the time of our TDepth.

7. A Repetition-Aware CST

We now develop a variant of our $\mathit{RMM}$ representation that is suitable for highly repetitive text collections, and upgrade it to a fully-functional CST for this case. Recall that we need three components: A CSA, an LCP representation, and fast $\mathit{PSV}/\mathit{NSV}/\mathit{RMQ}$ queries on that $\mathit{LCP}$ sequence.

We use the RLCSA [25] as the base CSA of our repetition-aware CST. We also use the compressed representation of $\mathit{PLCP}$ (i.e., bitmap H) [18]. Since now we assume $r\ll n$, we use a compressed bitmap representation that is useful for very sparse bitmaps [24]: We δ-encode the runs of 0’s between consecutive 1’s, and store absolute pointers to the representation of every sth 1. This is very efficient in space and solves $selec{t}_1$ queries in time $O\left(s\right)$, which is the operation needed to compute a $\mathit{PLCP}$ value.

The main issue is how to support fast operations using the RLCSA and our LCP representation. Directly using the $\mathit{RMM}$ tree structure requires at least 1 bpc (see Figure 3), which is too much when indexing repetitive collections. Our main idea is to replace the regular structure of tree $T_m$ by the parsing tree obtained by a Re-Pair compression of the sequence $\mathit{LCP}$. We now explain this idea in detail.

7.1. Grammar-Compressing the LCP Array

To solve the queries on top of the LCP array, we represent a part of it in grammar-compressed form. This will be redundant with our compressed representation of array H, which was already explained.

Following the idea in Fischer et al. [18], we grammar-compress the differential LCP array, defined as ${\mathit{LCP}}^{\prime }\left[i\right]=\mathit{LCP}\left[i\right]-\mathit{LCP}[i-1]$ if $i>1$, and ${\mathit{LCP}}^{\prime }\left[1\right]=\mathit{LCP}\left[1\right]$. This differential LCP array contains now $O\left(r\right)$ areas that are exact repetitions of others, and a Re-Pair-based compression of it yields $\left|R\right|+\left|C\right|=O(rlog\frac{n}{r})$ words [18,35]. We note, however, that the compression achieved in this way is modest [35]: We guarantee $O(rlog\frac{n}{r})$words, whereas the RLCSA and PLCP representations require basically $O(rlog\frac{n}{r})$bits. Indeed, the poor performance of variant $\mathit{RP}$ in Section 3 shows that the idea should not be applied directly.

To overcome this problem, we take advantage of the fact that this representation is redundant with H. We truncate the parsing tree of the grammar, and use it as a device to speed up computations that would otherwise require expensive accesses to $\mathit{PLCP}$ (i.e., to bitmap H).

Let R and C be the results of compressing ${\mathit{LCP}}^{\prime }$ with Re-Pair. Every nonterminal i of R expands to a substring $S[1,t]$ of ${\mathit{LCP}}^{\prime }$. No matter where S appears in ${\mathit{LCP}}^{\prime }$ (indeed, it must appear more than once), we can store some values that are intrinsic to S. Let us define a relative sequence of values associated to S, as follows: $S^{\prime }\left[0\right]=0$ and $S^{\prime }\left[j\right]=S\left[j\right]+S^{\prime }[j-1]$. Then, we define the following variables associated to the nonterminal:

• $mi{n}_i={min}_{1\le j\le t}{S}^{\prime }\left[j\right]$ is the minimum value in $S^{\prime }$.
• $lmi{n}_i$ and $rmi{n}_i$ are the leftmost and rightmost positions j where $S^{\prime }\left[j\right]=mi{n}_i$, respectively.
• $su{m}_i=S^{\prime }\left[t\right]={\sum }_{1\le j\le t}S\left[j\right]$ is the sum of the values $S\left[j\right]$.
• $cove{r}_i=t$ is the number of values in $S^{\prime }$.

As most of these values are small, we encode them with DACs [43], which use less space for short numbers while providing fast access ($rmin$ is stored as the difference with $lmin$).

To reduce space, we prune the grammar by deleting the nonterminals i such that $cove{r}_i<t$, where t will be a space/time tradeoff parameter. However, “short” nonterminals that are mentioned in sequence C are not deleted.

This ensures that we can skip $\Omega \left(t\right)$ symbols of $\mathit{LCP}$ with a single access to the corresponding nonterminal in C, except for the short nonterminals (and terminals) that are retained in C. To speed up traversals on C, we join together maximal consecutive subsequences of nonterminals and terminals in C that sum up a total $cover<t$: We create a new nonterminal rule in R (for which we precompute the variables above) and replace it in C, deleting those nonterminals that formed the new rule and do not appear anymore in C. This will also guarantee that no more than $O\left(t\right)$ accesses to $\mathit{LCP}$ are needed to solve queries. Note that we could have built a hierarchy of new nonterminals by recursively grouping t consecutive symbols of C, achieving logarithmic operation times just as with tree $T_m$ [29], but this turned out to be counterproductive in practice. Figure 9 gives an example.

Figure 9. On the left, example of the Re-Pair compression of a sequence $T={\mathit{LCP}}^{\prime }$. We show R in array form and also in tree form. On the right, our $\mathit{RP}-\mathit{NPR}$ construction over T, pruning with $t=4$. We show how deep can the symbols of C be expanded after the pruning.

Figure 9. On the left, example of the Re-Pair compression of a sequence $T={\mathit{LCP}}^{\prime }$. We show R in array form and also in tree form. On the right, our $\mathit{RP}-\mathit{NPR}$ construction over T, pruning with $t=4$. We show how deep can the symbols of C be expanded after the pruning.

Finally, sampled pointers are stored to every c-th cell of C. Each sample for position $C[c·j]$, stores:

• $\mathit{Pos}\left[j\right]=1+{\sum }_{1\le k\le cj-1}cove{r}_{C\left[k\right]}$, that is, the first position $\mathit{LCP}\left[i\right]$ corresponding to $C[c·j]$.
• $\mathit{Val}\left[j\right]={\sum }_{1\le k\le cj-1}su{m}_{C\left[k\right]}$, that is, the value $\mathit{LCP}\left[i\right]$.

7.2. Computing NSV, PSV, and RMQ

To answer $\mathit{NSV}\left(i\right)$, we first look for the rule $C\left[j\right]$ that contains $\mathit{LCP}[i+1]$: We binary search $\mathit{Pos}$ for the largest $j^{\prime }$ such that $\mathit{Pos}\left[j^{\prime }\right]\le i+1$ and then sequentially advance on $C[c{j}^{\prime }..j]$ until finding the largest j such that $pos=\mathit{Pos}\left[j\right]+{\sum }_{c{j}^{\prime }\le k<j}cove{r}_{C\left[k\right]}\le i+1$. At the same time, we compute $\ell =\mathit{Val}\left[j^{\prime }\right]+{\sum }_{c{j}^{\prime }\le k<j}su{m}_{C\left[k\right]}$.

Now, if $\ell +mi{n}_{C\left[j\right]}<\mathit{LCP}\left[i\right]$, it is possible that $\mathit{NSV}\left(i\right)$ is within the same $C\left[j\right]$. In this case, we search recursively the tree expansion with root $C\left[j\right]$ for the leftmost value to the right of i and smaller than $\mathit{LCP}\left[i\right]$: Let $C\left[j\right]\to ab$ in the grammar. We recursively visit child a if $\ell +mi{n}_a<\mathit{LCP}\left[i\right]$ and $pos+cove{r}_a\ge i+1$. If we find no answer there, or we had decided not to visit a, then we set $\ell =\ell +su{m}_a$ and $pos=pos+cove{r}_a$ and recursively visit child b if $\ell +mi{n}_b<\mathit{LCP}\left[i\right]$. Note that if $pos\ge i+1$ we do not need to enter b, but can simply use the value $mi{n}_b$ and the position $pos+lmi{n}_b$ for the minimum. If we also find no answer inside b, or we had decided not to visit b, we return with no value. On the other hand, if we reach a leaf l during the recursion, we sequentially scan the array $\mathit{LCP}[pos,pos+cove{r}_l-1]$, updating $\ell =\ell +\mathit{LCP}\left[k\right]$ and increasing $pos$. If at some position we find a value smaller than $\mathit{LCP}\left[i\right]$, we report the position $pos$.

If we return with no value from the first recursive call at $C\left[j\right]$, it was because the only values smaller than $\mathit{LCP}\left[i\right]$ were to the left of i. In this case, or if we had decided not to enter into $C\left[j\right]$ because $\ell +mi{n}_{C\left[j\right]}\ge \mathit{LCP}\left[i\right]$, we sequentially scan $C[j+1,n]$, while updating $\ell =\ell +su{m}_{C\left[k\right]}$ and $pos=pos+cove{r}_{C\left[k\right]}$, until finding the first k such that $\ell +mi{n}_{C\left[k\right]}<\mathit{LCP}\left[i\right]$. Once we find such k, we are sure that the answer is inside $C\left[k\right]$. Thus we enter into $C\left[k\right]$ with a procedure very similar to the one for $C\left[j\right]$ (albeit slightly simpler as we know that all the positions are larger than i). In this case, as the LCP values are discrete, we know that if $\ell +mi{n}_{C\left[k\right]}=\mathit{LCP}\left[i\right]-1$, there is no smaller value to the left of the $min$ value, so in this case we directly answer the corresponding $lmin$ value, without accessing the $\mathit{LCP}$ array. The solution to $\mathit{PSV}\left(i\right)$ is symmetric.

To answer $\mathit{RMQ}(x,y)$, we find the rules $C\left[i\right]$ and $C\left[j\right]$ containing x and y, respectively. We sequentially scan $C[i+1,j-1]$ and store the smallest $\ell +mi{n}_{C\left[k\right]}$ value found (in case of ties, the leftmost). If the minimum is smaller than the corresponding values $\ell +mi{n}_{C\left[i\right]}$ and $\ell +mi{n}_{C\left[j\right]}$, we directly return the value $pos+lmi{n}_{C\left[k\right]}$ corresponding to position $C\left[k\right]$. Else, if the global minimum in $C\left[i\right]$ is equal to or less than the minimum for $i<k<j$, we must examine $C\left[i\right]$ to find the smallest value to the right of $x-1$. Assume $C\left[i\right]\to ab$. We recursively enter into a if $pos+cove{r}_a\ge x$, otherwise we skip it. Then, we update $\ell =\ell +su{m}_a$ and $pos=pos+cove{r}_a$, and enter into b if $pos<x$, otherwise we directly consider $\ell +mi{n}_b$ as a candidate for the minimum sought. Finally, if we arrive at a leaf we scan it, updating ℓ and $pos$, and consider all the values ℓ where $pos\ge x$ as candidates to the minimum. The minimum for $C\left[i\right]$ is the smallest among all candidates to minimum considered, and with $pos+lmi{n}_b$ or the leaf scanning process we know its global position. This new minimum is compared with the minimum of $C\left[k\right]$ for $i<k<j$. Symmetrically, in case $k=j$ contains a value smaller than the minimum for $i\le j<j$, we have to examine $C\left[j\right]$ for the smallest value to the left of $y+1$.

7.3. Analysis

For the analysis we will assume that we hierarchically group the terminals and nonterminals of consecutive symbols in C (by extending the grammar) using a grouping factor of g, although, as explained, it turned out to be faster in practice not to do so. We will call h the height of the grammar, which can be made $O(logn)$ by generating balanced grammars [48] (we experiment with balanced and unbalanced grammars in the next section). We also use sampling steps c to access C and s for the $\mathit{PLCP}$ representation. We also assume s is the sampling step of the RLCSA, thus accessing one $\mathit{PLCP}$ cell takes $O(slogn)$ time.

Let us first consider operation $\mathit{NSV}$ (and $\mathit{PSV}$). We spend $O(logn+c)$ time to binary search $\mathit{Pos}$ and move from $C\left[c{j}^{\prime }\right]$ to $C\left[j\right]$. If we have to expand $C\left[j\right]$, the cost increases by $O\left(h\right)$: Note that if we had entered a, and obtained no answer inside it, then we can directly use $mi{n}_b$ and thus do not enter b, so we only enter one of the two. At the leaf of the grammar tree of $C\left[j\right]$, we may scan $O\left(t\right)$ symbols of $\mathit{LCP}$ using $\mathit{PLCP}$, which costs $O(tslogn)$. Further, the scanning of $C[j+1,n]$ takes time $O(glogn)$ assuming the hierarchical grouping, and the final expansion of $C\left[k\right]$ takes again $O(h+tslogn)$ time.

Now consider operation $\mathit{RMQ}$. Again, we spend $O(c+logn)$ time to find $C\left[i\right]$ and $C\left[j\right]$, and then expand them as before: Only one of the two branches is expanded in each case, so the time is $O(h+tslogn)$. Finally, we need time $O(glogn)$ to traverse the area $C[i+1,j-1]$.

Thus, for all the operations, the cost is $O(c+h+(ts+g)logn)$.

Let $r^{\prime }=\left|R\right|+\left|C\right|$, and recall that r is the number of runs, so $n^{\prime }=O(rlog\frac{n}{r})$ if using Re-Pair. The sampling parameters involve $O((n^{\prime }/c)log{n}^{\prime })$ bits for the sampling of C, plus $O\left(\right(r/s)logn)$ for the sampling of $\mathit{PLCP}$, plus $O\left(\right(n/s)logn)$ for the sampling of the RLCSA, plus $O((n^{\prime }/g)log{n}^{\prime })$ for the new rules created in the hierarchy for C. Parameter t involves in practice an important reduction in $\left|R\right|$, the set of rules, but this cannot be upper bounded in the worst case unless the grammar is balanced, in which case it is reduced to $O\left(\right|R|/t)$ rules.

By choosing $c=g={log}^{3}n$, $s={log}^{2}n$, $t=logn$, and assuming a balanced grammar, the cost of the operations simplifies to $O\left({log}^{4}n\right)$ and the extra space incurred by the samplings is $o\left(r\right)+O(n/logn)$ bits. This can be reduced to any $o\left(r\right)+O(n/{log}^{k}n)$, for any constant k, by raising the time complexity to $O\left({log}^{k+3}n\right)$.

8. Experimental Evaluation on Repetitive Collections

We used various DNA collections from the Repetitive Corpus of Pizza & Chili [49]. We took DNA collections Influenza and Para, which are the most repetitive ones, and Escherichia, a less repetitive one. These are collections of genomes of various bacteria of those species. We also use Plain DNA, which is plain DNA from PizzaChili, as a non-repetitive baseline. On the other hand, in order to show how results scale with repetitiveness, we also included Einstein, corresponding to the Wikipedia versions of the article about Einstein in German, although it is not a biological collection. Table 4 (left) gives some basic information on the collections, including the number of runs in Ψ (much lower than those for general sequences; see Table 2).

For the RLCSA we used a fixed sampling that gave reasonable performance: One absolute value out of 32 is stored to access $\Psi \left(i\right)$, and one text position every 128 is sampled to compute $A\left[i\right]$. Similarly, we used sampling step 32 for the δ-encoding of the bitmaps Z and O that encode H.

Table 4. Text size and size of our CST (which replaces the text), both in MB, and number of runs in Ψ. On the right, bpc for the different components, and total bpc of the different collections considered. The NPR structure is the smallest setting between $\mathit{RP}-\mathit{NPR}$ and $\mathit{RPBal}-\mathit{NPR}$ for that particular text.

Collection	Text Size	Runs ( $\mathit{r}\mathbf{/}\mathit{n}$)	CST size	RLCSA	(P)LCP	NPR	Total
Influenza	148	0.019	27	0.77	0.21	0.42	1.40
Para	410	0.036	67	1.28	0.26	0.36	1.90
Escherichia	108	0.134	48	2.46	0.92	0.39	3.77
Plain DNA	50	0.632	61	5.91	3.62	0.29	9.82
Einstein	89	0.001	3	0.48	0.01	0.14	0.63

Table 4. Text size and size of our CST (which replaces the text), both in MB, and number of runs in Ψ. On the right, bpc for the different components, and total bpc of the different collections considered. The NPR structure is the smallest setting between $\mathit{RP}-\mathit{NPR}$ and $\mathit{RPBal}-\mathit{NPR}$ for that particular text.

Collection	Text Size	Runs ( $\mathit{r}\mathbf{/}\mathit{n}$)	CST size	RLCSA	(P)LCP	NPR	Total
Influenza	148	0.019	27	0.77	0.21	0.42	1.40
Para	410	0.036	67	1.28	0.26	0.36	1.90
Escherichia	108	0.134	48	2.46	0.92	0.39	3.77
Plain DNA	50	0.632	61	5.91	3.62	0.29	9.82
Einstein	89	0.001	3	0.48	0.01	0.14	0.63

Table 4 (right) shows the resulting sizes. The bpc of the CST is partitioned into those for the RLCSA, for the PLCP (H), and for NPR, which stands for the data structure that solves $\mathit{NSV}/\mathit{PSV}/\mathit{RMQ}$ queries. For the latter we used $t=256$, which offered answers within 2 milliseconds (ms). Note that Fischer et al.’s [18] compression of bitmap H does work in repetitive sequences, unlike what happened in the general case: We reduce the space from 2 bpc to 0.21–0.26 bpc on the more repetitive DNA sequences, for example. Similarly, the regular RMM-tree uses 1–5 bpc, whereas our version adapted to repetitive sequences uses as little as 0.3–0.4 bpc. The good space performance of the RLCSA, compared with a regular CSA for general sequences, also contributes to obtain a remarkable final space of 1.4–1.9 bpc for the more repetitive DNA sequences. This value deteriorates until approaching, for plain (non-repetitive) DNA, the same 10 bpc that we obtained before. Thus our data structure adapts smoothly to the repetitiveness (or lack of it) of the collection.

On the other hand, on Einstein, which is much more repetitive, the total space gets as low as 0.6 bpc. This is a good indication of what we can expect on future databases with thousands of individuals of the same species, as opposed to these testbeds with a few tens of individuals, or with more genetic variation. To give more insight into how the space of our structures evolve as the repetitiveness increases, Figure 10 shows the space used by each component of the index on increasing prefixes of collections Influenza and Einstein. It can be seen that, as the we index more of the collection, the space of the different components decreases until reaching a stable point that depends on the intrinsic repetitiveness of the collection (this is reached earlier for Influenza). Note, however, that even in the more repetitive Einstein, the RLCSA stabilizes very early at a fixed space. This space is that of the suffix array sampling, which is related to the speed of computing the contents of suffix array cells (and hence computing LCP values). It is interesting that Mäkinen et al. [25] proposed a solution to compress this array that proved impractical for the small databases we are experimenting with, but whose asymptotic properties ensure that will become practical for sufficiently large and repetitive collections.

Figure 10. Evolution of the space, in bpc, of our structures for increasing prefixes of collections Influenza and Einstein.

Figure 10. Evolution of the space, in bpc, of our structures for increasing prefixes of collections Influenza and Einstein.

Let us discuss the NPR operations now. We used a public Re-Pair compressor built by ourselves [50], which offers two alternatives when dealing with symbols of the same frequencies. The basic one, which we will call $\mathit{RP}-\mathit{NPR}$, stacks the pairs of the same frequency, whereas the second one, $\mathit{RPBal}-\mathit{NPR}$, enqueues them and obtains much more balanced grammars in practice. For our structure we tested values $t=c=64,128,256,512$. We also include the basic regular RMM-tree of the previous sections (but running over our RLCSA and PLCP representations), to show that on repetitive collections our grammar-based version offers better space/time tradeoffs than the regular tree $T_m$. For this version, $\mathit{RP}-\mathit{RMM}$, we used values $L=36,64,128,256,512$.

We measure the times of operations $\mathit{NSV}$ (as $\mathit{PSV}$ is symmetric) and $\mathit{RMQ}$ following the methodology of Section 6: We choose 10,000 random suffix tree leaves (corresponding to uniformly random suffix array intervals $[v_l,v_r]=[v,v],v\in [1,n]$) and navigate towards the root using operation $\mathit{Parent}(v_l,v_r)=[\mathit{PSV}\left(v_l\right),\mathit{NSV}\left(v_r\right)-1]$. At each such node, we also measure the string depth, $\mathit{SDepth}(v_l,v_r)=\mathit{LCP}\left[\mathit{RMQ}(v_l+1,v_r)\right]$. We average the times of the $\mathit{NSV}$ and $\mathit{RMQ}$ queries involved.

Figure 11 shows the space/time performance of $\mathit{RMM}-\mathit{NPR}$, $\mathit{RP}-\mathit{NPR}$, and $\mathit{RPBal}-\mathit{NPR}$ on the repetitive collections. In addition, it shows the number of explicit accesses to $\mathit{LCP}$ made per NPR operation.

In general the curves for total time and number of $\mathit{LCP}$ accesses have the same shape, showing that in practice the main cost of the NPR operations lies in retrieving the LCP values. In some cases, and most noticeably for $\mathit{RMQ}$ queries on Para using $\mathit{RP}-\mathit{NPR}$, using more space yields fewer $\mathit{LCP}$ accesses but higher time. This is because the Re-Pair grammars may be very unbalanced, and giving more space to them results in less tree pruning. Thus deeper trees, whose nodes have to be traversed one by one to cover short $\mathit{LCP}$ passages, are generated. $\mathit{RPBal}-\mathit{NPR}$ largely corrects this effect by generating more balanced grammar trees.

Clearly, $\mathit{RP}-\mathit{NPR}$ and $\mathit{RPBal}-\mathit{NPR}$ dominate the space/time map for all queries. They always make better use of the space than the regular tree of $\mathit{RMM}-\mathit{NPR}$. $\mathit{RPBal}-\mathit{NPR}$ is usually better than $\mathit{RP}-\mathit{NPR}$, except on some particular cases, like $\mathit{NSV}$ on Escherichia, where $\mathit{RP}-\mathit{NPR}$ is faster.

Figure 11. Space/Time performance of NPR operations. The x-axis shows the size of the NPR structure. On the left y-axis the average time per operation (solid lines), and on the right y-axis the average number of LCP accesses per operation (dashed lines). Note the log scale on y for Einstein.

Figure 11. Space/Time performance of NPR operations. The x-axis shows the size of the NPR structure. On the left y-axis the average time per operation (solid lines), and on the right y-axis the average number of LCP accesses per operation (dashed lines). Note the log scale on y for Einstein.

The times of our best variants are in the range of a few milliseconds per operation. This is high compared with the times obtained on general sequences. The closest comparison point is Russo et al.’s CST [14] whose times are very similar, but it uses 4–6 bpc compared with our 1.4–1.9 bpc. As discussed, we can expect our bpc value to decrease even more on larger databases. Such a representation, even if taking milliseconds per operation, is very convenient if it saves us from using a disk-based suffix tree. Note also that, on very repetitive collections, we could avoid pruning the grammar at all. In this case the grammar itself would give access to the LCP array much faster than by accessing bitmap H.

9. Conclusions

We have presented new practical compressed suffix tree implementations that offer very relevant space/time tradeoffs. This opens the door to a number of practical suffix tree applications, particularly relevant to bioinformatics. We have left the code publicly available at the Pizza & Chili site, to foster its widest dissemination [51].

Our main idea is to adapt range min-max trees [22] to the problem of solving queries on the LCP array. This has proved to offer an attractive combination of time and space. Moreover, it offers stronger functionality, allowing us to easily implement complex operations like string-level ancestors (${\mathit{LAQ}}_S$), which are seldom implemented in other CSTs. The second key idea is that, on repetitive collections, one can grammar-compress the differential LCP array and use the grammar tree as a (non-regular) variant of the range min-max tree, whose size depends on the repetitiveness of the text collection. This has yielded the first compressed suffix tree that takes full advantage of repetitive collections, offering spaces well below 2 bits per character.

This is an active and lively research topic, and there has been interesting advances since our first publication [29]. Gog [21] developed another LCP representation that falls between $\mathit{DAC}/\mathit{DAC}-\mathit{Var}$ and $\mathit{Sad}-\mathit{Gon}/\mathit{FMN}-\mathit{RRR}$ (recall Section 3). Ohlebusch et al. [21,28] developed a data structure using $3n+o\left(n\right)$ bits that answers the three queries $\mathit{NSV}/\mathit{PSV}/\mathit{RMQ}$ efficiently (recall Section 4). Both techniques were combined to build an alternative CST implementing Fischer et al.’s [18] idea, which outperforms our “large and fast” variant based on $\mathit{DAC}/\mathit{DAC}-\mathit{Var}$. Our “small and slow” variant, instead, still requires less space, and in this aspect is only outperformed by Russo et al.’s [14] CST, which is orders of magnitude slower. Furthermore, our technique is unbeaten when adapted to repetitive collections, which none of the other existing CSTs exploits well. As an example, our adapted range min-max tree uses 0.2–0.3 bpc on these collections, which is at least 10–15 times smaller than the new $3n+o\left(n\right)$$\mathit{NSV}/\mathit{PSV}/\mathit{RMQ}$ structure of Ohlebusch et al. [28].