Search

Finding substrings of a text T that match a regular expression p is a fundamental problem. Despite being the subject of extensive research, no solution with a time complexity significantly better than O(|T||p|) has been found. Backurs and Indyk in FOCS 2016 established conditional lower bounds for the algorithmic problem based on the Strong Exponential Time Hypothesis that helps explain this difficulty. A natural question is whether we can improve the time complexity for matching the regular expression by preprocessing the text T? We show that conditioned on the Online Matrix–Vector Multiplication (OMv) conjecture, even with arbitrary polynomial preprocessing time, a regular expression query on a text cannot be answered in strongly sublinear time, i.e., O(|T|1−ε) for any ε&gt, 0. Furthermore, if we extend the OMv conjecture to a plausible conjecture regarding Boolean matrix multiplication with polynomial preprocessing time, which we call Online Matrix–Matrix Multiplication (OMM), we can strengthen this hardness result to there being no solution with a query time that is O(|T|3/2−ε). These results hold for alphabet sizes three or greater. We then provide data structures that answer queries in O(|T||p|τ) time where τ∈[1,|T|] is fixed at construction. These include a solution that works for all regular expressions with Expτ·|T| preprocessing time and space. For patterns containing only ‘concatenation’ and ‘or’ operators (the same type used in the hardness result), we provide (1) a deterministic solution which requires Expτ·|T|log2|T| preprocessing time and space, and (2) when |p|≤|T|z for z=2o(log|T|), a randomized solution with amortized query time which answers queries correctly with high probability, requiring Expτ·|T|2Ωlog|T| preprocessing time and space.

In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in $$O(|P|+k)$$ time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086–1095, 2008).

In a \emph{weighted sequence}, for every position of the sequence and every letter of the alphabet a probability of occurrence of this letter at this position is specified. Weighted sequences are commonly used to represent imprecise or uncertain data, for example, in molecular biology where they are known under the name of Position-Weight Matrices. Given a probability threshold $\frac1z$, we say that a string $P$ of length $m$ occurs in a weighted sequence $X$ at position $i$ if the product of probabilities of the letters of $P$ at positions $i,\ldots,i+m-1$ in $X$ is at least $\frac1z$. In this article, we consider an \emph{indexing} variant of the problem, in which we are to preprocess a weighted sequence to answer multiple pattern matching queries. We present an $O(nz)$-time construction of an $O(nz)$-sized index for a weighted sequence of length $n$ over a constant-sized alphabet that answers pattern matching queries in optimal, $O(m+Occ)$ time, where $Occ$ is the number of occurrences reported. The cornerstone of our data structure is a novel construction of a family of $\lfloor z \rfloor$ special strings that carries the information about all the strings that occur in the weighted sequence with a sufficient probability. We obtain a weighted index with the same complexities as in the most efficient previously known index by Barton et al. (CPM 2016), but our construction is significantly simpler. The most complex algorithmic tool required in the basic form of our index is the suffix tree which we use to develop a new, more straightforward index for the so-called property matching problem. We provide an implementation of our data structure. Our construction allows us also to obtain a significant improvement over the complexities of the approximate variant of the weighted index presented by Biswas et al. (EDBT 2016) and an improvement of the space complexity of their general index., A new, even simpler version of the index

Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and links for suffix tries in the worst case because of their unary nodes. It is an interesting question if the suffix trie can be stored using O ( n ) nodes. We present the linear-size suffix trie, which guarantees O ( n ) nodes. We use a new technique for reducing the number of unary nodes to O ( n ) , that stems from some results on antidictionaries. For instance, by using the linear-size suffix trie, we are able to check whether a pattern p of length m = | p | occurs in w in O ( m log ⁡ | Σ | ) time and we can find the longest common substring of two strings w 1 and w 2 in O ( ( | w 1 | + | w 2 | ) log ⁡ | Σ | ) time for an alphabet Σ.

