Generalized suffix array

In computer science, a generalized suffix array (GSA) is a suffix array containing all suffixes for a set of strings. Given the set of strings S = S_1, S_2, S_3, ..., S_k of total length n , it is a lexicographically sorted array of all suffixes of each string in S . It is primarily used in bioinformatics and string processing.

In computer science, a generalized suffix array (GSA) is a suffix array containing all suffixes for a set of strings. Given the set of strings S = S_1, S_2, S_3, ..., S_k of total length n , it is a lexicographically sorted array of all suffixes of each string in S . It is primarily used in bioinformatics and string processing. For a collection or set of strings, S = S_1, S_2, S_3, ..., S_k . It is a lexicographically sorted array of all suffixes of each string in the set S . In the array, each suffix is represented by an integer pair (i, j) which denotes the suffix starting from position j in s_i . In the case where different strings in S have identical suffixes, in the generalized suffix array, those suffixes will occupy consecutive positions. However, for convenience, the exception can be made where repeats will not be listed. A generalized suffix array can be generated for a generalized suffix tree. When compared to a generalized suffix tree, while the generalized suffix array will require more time to construct, it will use less space than the tree. Binary search on G takes \Theta (log n) comparisons. P is compared with a suffix to determine their lexicographic order in each comparison that is done. Thus, this requires comparing at most |P| = m characters. Note that a lcp array is not required, but will offer the benefit of a lower running time. The runtime of the algorithm is \Theta (m log n) . By comparison, solving this problem using suffix trees takes \Theta (m) time. Note that with a generalized suffix array, the space required is smaller compared to a suffix tree, since the algorithm only requires space for n words and the space to store the string. As mentioned above, by optionally keeping track of lcp information which will use slightly more space, the running time of the algorithm can be improved to \Theta (m+log n) .

External links

Generalized enhanced suffix array construction in external memory

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370131643 under CC BY-SA 4.0; modifications have been made.