FM-index：机会主义数据结构及其应用

There is an upsurging interest in designing succinct data structures for basic searching problems (see [23] and references therein). The motivation has to be found in the exponential increase of electronic data nowadays available which is even surpassing the significant increase in memory and disk storage capacities of current computers. Space reduction is an attractive issue because it is also intimately related to performance improvements as noted by several authors (e.g. Knuth [15], Bentley [5]). In designing these implicit data structures the goal is to reduce as much as possible the auxiliary information kept together with the input data without introducing a significant slowdown in the final query performance. Yet input data are represented in their entirety thus taking no advantage of possible repetitiveness into them. The importance of those issues is well known to programmers who typically use various tricks to squeeze data as much as possible and still achieve good query performance. Their approaches, though, boil down to heuristics whose effectiveness is witnessed only by experimentation.

In this paper, we address the issue of compressing and indexing data by studying it in a theoretical framework. We devise a novel data structure for indexing and searching whose space occupancy is a function of the entropy of the underlying data set. The novelty resides in the careful combination of a compression algorithm, proposed by Burrows and Wheeler [7], with the structural properties of a well known indexing tool, the Suffix Array [17]. We call the data structure opportunistic since its space occupancy is decreased when the input is compressible at no significant slowdown in the query performance. More precisely, its space occupancy is optimal in an information-content sense because a text T[1,u] is stored using O(H_k(T)) + o(1) bits per input symbol, where H_k(T) is the k-th order entropy of T (the bound holds for any fixed k). Given an arbitrary string P[1,p], the opportunistic data structure allows to search for the occ occurrences of P in T requiring O(p + occ log^ε u) time complexity (for any fixed ε > 0). If data are uncompressible we achieve the best space bound currently known [11]; on compressible data our solution improves the succinct suffix array of [11] and the classical suffix tree and suffix array data structures either in space or in query time complexity or both.

It is a belief [27] that some space overhead should be paid to use full-text indices (like suffix trees or suffix arrays) with respect to word-based indices (like inverted lists). The results in this paper show that a full-text index may achieve sublinear space overhead on compressible texts. As an application we devise a variant of the well-known Glimpse tool [18] which achieves sublinear space and sublinear query time complexity. Conversely, inverted lists achieve only the second goal [27], and classical Glimpse achieves both goals but under some restrictive conditions [4].

Finally, we investigate the modifiability of our opportunistic data structure by studying how to choreograph its basic ideas with a dynamic setting thus achieving effective searching and updating time bounds.

Data structure is a central concept in algorithmics and computer science in general. In the last decades it has been investigated from different points of view and its basic ideas enriched by new functionalities with the aim to cope with the features of the peculiar setting of use: dynamic, persistent, self-adjusting, implicit, fault-tolerant, just to cite a few. Space reduction in data structural design is an attractive issue, now more than ever before, because of the exponential increase of electronic data nowadays available, and because of its intimate relation with algorithmic performance improvements (see e.g. Knuth [15] and Bentley [5]). This has recently motivated an upsurging interest in the design of implicit data structures for basic searching problems (see [23] and references therein). The goal in their design is to reduce as much as possible the auxiliary information kept together with the input data without introducing any significant slowdown in the final query performance. However, input data are represented in their entirety thus taking no advantage of possible repetitiveness into them. The importance of those issues is well known to programmers who typically use various tricks to squeeze data as much as possible and still achieve good query performance. Their approaches, though, boil down to heuristics whose effectiveness is witnessed only by experimentation.

In this paper we address the issue of compressing and indexing data by studying it in a theoretical framework. From the best of our knowledge no other result is known in the literature about the study of the interplay between compression and indexing of data collections. The exploitation of data compressibility have been already investigated only with respect to its impact on algorithmic performance in the context of on-line algorithms (e.g. caching and prefetching [16, 14]), string-matching algorithms (see e.g. [1, 2, 9]), sorting and computational geometry algorithms [8].

The scenario. Most of the research in the design of indexing data structure has been mainly directed to devise solutions which offer a good trade-off between query and update time versus space usage. The two main approaches are word-based indices and full-text indices. The former achieve succinct space occupancy at the cost of being mainly limited to index linguistic texts [27], the latter achieve versatility and guaranteed performance at the cost of requiring large space occupancy (see e.g. [20, 17, 10]). Some progress on full-text indices has been recently achieved [23, 11], but an asymptotical linear space seems unavoidable and this makes word-based indices much more appealing when space occupancy is a primary concern. In this context compression appears always as an attractive choice, if not mandatory. Processing speed is currently improving at a faster rate than disk speeds. Since compression decreases the demand of storage devices at the expenses of processing, it is becoming more economical to store data in a compressed form rather than uncompressed. Furthermore, compression may introduce some improvements which are surprisingly not confined to the space occupancy: like transfer time and, even, seek times [15, 5].

Starting from these promising considerations, many authors have recently concentrated on the compressed matching problem, introduced in [1], as the task of performing string matching in a compressed text without decompressing it. A collection of algorithms is currently known to solve efficiently (possibly optimally) this problem on text compressed by means of various schemes: e.g. run-length [1], LZ77 [9], LZ78 [2], Huffman [24]. All of those results, although asymptotically faster than the classical scan-based methods, they rely on the full scan of the whole compressed text and thus result still unacceptable for large text collections.

Approaches to combine compression and indexing techniques are nowadays receiving more and more attention, especially in the context of word-based indices, achieving experimental trade-offs between space occupancy and query performance (see e.g. [18, 27, 4]). A significant idea towards the direct compression of the index data structure has been proposed in [12, 13] where the properties of the Lempel-Ziv's compression scheme have been exploited to reduce the number of index points, still supporting pattern searches. As a result, the overall index requires provably sublinear space but at the cost of either limiting the search to q-grams [12] or worsening significantly the query performance [13].

A natural question arises at this point: Do full-text indices need a space occupancy linear in the (uncompressed) text size in order to support effective search operations on arbitrary patterns? It is a common belief [27] that some space overhead must be paid to use the full-text indices, but is this actually a provable need?

