In this paper we study the structure of suffix trees. Given an unlabeled tree @math on @math nodes and suffix links of its internal nodes, we ask the question "Is @math a suffix tree?", i.e., is there a string @math whose suffix tree has the same topological structure as @math ? We place no restrictions on @math , in particular we do not require that @math ends with a unique symbol. This corresponds to considering the more general definition of implicit or extended suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. We prove that @math is a suffix tree if and only if it is realized by a string @math of length @math , and we give a linear-time algorithm for inferring @math when the first letter on each edge is known. This generalizes the work of [Discrete Appl. Math. 163, 2014].
The problem of revealing structural properties and exploiting them to recover a string realizing a data structure has received a lot of attention in the literature. Besides @math $-suffix trees, the problem has been considered for border arrays @cite_19 @cite_12 , parameterized border arrays @cite_8 @cite_0 @cite_9 , suffix arrays @cite_13 @cite_14 @cite_4 , KMP failure tables @cite_2 @cite_16 , prefix tables @cite_17 , cover arrays @cite_1 , directed acyclic word graphs @cite_13 , and directed acyclic subsequence graphs @cite_13 .
@cite_14 @cite_4 @cite_8 @cite_9 @cite_1 @cite_0 @cite_19 @cite_2 @cite_16 @cite_13 @cite_12 @cite_17
2141957180 2158874082 2522621913 1874135322
Given a set @math of @math strings of total length @math , our task is to report the "most relevant"strings for a given query pattern @math . This involves somewhat more advanced query functionality than the usual pattern matching, as some notion of "most relevant" is involved. In information retrieval literature, this task is best achieved by using inverted indexes. However, inverted indexes work only for some predefined set of patterns. In the pattern matching community, the most popular pattern-matching data structures are suffix trees and suffix arrays. However, a typical suffix tree search involves going through all the occurrences of the pattern over the entire string collection, which might be a lot more than the required relevant documents. The first formal framework to study such kind of retrieval problems was given by [Muthukrishnan, 2002]. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures taking @math words of space. We study this problem in a slightly different framework of reporting the top @math most relevant documents (in sorted order) under similar and more general relevance metrics. Our framework gives linear space data structure with optimal query times for arbitrary score functions. As a corollary, it improves the space utilization for the problems in [Muthukrishnan, 2002] while maintaining optimal query performance. We also develop compressed variants of these data structures for several specific relevance metrics. A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, “Is W a substring of A?” to be answered in time @math , where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in @math time in the worst case, versus @math time for suffix arrays. However, an augmented algorithm is given that, regardless of the alphabet size, constructs suffix arrays in @math expected time, albeit with lesser space efficiency. It is ... The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string @math can be built in deterministic @math time using just @math bits of space, where @math . Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of @math . Many fundamental string analysis problems can be mapped to such enumeration, and can thus be solved in deterministic @math time and in @math bits of space from the input string. We also show how to build many of the existing indexes based on the BWT, such as the CSA, the compressed suffix tree (CST), and the bidirectional BWT index, in randomized @math time and in @math bits of space. The previously fastest construction algorithms for BWT, CSA and CST, which used @math bits of space, took @math time for the first two structures, and @math time for the third, where @math is any positive constant. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output. This paper introduces a new problem of inferring strings from graphs, and inferring strings from arrays. Given a graph G or an array A, we infer a string that suits the graph, or the array, under some condition. Firstly, we solve the problem of finding a string w such that the directed acyclic subsequence graph (DASG )o fw is isomorphic to a given graph G. Secondly, we consider directed acyclic word graphs (DAWGs) in terms of string inference. Finally, we consider the problem of finding a string w of a minimal size alphabet, such that the suffix array (SA )o f w is identical to a given permutation p = p1 ,...,p n of integers 1 ,...,n . Each of our three algorithms solving the above problems runs in linear time with respect to the input size.