We present an index that stores a text of length n such that given a pattern of length m, all the substrings of the text that are within Hamming distance (or edit distance) at most k from the pattern are reported in O(m+loglogn+#matches) time (for constant k). The space complexity of the index is O(n1+ϵ) for any constant ϵ>0.

Operations rank and select over a sequence of symbols have many applications to the design of succinct and compressed data structures managing text collections, structured text, binary relations, trees, graphs, and so on. We are interested in the case where the collections can be updated via insertions and deletions of symbols. Two current solutions stand out as the best in the tradeoff of space versus time (when considering all the operations). One solution, by Makinen and Navarro, achieves compressed space (i.e., nH"0+o([email protected]) bits) and O([email protected]) worst-case time for all the operations, where n is the sequence length, @s is the alphabet size, and H"0 is the zero-order entropy of the sequence. The other solution, by Lee and Park, achieves O(logn([email protected])) amortized time and uncompressed space, i.e. nlog"[email protected]+O(n)+o([email protected]) bits. In this paper we show that the best of both worlds can be achieved. We combine the solutions to obtain nH"0+o([email protected]) bits of space and O(logn([email protected])) worst-case time for all the operations. Apart from the best current solution to the problem, we obtain several byproducts of independent interest applicable to partial sums, text indexes, suffix arrays, the Burrows-Wheeler transform, and others.

In this paper we study the problem of estimating the number of occurrences of substrings in textual data: A text $$T$$T on some alphabet $$\varSigma =[\sigma ]$$Σ=[?] of length $$n$$n is preprocessed and an index $${\mathcal {I}}$$I is built. The index is used in lieu of the text to answer queries of the form $$\mathsf{Count}\approx (P)$$Count?(P), returning an approximated number of the occurrences of an arbitrary pattern $$P$$P as a substring of $$T$$T. The problem has its main application in selectivity estimation related to the LIKE predicate in textual databases. Our focus is on obtaining an algorithmic solution with guaranteed error rates and small footprint. To achieve that, we first enrich previous work in the area of compressed text-indexing providing an optimal data structure that, for a given additive error $$\ell \ge 1$$l?1, requires $$\varTheta \left( \frac{n}{\ell }\log \sigma \right) $$?nllog? bits. We also approach the issue of guaranteeing exact answers for sufficiently frequent patterns, providing a data structure whose size scales with the amount of such patterns. Our theoretical findings are supported by experiments showing the practical impact of our data structures.

Edited by Maxime Crochemore, Jacqueline W. Daykin and Zsuzsanna Lipták; International audience; Invented in the 70's, the Suffix Tree (ST) is a data structure that indexes all substrings of a text in linear space. Although more space demanding than other indexes, the ST remains an inspiring index likely because it represents substrings in a hierarchical tree structure. Along time, STs have acquired a central position in text algorithmics with myriad of algorithms and applications to for instance motif discovery, biological sequence comparison, or text compres-sion. It is well known that different words can lead to the same suffix tree structure with different labels. Moreover, the properties of STs prevent all tree structures from being STs. Even the suffix links, which play a key role in efficient construction algorithms and many ap-plications, are not sufficient to discriminate the suffix trees of distinct words. The question of recognising which trees can be STs has been raised and termed Reverse Engineering on STs. For the case where a tree is given with potential suffix links, a seminal work provides a linear time solution only for binary alphabets. Here, we also investigate the Reverse Engineering problem on ST with links and exhibit a novel approach and algorithm. Hopefully, this new suffix tree characterisation makes up a valuable step towards a better understanding of suffix tree combinatorics. * This work is supported by ANR Colib'read (ANR-12-BS02-0008) and Défi MASTODONS SePhHaDe from CNRS.

We investigate the problem of maintaining the arc labels in the suffix tree data structure (Gusfield et al., 1992; Amir et al., 1994) when it undergoes string insertions and deletions. In current literature, this problem is solved either by a simple accounting strategy to obtain amortized bounds (Fiala and Green, 1989; Larson, 1996) or by a periodical suffix tree reconstruction to obtain worst-case bounds (according to the global rebuilding technique in Overmars, 1983). Unfortunately, the former approach is simple and space efficient at the cost of attaining amortized bounds for the single update; the latter is space consuming, in practice, because it needs to keep two extra suffix tree copies. In this paper, we obtain a simple realtime algorithm that achieves worst-case bounds and only requires small additional space (i.e., a bi-directional pointer per suffix tree label). We analyze it by introducing a combinatorial coloring problem on the suffix tree arcs.

Suffix tree is one of the most important data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length n from alphabet Σ = { A , C , G , T } can be stored in n log |Σ| = 2 n bits, its suffix tree occupies O ( n log n ) bits. In practice, the size difference easily reaches factor 50. We report on an implementation of the compressed suffix tree very recently proposed by Sadakane (2007). The compressed suffix tree occupies space proportional to the text size, that is, O ( n log |Σ|) bits, and supports all typical suffix tree operations with at most log n factor slowdown. Our experiments show that, for example, on a 10 MB DNA sequence, the compressed suffix tree takes 10% of the space of the normal suffix tree. At the same time, a representative algorithm is slowed down by factor 30. Our implementation follows the original proposal in spirit, but some internal parts are tailored toward practical implementation. Our construction algorithm has time requirement O ( n log n log |Σ|) and uses closely the same space as the final structure while constructing it: on the 10MB DNA sequence, the maximum space usage during construction is only 1.5 times the final product size. As by-products, we develop a method to create Succinct Suffix Array directly from Burrows-Wheeler transform and a space-efficient version of the suffixes-insertion algorithm to build balanced parentheses representation of suffix tree from LCP information.

Let S be a string over a finite, ordered alphabet @S. For any substring S^' of S, the set of distinct characters contained in S^' is called its fingerprint. The text fingerprinting indexing problem is to construct a data structure for the string S in advance, so that on given any input subset C of @S, we can answer the following queries efficiently: (1) determine if C represents a fingerprint of some substrings in S; (2) find all maximal substrings of S whose fingerprint is C. The best known results solved these two queries in @Q(|@S|) and @Q(|@S|+K) time, respectively, where K is the number of maximal substrings. In this paper, we propose two improved algorithms for the text fingerprinting indexing problem. The first one solves the two queries in O(|C|logn) and O(|C|logn+K) time, respectively. For the second one, the query time complexities are further reduced to O(|C|log(|@S|/|C|)) and O(|C|log(|@S|/|C|)+K). Both results answer an open problem proposed by Amir et al.

Suffix arrays are a key data structure for solving a run of problems on texts and sequences, from data compression and information retrieval to biological sequence analysis and pattern discovery. In their simplest version, they can just be seen as a permutation of the elements in {1,2,…,n}, encoding the sorted sequence of suffixes from a given text of length n, under the lexicographic order. Yet, they are on a par with ubiquitous and sophisticated suffix trees. Over the years, many interesting combinatorial properties have been devised for this special class of permutations: for instance, they can implicitly encode extra information, and they are a well characterized subset of the n! permutations. This paper gives a short tutorial on suffix arrays and their compressed version to explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression.

Given a sequence S = s 1 s 2 … s n of integers smaller than r = O (polylog( n )), we show how S can be represented using nH 0 ( S ) + o ( n ) bits, so that we can know any s q , as well as answer rank and select queries on S , in constant time. H 0 ( S ) is the zero-order empirical entropy of S and nH 0 ( S ) provides an information-theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O (log r ) time. For larger r , we can still represent S in nH 0 ( S ) + o ( n log r ) bits and answer queries in O (log r /log log n ) time. Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet Σ. Specifically, we design a variant of the FM-index that indexes a string T [1, n ] within nH k ( T ) + o ( n ) bits of storage, where H k ( T ) is the k th-order empirical entropy of T . This space bound holds simultaneously for all k ≤ α log |Σ| n , constant 0 < α < 1, and |Σ| = O (polylog( n )). This index counts the occurrences of an arbitrary pattern P [1, p ] as a substring of T in O ( p ) time; it locates each pattern occurrence in O (log 1+ε n ) time for any constant 0 < ε < 1; and reports a text substring of length ℓ in O (ℓ + log 1+ε n ) time. Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the k th-order entropy of the text T , which is the best space obtained in previous work. We can also handle larger alphabets of size |Σ| = O ( n β ), for any 0 < β < 1, by paying o ( n log|Σ|) extra space and multiplying all query times by O (log |Σ|/log log n ).