Our Results. In this paper we answer the two questions above by providing a novel data structure for indexing and searching whose space occupancy is a function of the entropy of the underlying data set. The data structure is called opportunistic in that, although no assumption on a particular distribution is made, it takes advantage of compressibility of the input data by decreasing the space occupancy at no significant slowdown in the query performance. The data structure is provably space optimal in an information-content sense because it stores a text T[1,u] using O(H_k(T)) + o(1) bits per input symbol (for any fixed k ≥ 0), where H_k(T) is the k-th order empirical entropy (see Appendix A). H_k expresses the maximum compression we can achieve using for each character a code which depends only on the k characters preceding it. We point out that in the case of an uncompressible string T, the space occupancy is O(u) bits which is actually the best space bound currently known [11]; for a compressible string, our opportunistic data structure is the first index to achieve sublinear space occupancy. Given an arbitrary pattern P[1,p], such opportunistic data structure allows to search for the occ occurrences of P in T requiring O(p + occ log^ε u) time, for any fixed ε > 0. The removal of the sublogarithmic term in the query bound is yet an open problem even in the uncompressed setting [11].

The novelty of our approach resides in the careful combination of the Burrows-Wheeler compression algorithm [7] with the Suffix Array data structure [17] to obtain a sort of compressed suffix array. We indeed show how to augment the information kept by the Burrows-Wheeler algorithm, in order to support effective random accesses to the compressed data without the need of uncompressing all of them at querying time. We design two algorithms for operating on our opportunistic data structure. The first algorithm is a novel effective approach to search for an arbitrary pattern P[1,p] in a compressed suffix array, taking O(p) time in the worst case (see Section 3.1); the second algorithm exploits compression to speed up the retrieval of the actual positions of the pattern occurrences, thus incurring only in a sublogarithmic O(log^ε u) time slowdown (for any fixed ε > 0, see Section 3.2).

In some sense, our result can be interpreted as a method to compress the suffix array, and still support effective searches for arbitrary patterns. In their seminal paper, Manber and Myers [17] introduced the suffix array data structure showing how to search for a pattern P[1,p] in O(p + log u + occ) time in the worst case. The data structure used Θ(u log u) bits of storage. Recently, Grossi and Vitter [11] reduced the space usage of suffix arrays to Θ(u) bits at the cost of requiring O(log^ε u) time to retrieve the i-th suffix. Hence, searching in this succinct suffix array via the classical Manber-Myers' procedure takes O(p + log^1+ε u + occ log^ε u) time. Our solution therefore improves the succinct suffix array of [11] both in space and query time complexity. The authors of [11] introduce also other hybrid indices based on the combination of their succinct suffix array and various known techniques; they achieve O(p/log u + occ log^ε u) query-time complexity but yet require Θ(u) bits of storage. As far as the problem of counting the pattern occurrences is concerned, our solution improves the classical suffix tree and suffix array data structures, because they achieve Θ(p) time complexity and occupy Θ(u log u) bits.

In Section 4, we investigate the modifiability of our opportunistic data structure by studying how to choreograph its basic ideas with a dynamic setting, and thus achieving efficient searching and updating time bounds. We show that a dynamic text collection Δ of size u can be stored in O(H_k(Δ)) + o(1) bit per input symbol (for any fixed k ≥ 0 and not very short texts), support insert operations on individual texts T[1,t] in O(t log u) amortized time, delete operations on T in O(t log² u) amortized time, and search for a pattern P[1,p] in O(p log³ u + occ log u) time in the worst case. We point out that even in the case of an uncompressible text T, our space bounds are the best known ones since the data structures in [11] do not support updates (the dynamic case is left as open in their Section 4).

Finally, we investigate applications of our ideas to the development of novel text retrieval systems based on the concept of block addressing (first introduced in the Glimpse tool [18]). The notable feature of block addressing is that it can achieve both sublinear space overhead and sublinear query time, whereas inverted indices achieve only the second goal [4]. Unfortunately, up to now all the known block addressing indices [18, 4] achieve this goal only under some restrictive conditions on the block size. We show how to use our opportunistic data structure to devise a novel block addressing scheme, called CGlimpse (standing for Compressed Glimpse), which always achieves time and space sublinearity.

Let T[1,u] be a text drawn from a constant-size alphabet Σ. A central concept in our discussion is the suffix array data structure [17]. The suffix array A built on T[1,u] is an array containing the lexicographically ordered sequence of the suffixes of T, represented via pointers to their starting positions (i.e., integers). For instance, if T = ababc then A = [1, 3, 2, 4, 5]. In practice A occupies 4u bytes, actually a lot when indexing large text collections. It is a long standing belief that suffix arrays are uncompressible because of the "apparently random" permutation of the suffix pointers. Recent results in the data compression field have opened the door to revolutionary ways to compress suffix arrays and are the basic tools of our solution. In [7], Burrows and Wheeler proposed a transformation (BWT from now on) consisting of a reversible permutation of the text characters which gives a new string that is "easier to compress". The BWT tends to group together characters which occur adjacent to similar text substrings. This nice property is exploited by locally-adaptive compression algorithms, such as move-to-front coding [6], in combination with statistical (i.e. Huffman or Arithmetic coders) or structured coding models. The BWT-based compressors are among the best compressors currently available since they achieve a very good compression ratio using relatively small resources (time and space).

The reversible BW-transform. We distinguish between a forward transformation, which produces the string to be compressed, and a backward transformation which gives back the original text from the transformed one. The forward BWT consists of three basic steps: (1) Append to the end of T a special character # smaller than any other text character; (2) form a conceptual matrix M whose rows are the cyclic shifts of the string T# sorted in lexicographic order; (3) construct the transformed text L by taking the last column of M. Notice that every column of M is a permutation of the last column L, and in particular the first column of M, call it F, is obtained by lexicographically sorting the characters in L.

There is a strong apparent relation between the matrix M and the suffix array A of the string T#. When sorting the rows of the matrix M we are essentially sorting the suffixes of T#. Consequently, entry A[i] points to the suffix of T# occupying (a prefix of) the i-th row of M. The cost of performing the forward BWT is given by the cost of constructing the suffix array A, and this requires O(u) time [20].

The cyclic shift of the rows of M is crucial to define the backward BWT, which is based on two easy to prove observations [7]:
(a) Given the i-th row of M, its last character L[i] precedes its first character F[i] in the original text T, namely T = ... L[i] F[i] ...
(b) Let L[i] = c and let r_i be the rank of the row M[i] among all the rows ending with the character c. Take the row M[j] as the r_i-th row of M starting with c. Then the character corresponding to L[i] in the first column F is located at F[j] (we call this LF-mapping, where LF[i] = j).

We are therefore ready to describe the backward BWT:
1. Compute the array C[1...|Σ|] storing in C[c] the number of occurrences of characters {#, 1, ..., c − 1} in the text T. Notice that C[c] + 1 is the position of the first occurrence of c in F (if any).
2. Define the LF-mapping LF[1...u + 1] as follows LF[i] = C[L[i]] + r_i, where r_i equals the number of occurrences of character L[i] in the prefix L[1,i] (see observation (b) above).
3. Reconstruct T backward as follows: set s = 1 and T[u] = L[1] (because M[1] = #T); then, for each i = u − 1, ..., 1 do s = LF[s] and T[i] = L[s].

In [26] it has been shown how to derive the suffix array A from L in linear time; however in the context of pattern searching this approach is no better than the known scan-based opportunistic algorithms [9]. Nonetheless, the implicit presence of the suffix array A into L stimulates the investigation of the possibility to take full advantage of the structure of A for fast searching, and of the succinct compression of L for reducing the overall space occupancy. This is actually the ultimate hope of any indexer: succinct and fast! In the next section, we show that this result is achievable provided that a sublogarithmic slowdown is introduced in the cost of listing all pattern occurrences.

In order to describe our results on searching in BWT-compressed texts, we must commit ourselves to one of several algorithms based on the BWT. Let T_bw = bwt(T) denote the last column L, output of the BW-transform. We compress T_bw in three steps (see also [19]):
1. Use a move-to-front coder, briefly mtf [6], to encode a character c via the count of distinct characters seen since its previous occurrence. The structural properties of T_bw, mentioned above, imply that the string T_mtf = mtf(T_bw) will be dominated by low numbers.
2. Encode each run of zeroes in T_mtf using run length encoding (rle). More precisely, replace the sequence 0^m with the number (m + 1) written in binary, least significant bit first, discarding the most significant bit. For this encoding we use two new symbols 0 and 1 so that the resulting string T_rl = rle(T_mtf) is over the alphabet {0, 1, 1, 2, ..., |Σ| − 1}.
3. Compress T_rl by means of a variable-length prefix code, called PC, which encodes the symbols 0 and 1 using two bits (10 for 0, 11 for 1), and the symbol i using a variable-length prefix code of 1 + 2⌊log(i + 1)⌋ bits, where i = 1, 2, ..., |Σ| − 1.

The resulting algorithm BWRLX = bwt + mtf + rle + PC is sufficiently simple so that in the rest of the paper we can concentrate on the searching algorithm without being distracted by the details of the compression. Despite of the simplicity of BWRLX, using the results in [19] it is possible to show that (proof in the full paper), for any k ≥ 0 there exists a constant g_k such that

where H_k is the k-th order empirical entropy. H_k expresses the maximum compression we can achieve using for each character a code which depends only on the k characters preceding it. The bound (1) tells us that even for strings with very small entropy BWRLX's output size is within a constant factor of the optimum. Note that such a similar bound has not been proven for any LZ-based algorithm [19].

Let T[1,u] denote an arbitrary text over the alphabet Σ, and let Z = BWRLX(T). In this section we describe an algorithm which, given Z and a pattern P[1,p], reports all occurrences of P in the uncompressed text T without uncompressing the whole Z. Our algorithm makes use of the relation between the suffix array A and the matrix M (see above). Recall that the suffix array A posses two nice structural properties which are usually exploited to support fast pattern searches: (i) all the suffixes of the text T[1,u] prefixed by a pattern P[1,p] occupy a contiguous portion (subarray) of A; (ii) that subarray has starting position sp and ending position ep, where sp is actually the lexicographic position of the string P among the ordered sequence of text suffixes.

We now describe an algorithm, called BW Search, which identifies the positions sp and ep by accessing only the compressed string Z and some auxiliary array-based data structures.

Algorithm BW Search consists of p phases each one preserving the following invariant: At the i-th phase, the parameter sp points to the first row of M prefixed by P[i,p] and the parameter ep points to the last row of M prefixed by P[i,p]. The pseudo-code is given in Fig. 1. We start with i = p (step 1), so that sp and ep can be determined via the array C defined in Section 2 (step 2). If ep < sp then we can conclude that P[p] does not occur in T and hence P does not too. The subroutine Occ(c, 1, k) used in Steps 5 and 6 reports the number of occurrences of the character c in T_bw[1,k]; hence it is employed to implement the LF-mapping. After the final phase, sp and ep will delimit the portion of M (and thus of the suffix array A) containing all text suffixes prefixed by P. The integer (ep − sp + 1) will account for the number of occurrences of P in T. The following lemma proves the correctness of BW Search, assuming Occ works as claimed (proof in Appendix B).

Lemma 1 For i = p, p − 1, ..., 2, let us assume that sp (resp. ep) stores the position of the first (resp. last) row in M prefixed by P[i,p]. If P[i − 1, p] occurs in T, then Step 5 (resp. Step 6) of BW Search correctly updates the value of sp (resp. ep) thus pointing to the first (resp. last) row prefixed by P[i − 1, p].

The running time of BW Search depends on the cost of procedure Occ. We now describe an algorithm for computing Occ(c, 1, k) in O(1) time, on a RAM with word size Θ(log u) bits.

We logically partition the transformed string T_bw into substrings of ℓ characters each (called buckets), and denote them by BT_i = T_bw[(i − 1)ℓ + 1, iℓ], for i = 1, ..., u/ℓ. This partition naturally induces a partition of T_mtf into u/ℓ buckets BT^mtf₁, ..., BT^mtf_u/ℓ of size ℓ too. We assume that each run of zeroes in T_mtf is entirely contained in a single bucket and we describe our algorithm for computing Occ(c, 1, k) under this simplifying assumption. The general case in which a sequence of zeroes may span several buckets is discussed in Appendix C. Under our assumption, the buckets BT^mtf_i's induce a partition of the compressed file Z into u/ℓ compressed buckets BZ₁, ..., BZ_u/ℓ, defined as BZ_i = PC(rle(BT^mtf_i)).

Let BT_i denote the bucket containing the character T_bw[k] (i = ⌈k/ℓ⌉). The computation of Occ(c, 1, k) is based on a hierarchical decomposition of T_bw[1,k] in three substrings as follows: (i) the longest prefix of T_bw[1,k] having length a multiple of ℓ² (i.e. BT₁ ... BT_ℓi*, where i* = ⌊(k − 1)/ℓ²⌋), (ii) the longest prefix of the remaining suffix having length a multiple of ℓ (i.e. BT_ℓi*+1 ... BT_i−1), and finally (iii) the remaining suffix of T_bw[1,k] which is indeed a prefix of the bucket BT_i. We compute Occ(c, 1, k) by summing the number of occurrences of c in each of these substrings. This can be done in O(1) time and sublinear space using the following auxiliary data structures:

For the calculations on the substring of point (i):
- For i = 1, ..., u/ℓ², the array NO_i[1,|Σ|] stores in entry NO_i[c] the number of occurrences of character c in BT₁ ... BT_iℓ.
- The array W[1, u/ℓ²] stores in entry W[i] the value Σ_j=1^iℓ |BZ_j| equals to the sum of the sizes of the compressed buckets BZ₁, ..., BZ_iℓ.

For the calculations on the substring of point (ii):
- For i = 1, ..., u/ℓ, the array NO′_i[1,|Σ|] stores in entry NO′_i[c] the number of occurrences of character c in the string BT_ℓi*+1 ... BT_i−1 (this concatenated string has length less than ℓ²).
- The array W′[1, u/ℓ] stores in entry W′[i] the value Σ_j=i*+1ⁱ⁻¹ |BZ_j| equals to the overall size of the compressed buckets BZ_i*+1, ..., BZ_i−1 (bounded above by O(ℓ²)).

For the calculations on the (compressed) buckets:
- The array MTF[1, u/ℓ] stores in entry MTF[i] a picture of the state of the MTF-list at the beginning of the encoding of BT_i. Each entry takes |Σ| log |Σ| bits (i.e. O(1) bits).
- The table S stores in each entry S[c, h, BZ_i, MTF[i]] the number of occurrences of the character c among the first h characters of BT_i. The values of BZ_i and MTF[i] are used to determine BT_i from Z in O(1) time. Table S has O(ℓ 2^ℓ′) entries each one occupying log ℓ bits.

The computation of Occ(c, 1, k) proceeds as follows. First, the bucket BT_i containing the character c = T_bw[k] is determined via i = ⌈k/ℓ⌉, together with the position j = k − (i − 1)ℓ of this character in BT_i and the parameter i* = ⌊(k − 1)/ℓ²⌋. Then the number of occurrences of c in the prefix BT₁ ... BT_ℓi* (point (i)) is determined via NO_i*[c], and the number of occurrences of c in the substring BT_ℓi*+1 ... BT_i−1 (point (ii)) is determined via NO′_i[c]. Finally, the compressed bucket BZ_i is retrieved from Z (notice that W[i*] + W′[i] + 1 is its starting position), and the number of occurrences of c within BT_i[1,j] are accounted using table S. The sum of these three quantities gives Occ(c, 1, k).

By construction any compressed bucket BZ_i has size at most ℓ′ = (1 + 2⌊log Σ⌋) ℓ bits. Now we set ℓ = Θ(log u) so that ℓ′ = c log u with c < 1. Under this assumption, every step of Occ consists of arithmetic operations or table lookup operations involving O(log u)-bit operands. Consequently every call to Occ takes O(1) time on a RAM. As far as the space occupancy is concerned, the arrays NO and W take O((u/ℓ²) log u) = O(u/log u) bits. The arrays NO′ and W′ take O((u/ℓ) log ℓ) = O((u/log u) log log u) bits. The array MTF takes O(u/ℓ) = O(u/log u) bits. Table S consists of O(ℓ 2^ℓ′) log ℓ-bit entries, and thus it occupies O(2^ℓ′ ℓ log ℓ) = O(u^c log u log log u) bits, where c < 1. We conclude that the auxiliary data structures used by Occ occupy O((u/log u) log log u) bits (in addition to the compressed file Z). We can now state the first important result of our paper.

Theorem 1 Let Z denote the output of the algorithm BWRLX on input T[1,u]. The number of occurrences of a pattern P[1,p] in T[1,u] can be computed in O(p) time on a RAM. The space occupancy is |Z| + O((u/log u) log log u) bits.

We now consider the problem of determining the exact position in the text T[1,u] of all the occurrences of the pattern P[1,p]. This means that for s = sp, sp + 1, ..., ep, we need to find the position pos(s) in T of the suffix which prefixes the s-th row M[s]. We propose two approaches: the first one is simple but slow, the second one is faster and relies on the very special properties of the string T_bw and on a different compression algorithm.

In the first algorithm we logically mark the rows of M which correspond to text positions having the form 1 + iη, for η = Θ(log² u) and i = 0, 1, ..., u/η. We store with these marked rows the starting positions of the corresponding text suffixes explicitly. This preprocessing is done at compression time. At query time we find pos(s) as follows. If s is a marked row, then there is nothing to be done and its position is directly available. Otherwise, we use the LF-mapping to find the row s′ corresponding to the suffix T[pos(s) − 1, u]. We iterate this procedure v times until s′ points to a marked row; then we compute pos(s) = pos(s′) + v. The crucial point of the algorithm is the logical marking of the rows of M corresponding to the text suffixes starting at positions 1 + iη, i = 0, ..., u/η. Our solution consists in storing the row numbers in a two-level bucketing scheme. We partition the rows of M into buckets of size Θ(log² u) each. For each bucket, we take all the marked rows lying into it, and store them into a Packet B-tree [3] using as a key their distance from the beginning of the bucket. Since a bucket contains at most O(log² u) keys, each O(log log u) bits long, membership queries take O(1) time on a RAM. The overall space required for the logical marking is O((u/η) log log u) bits. In addition, for each marked row we also keep the starting position of the corresponding suffix in T, which requires additional O(log u) bits per marked row. Consequently, the overall space occupancy is O((u/η) log u) = O(u/log u) bits. For what concerns the time complexity, our algorithm computes pos(s) in at most η = Θ(log² u) steps, each taking constant time. Hence the occ occurrences of a pattern P in T can be retrieved in O(occ log² u) time, with a space overhead of O(u/log u) bits. Combining the results of this section with equation (1):

Theorem 2 Given a text T[1,u], we can preprocess it in O(u) time so that all the occ occurrences of a pattern P[1,p] in T can be listed in O(p + occ log² u) time on a RAM. The space occupancy is bounded by 5 H_k(T) + O((log log u)/(log u)) bits per input symbol, for any fixed k ≥ 0.

We now refine the above algorithm in order to compute pos(s) in O(log^ε u) time, for any fixed ε > 0. We still use the idea of marking some of the rows in M, however we introduce some shortcuts which allow to move in T by more than one character at a time, thus reducing the number of steps required to reach a marked position. The key ingredient of our new approach is a procedure for computing the LF-mapping over a string T̄ drawn from an alphabet Λ of non-constant size. The procedure is based on an alternative compression of the output T̄_bw. We make use of the following lemma (proof and details are given Appendix D):

Lemma 2 Given a string T̄[1,v] over an arbitrary alphabet Λ, we can compute the LF-mapping over T̄_bw in O(log^ε v) time using O(v(1 + H_k(T̄)) + |Λ|^k+1 (log |Λ| + log v)) bits of storage, for any given ε > 0.

We now show how to use Lemma 2 to compute pos(s) in O(log^(1/2)+2ε u) time; this is an intermediate result that will be then refined to achieve the final O(log^ε u) time bound.

At compression time we logically mark the rows of M which correspond to text positions of the form 1 + iμ for i = 0, ..., u/μ and μ = Θ(log^(1/2)+ε u). Then, we consider the string T⁰ obtained by grouping the characters of T into blocks of size μ. Clearly T⁰ has length u/μ and its characters belong to the alphabet Σ^μ. Let M⁰ denote the cyclic-shift matrix associated to T⁰. It is easy to see that M⁰ consists of the marked rows of M. Now we mark the rows of M⁰ corresponding to the suffixes of T⁰ starting at the positions 1 + iη, for i = 0, ..., |T⁰|/η and η = Θ(log^(1/2)+ε u). For these rows we explicitly keep the starting position of the corresponding text suffixes. To compute pos(s) we first compute the LF-mapping in M until we reach a marked row s′. Then we compute pos(s′) by finding its corresponding row in M⁰ and computing the LF-mapping in M⁰ (via Lemma 2) until we reach a marked row s′′ in M⁰ (for which pos(s′′) is explicitly available by construction). The marking of T and the counting of the number of marked rows in M that precede a given marked row s′ (this is required in order to determine the position in M⁰ of M[s′]) can be done in constant time and O((u/μ) log log u) bits of storage using again a Packed B-tree and a two level bucketing scheme as before. In addition, for Θ(|T⁰|/η) rows of M⁰ we keep explicitly their positions in T⁰ which take Θ((|T⁰|/η) log u) = Θ(u/log^2ε u) bits of storage. The space occupancy of the procedure for computing the LF-mapping in T̄⁰_bw is given by Lemma 2. Since H_k(T⁰) ≤ H_k(T), a simple algebraic calculation yields that the overall space occupancy is O(H_k(T) + 1/log^2ε u) bits per input symbol, for any fixed k. The time complexity of the algorithm is O(μ) (for finding a marked row in M) plus O(η log^ε u) (for finding a marked row in M⁰), thus O(log^(1/2)+2ε u) time overall.

The final time bound of O(log^ε u) for the computation of pos(s) can be achieved by iterating the approach above as follows. The main idea is to take μ₀ = Θ(log^ε u), and apply the procedure for computing the LF-mapping in T⁰ for Θ(log^ε u) steps, thus identifying a row s₁ of the matrix M⁰ such that pos(s₁) has the form 1 + i μ₁ with μ₁ = Θ(log^2ε u). Next, we define the string T¹ obtained by grouping the characters of T into blocks of size μ₁ and we consider the corresponding matrix M¹. By construction s₁ corresponds to a row in M¹ and we can iterate the above scheme. At the j-th step we operate on the matrix M^j−1 until we find a row s_j such that pos(s_j) has the form 1 + i μ_j where μ_j = Θ(log^(j+1)ε u). This continues until j reaches the value ⌈1/ε⌉. At that point the matrix M^j consists of Θ(u/log^1+ε u) rows and thus we can store explicitly the starting position of their corresponding text suffixes. Summing up, the algorithm computes pos(s) in 1/ε = Θ(1) iterations, each taking Θ(log^2ε u) time. Since ε is an arbitrary positive constant, it is clear that we can rewrite the previous time bound as Θ(log^ε u). The space occupancy is dominated by the one required for the marking of M.

Theorem 3 A text T[1,u] can be indexed so that all the occ occurrences of a pattern P[1,p] in T can be listed in O(p + occ log^ε u) time on a RAM. The space occupancy is O(H_k(T) + (log log u)/(log^ε u)) bits per input symbol, for any fixed k ≥ 0.

Let Δ be a dynamic collection of texts {T₁, T₂, ..., T_m} having arbitrary lengths and total size u. Collection Δ may shrink or grow over the time due to insert and delete operations which allow to add or remove from Δ an individual text string. Our aim is to store Δ in succinct space, perform the update operations efficiently, and support fast searches for the occurrences of an arbitrary pattern P[1,p] into Δ's texts. This problem can be solved in optimal time complexity and Θ(u log u) bits of storage [20, 10]. In the present section we aim at dynamizing our compressed index in order to keep Δ in a reduced space and be able to efficiently support update and search operations. Our result exploits an elegant technique proposed at the beginning of '80 in [25, 21], here adapted to manage items (i.e. texts) of variable lengths.

In the following we bound the space occupancy of our data structure in terms of the entropy of the concatenation of Δ's texts. A better overall space reduction might be possibly achieved by compressing separately the texts T_i's. However, if the texts T_i's have similar statistics the entropy of the concatenated string is a reasonable lower bound to the compressibility of the collection. Furthermore, in the probabilistic setting where we assume that every text is generated by the same probabilistic source, the entropy of the concatenated string coincides with the entropy of the single texts and therefore provides a tight lower bound to the compressibility of the collection.

In the following we focus on the situation in which the length p of the searched pattern is O(u/log² u) because for the other range of p's values, the search operation can be implemented in a brute-force way by first decompressing the text collection and then searching for P into it using a scan-based string matching algorithm thus taking O(p log³ u + occ) time complexity. We partition the texts T_i's into λ = Θ(log² u) collections C₁, ..., C_λ, each containing texts of overall length O(u/log² u). This is always possible, independently of the lengths of the text strings in Δ, since the upper bound on the length of the searchable patterns allows us to split very long texts (i.e. texts of lengths Ω(u/log² u)) into 2 log² u pieces overlapping for Θ(u/log² u) characters. This covering of a single long text with many shorter ones still allows us to find the occurrences of the searched patterns.

Every collection C_h is then partitioned into a series of subsets S^h_i defined as follows: S^h_i contains some texts of C_h having overall length in the range [2ⁱ, 2ⁱ⁺¹), where i = O(log u). Each set S^h_i is simultaneously indexed and compressed using our opportunistic data structure. Searching for an arbitrary pattern P[1,p] in Δ, with p = O(u/log² u) can be performed by searching for P in all the subsets S^h_i via the compressed index built on each of them, thus requiring overall O(p log³ u + occ log^ε u) time.

Inserting a new text T[1,t] into Δ consists of inserting T into one of the sets C_h, the most empty one. Then, the subset S^h_i is selected, where i = ⌊log t⌋, and T is inserted into it using the following approach. If S^h_i is empty then the compressed index is built for T and associated to this subset, thus taking O(t) time. Otherwise the new set S^h_i ∪ {T} is formed and inserted in S^h_i+1. If the latter subset is not empty then the insertion process is propagated until an empty subset S^h_i+j is found. At this point, the compressed index is built over the set S^h_i ∪ ... ∪ S^h_i+j−1 ∪ {T}, by concatenating all the texts contained in this set to form a unique string, texts are separated by a special symbol (as usual). By noticing that these texts have overall length Θ(2^i+j), we conclude that this propagation process has a complexity proportional to the overall length of the moved texts. Although each single insertion may be very costly, we can amortize this cost by charging O(log u) credits per text character (since i, j = O(log u)), thus obtaining an overall amortized cost of O(t log u) to insert T[1,t] in Δ. Some care must be taken to evaluate the space occupied during the reconstruction of the set S^h_i. In fact, the construction of our compressed index over the set S^h_i requires the use of the suffix tree data structure (to compute the BWT) and thus O(2ⁱ log 2ⁱ) bits of auxiliary storage. This could be too much, but we ensured that every collection C_h contains texts having overall length O(u/log² u). So that at most O(u/log u) bits suffices to support any reconstruction process.

We now show how to support text deletions from Δ. The main problem here is that from one side we would like to physically cancel the texts in order to avoid the listing of ghost occurrences belonging to texts no longer in Δ; but from the other side a physical deletion would be too much time-consuming to be performed on-the-fly. Amortization can still be used but much care must be taken when answering a query to properly deal with texts which have been logically deleted from the S^h_i's. For the sake of presentation let T_bw be the BWT of the texts stored in some set S^h_i. We store in a balanced search tree the set I^h_i of interval positions in T_bw occupied by deleted text suffixes. If a pattern occurrence is found in T_bw using our compressed index, we can check in O(log u) time if it is a real or a ghost occurrence. Every time a text T[1,t] must be deleted from S^h_i, we search for all of its suffixes in S^h_i and then update accordingly I^h_i in O(t log u) time. The additional space required to store the balanced search tree is O(|I^h_i| log u) = O(u/log u) bits, where we are assuming to physically delete the texts from S^h_i as soon as a fraction of Θ(1/log² u) suffixes is logically marked. Hence, each set S^h_i may undergo O(log² u) reconstructions before it shrinks enough to move back to the previous set S^h_i−1. Consequently the amortized cost of delete is O(t log u + t log² u) = O(t log² u), where the first term denotes the cost of I^h_i's update and the second term accounts for the credits to be left in order to pay for the physical deletions.

Finally, to identify a text to be deleted we append to every text in Δ an identifier of O(log u) bits, and we keep track of the subset S^h_i containing a text via a table. This introduces an overhead of O(m log u) bits which is o(u) if we reasonably assume that the texts are not too short, i.e. ω(log u) bits each.

Theorem 4 Let Δ be a dynamic collection of texts {T₁, T₂, ..., T_m} having total length u. All the occ occurrences of a pattern P[1,p] in the texts of Δ can be listed in O(p log³ u + occ log u) time in the worst case. Operation insert adds a new text T[1,t] in Δ taking O(t log u) amortized time. Operation delete removes a text T[1,t] from Δ taking O(t log² u) amortized time. The space occupancy is O(H_k(Δ) + (m log u)/u) + o(1) bits per input symbol, for any fixed k ≥ 0.

Glimpse [18] is an effective tool to index linguistic texts. From a high level point of view, it is a hybrid between inverted files and scan-based approaches with no index. It relies on the observation that there is no need to index every word with an exact location (as it occurs in inverted files); but only pointers to an area where the word occurs (called a block) should be maintained. Glimpse assumes that the text T[1,u] is logically partitioned into r blocks of size b each, and thus its index consists of two parts: a vocabulary V containing all the distinct words of the text; and for each word w ∈ V, a list L(w) of blocks where the word w occurs. This blocking scheme induces two space savings: pointers to word occurrences are shorter, and the occurrences of the same word in a single block are represented only once. Typically the index is very compact, 2–4% of the original text size [18].

Given this index structure, the search scheme proceeds in two steps: first the queried word w is searched in V, then all candidate blocks of L(w) are sequentially examined to find all the w's occurrences. More complex queries (e.g. approximate or regular expression searches) can be supported by using Agrep [28] both in the vocabulary and in the block searches. Clearly, the search is efficient if the vocabulary is small, if the query is enough selective, and if the block size is not too large. The first two requirements are usually met in practice, so that the main constraint to the effective use of Glimpse remains the strict relation between block-pointer sizes and text sizes. Theoretical and experimental analysis of such block-addressing scheme [18, 4] have shown that the Glimpse approach is effective only for medium sized texts (roughly up to 200Mb). Recent papers tried to overcome this limitation by compressing each text block individually and then searching it via proper opportunistic string-matching algorithms [18, 24]. The experimental results showed an improvement of about 30–50% in the final performance, thus implicitly proving that the second searching step dominates Glimpse's query performance.

Our opportunistic index naturally fits in this block-addressing framework and allows us to extend its applicability to larger text databases. The new approach, named Compressed Glimpse (shortly CGlimpse), consists of using our opportunistic data structure to index each text block individually; this way, each candidate block is not fully scanned at query time but its index is employed to fasten the detection of the pattern occurrences. In some sense CGlimpse is a compromise between a full-text index (like a suffix array) and a word-based index (like an inverted list) over a compressed text.

A theoretical investigation of the performance of CGlimpse is feasible using a model generally accepted in Information Retrieval [4]. It assumes the Heaps law to model the vocabulary size (i.e. V = O(u^β) with 0 < β < 1), the generalized Zipf's law to model the frequency of words in the text collection (i.e. the i-th largest frequency of a word is u/(i^θ H^(θ)_V), where H^(θ)_V is a normalization term and θ is a parameter larger than 1), and assumes that O(u^γ) is the number of matches for a given word with k ≥ 1 errors (where γ < 1). Under these hypothesis we can show that CGlimpse achieves both sublinear space overhead and sublinear query time independent of the block size (proof in the full paper). Conversely, inverted indices achieve only the second goal [27], and classical Glimpse achieves both goals but under some restrictive conditions on the block size [4].

Various issues remain still to be investigated in various models of computation. In the RAM, it would be interesting to avoid the o(log u) overhead incurred in the listing of the pattern occurrences. This is an open problem also in the uncompressed setting [11]. In external memory, it would be interesting to devise a compressed index which takes advantage of the blocked access to the disk and thus reduces the I/O-complexity of the listing of the pattern occurrences by a factor Θ(B). As far as the problem of counting the number of pattern occurrences is concerned, we are investigating the use of the technique in Lemma 2 to achieve o(p) time bound.

Another interesting issue concerns with the design of word-based indices where the searches are mainly confined to words or prefixes of words. We are investigating a novel word-based compression scheme which compresses the pattern before searching it into the opportunistic data structure thus achieving o(p) I/O-complexity.

Let s be a string of length n over the alphabet Σ = {α₁, ..., α_h}, and let n_i denote the number of occurrences of the symbol α_i inside s. The zeroth order empirical entropy of the string s is defined as

where we assume 0 log 0 = 0. The value |s| H₀(s) represents the output size of an ideal compressor which uses −log (n_i/n) bits for coding the symbol α_i. It is well known that this is the maximum compression we can achieve using a uniquely decodable code in which a fixed codeword is assigned to each alphabet symbol. We can achieve a greater compression if the codeword we use for each symbol depends on the k symbols preceding it. For any length-k word w ∈ Σ^k let w_s denote the string consisting of the characters following w inside s. Note that the length of w_s is equal to the number of occurrences of w in s, or to that number minus one if w is a suffix of s. The value

is called the k-th order empirical entropy of the string s. The value |s| H_k(s) represents a lower bound to the compression we can achieve using codes which depend on the k most recently seen symbols. Not surprisingly, for any string s and k ≥ 0, we have H_k+1(s) ≤ H_k(s). Note that the empirical entropy is defined for any string without any assumption on the input.

For the sake of presentation, let us refer to the matrix M of BWT and concentrate on the computation of sp. By the inductive hypothesis, sp points to the first row of M prefixed by the string P[i,p].

Let M[s] = c P[i,p] τ be the first row in M prefixed by P[i − 1, p] (if any), where τ is an arbitrary string and c = P[i − 1]. Indeed M[s] is the row we are interested in, so that we aim at proving that s = C[c] + Occ(c, 1, sp − 1) + 1.

We rotate cyclically to the left the row M[s] thus obtaining the row M[s′] = P[i,p] τ c, for a proper value s′. By the hypothesis, sp is the first row of M prefixed by P[i,p] and thus sp ≤ s′. From the ordering of the rows in M (see Section 2), s′ must be the first row which follows the position sp and ends with the character c (i.e. L[s′] = c). If this were not the case, then we would have found a row M[t′] having the form P[i,p] σ c with sp ≤ t′ < s′. This way M[t′] would precede lexicographically M[s′] and hence σ would be lexicographically smaller than τ. The row c P[i,p] σ would exist in M and should occur before M[s], thus contradicting the definition of s.

From the properties of LF-mapping (see Section 2), we know that s is equal to C[c] plus the rank of M[s′] among all rows in M ending with the character c. This rank is actually given by Occ(c, 1, sp − 1) + 1, since it equals the number of times the character c occurs in the prefix T_bw[1, sp − 1], plus one unit. This proves the correctness of our formula for updating sp. A similar argument can be used to prove the correctness of the formula for ep, and easily show that the algorithm correctly detects the case in which P[i − 1, p] is not a prefix of any row in M (and therefore does not appear in T).

In this appendix we discuss the computation of Occ(c, 1, k) in the general case in which T_mtf contains one or more runs of zeroes which cross the border of the buckets BT^mtf_i's. Recall that rle replaces each (maximal) run of zeroes 0^m in T_mtf with the string Bin(m) defined as the binary representation of (m + 1) in reverse order (least significant bit first) and with the most significant bit discarded. This encoding is also known as 1/2-encoding since if Bin(m) = b₀ b₁ ... b_k then m = Σ_j=0^k (b_j + 1) 2^j. Because of this property, from Bin(m) we can retrieve 0^m by simply replacing each bit b_j with a sequence of (b_j + 1) 2^j zeroes.

Suppose now that a sequence of a + b zeroes is split between two buckets, let say BT^mtf_i−1 ends with a zeroes and BT^mtf_i starts with b zeroes (a similar argument can be adopted in the case of a sequence overlapping an entire bucket). We define the compressed buckets BZ_i−1 and BZ_i as follows. We know that rle transforms this sequence of zeroes into the string ε = Bin(a + b). We interpret every digit of ε according to the 1/2 decoding scheme mentioned above and we assign to BZ_i−1 the shortest prefix of ε whose 1/2 decoding is greater or equal than a. The remaining digits of ε are assigned to BZ_i. It should be clear that table S introduced in Section 3.2 can be used to count the number of occurrences of a character in a prefix of BZ_i−1 but does not work for BZ_i. Indeed, BZ_i−1 is a faithful encoding of BT^mtf_i−1 whereas the leading b zeroes of BT^mtf_i are usually not faithfully encoded by the digits of ε which we assigned to BZ_i. For this reason we introduce two additional arrays LT[1, u/ℓ] and LZ[1, u/ℓ] defined in such a way that the portion of BT^mtf_i starting from position LT[i] + 1 is faithfully encoded by the portion of BZ_i starting from position LZ[i] + 1 (in our example LT[i] = b). Figure 2 shows the resulting algorithm for the computation of the number of occurrences of c among the first j characters of a compressed bucket BZ_i.

Since the arrays LT and LZ occupy O((u/ℓ) log ℓ) = O((u/log u) log log u) bits, their introduction does not change the asymptotic space occupancy of the procedure Occ.

Let T̄[1,v] denote a string drawn from an alphabet Λ of non-constant size, and let T̄_bw = bwt(T̄). For each j = 0, 1, ..., 2/ε, we construct the string T̄_bw^j by selecting from T̄_bw one out of log^jε v consecutive occurrences of κ, for every character κ ∈ Λ. Moreover, we logically mark the characters of T̄_bw^j which occur in the next string T̄_bw^j+1. Notice that T̄_bw⁰ = T̄_bw and that the length of T̄_bw^j is Θ(v / log^jε v).

Now consider a modified move-to-front procedure, called mtf*, that encodes a character in T̄_bw by the number of characters seen since its previous occurrence. For j = 0, 1, ..., 2/ε, let T̄_mtf*^j = mtf*(T̄_bw^j). We store the strings T̄_mtf*⁰, T̄_mtf*¹, ..., T̄_mtf*^2/ε and, for the characters in T̄_bw^2/ε, we also keep the explicit value of their LF-mapping in the original transformed text T̄_bw.

The high-level idea to compute LF[s] for a character κ = T̄_bw[s] is to use the arrays T̄_mtf*^j's to jump, in Θ((2/ε) log^ε v) = Θ(log^ε v) steps, to an occurrence of κ which is also in T̄_bw^2/ε. For this occurrence we have the explicit LF-mapping and we can easily reconstruct LF[s]. More precisely, we start from T̄_bw⁰[s] and we move to T̄_bw¹, T̄_bw², ..., T̄_bw^2/ε updating a counter v as follows. Let T̄_bw^j[i] be the currently examined character (initially j = 0, i = s and v = 0); if this character κ is marked then we are done and v remains unchanged; otherwise we move to the previous copy of κ in T̄_bw^j using the distance encoded in T̄_mtf*^j[i] and sum log^jε v to the counter v. Note that we are indeed implicitly jumping log^jε v occurrences of the character κ in the original T̄_bw, and thus we account for them in v. We have now reached a marked character κ, thus we can move to its corresponding copy in T̄_bw^j+1. After Θ(log^ε v) iterations, we reach a copy of κ in T̄_bw^2/ε for which its LF-mapping over T̄_bw is available. Consequently, we sum this value with v and thus obtain LF[s] in overall Θ(log^2ε v) time.

Note that in the above scheme we do not need the arrays T̄_bw^j's: we only need to access the values stored in T̄_mtf*⁰, T̄_mtf*¹, ..., T̄_mtf*^2/ε. This is crucial to achieve a sublinear space bound. Let bin(i) denote the binary representation of i + 1 (which takes 1 + ⌊log(i + 1)⌋ bits). We construct the following three arrays for each j = 0, 1, ..., 2/ε:

• Z_j is a string succinctly encoding T̄_mtf*^j and consisting of the concatenation bin(T̄_mtf*^j[1]) bin(T̄_mtf*^j[2]) ... bin(T̄_mtf*^j[v/log^jε v]);
• W_j is a binary array of length |Z_j| such that W_j[i] = 1 iff Z_j[i] is the starting bit-position of the encoding of a value in T̄_mtf*^j;
• N_j is a binary array of length |Z_j| such that N_j[i] = 1 iff W_j[i] = 1 and the corresponding character of T̄_bw^j occurs also in T̄_bw^j+1 (and thus it is marked).

Using the procedures rank and select described in [22] and applied on the arrays above, we can implement each step of the computation of LF[s] described before in O(1) time. Namely, given an encoding of T̄_mtf*^j starting at bit position i, we can check if this corresponds to a marked character κ by accessing N_j[i]. If this is the case we count the number of characters of T̄_bw^j+1 preceding κ (via rank over N_j[1,i]) and finally find the position of the encoding of κ in T̄_mtf*^j+1 (via select on N_j+1). If κ is not marked, then we decode in O(1) time the entry of T̄_mtf*^j starting at the i-th bit of Z_j and then jump to the previous occurrence of κ in T̄_bw^j via rank and select operations over array W_j. In summary, each of these operations takes O(1) time, and this proves the time bound of Lemma 2.

To prove the space bound we first observe that the space occupancy induced by the explicit LF-mapping kept for the characters in T̄_bw^2/ε is O(v/log v) bits (we store O(v/log² v) entries of O(log v) bits each). The arrays Z_j's, W_j's, N_j's and the data structures for the rank and select operations take O(|Z₀| + |Z₁| + ... + |Z_2/ε|) bits of storage, hence O(|Z₀|) bits. The lemma follows since from [6, 19] we can derive the relation |Z₀| = O(v(1 + H_k(T̄)) + |Λ|^k+1 (log |Λ| + log v)).