Generalized suffix array

In computer science, a generalized suffix array (or 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.

Functionality

• Let {$S=S_{1},S_{2},S_{3},...,S_{k}$}.
• Lexicographically sorted array of all suffixes of each string in $S$.
• Each suffix is represented by an integer pair $(i,j)$ denoting suffix starting from position j in $s_{i}$.
• If suffixes from different strings within $S$ are identical, they occupy consecutive positions in the generalized suffix array. However, for convenience, the exception can be made of only listing repeats once.

A generalized suffix array can be generated for a generalized suffix tree. Compared to a generalized suffix tree, a generalized suffix array can be constructed in that it will use less space than the tree, the only drawback is it will require more time to construct.

Algorithms and Implementations

Algorithms and tools for constructing a generalized suffix array include:

• Fei Shi's (1996) algorithm which runs in $\Theta (nlogn)$ time with a worst case of $\Theta (n)$ and includes sorting, searching and finding the longest common prefixes
• The external generalized enhanced suffix array (eGSA) construction algorithm which resembles a two-phase multiway merge sort specializes in external memory construction when the size of the input collection or data structure exceed the amount of internal memory
• gsufsort is fast, portable, lightweight tool for constructing generalized suffix arrays and related data structures ;ole Burrows Wheeler transform or LCP Array)

Solving the Pattern Matching Problem

Generalized suffix arrays can be used to solve the pattern matching problem:

• Given the pattern $P$ and a text $T$, find all occurrences of $P$ in $T$.
• If the generalized suffix array, $G$, of $T$ is available, then first, the suffixes that have $P$ as a prefix need to be found.
• Since $G$ is a lexicographically sorted order of the suffixes of $T$, all such suffixes will appear in consecutive positions in it. Furthermore, the sorted order attribute of G allows for easy identification of the suffixes using binary search.
• Using binary search, find the smallest index $i$ in $G$ such that $G$ such that $suff_{G}[i]$ contains $P$ as a prefix, or determine that no such suffix is present. If no suffix is found, $P$ does not occur in $T$. Otherwise, find the largest index $j(\geq i)$ contains $P$ as a prefix. All the elements in the range $G[i..j]$ give the starting positions of the occurrences of $P$ in $T$.
• Binary search in $G$ takes $\Theta (logn)$ comparisons. In each comparison, $P$ is compared with a suffix to determine their lexicographic order. This requires comparing at most $|P|=m$ characters. An $lcp$ array is not required, but having one will benefit running time.
• Thus, the runtime of the algorithm is $\Theta (mlogn)$. By comparison, solving this problem using suffix trees takes $\Theta (m)$ time, however the space is smaller utilizing suffix arrays since the space required by the algorithm is only $n$ words, in addition to the space required to store the string. By keeping track of $lcp$ information and using slightly more space, running time can be improved to $\Theta (m+logn)$.

Other Applications

• A generalized suffix array can be used to compete the longest common subsequence of the strings in the set in linear time, whereas a naive implementation would compute this information in quadratic time.
• Create the Longest Previous Factor array used in text compression and for detecting motifs, repeats

See Also

• Suffix Tree
• Suffix Array
• Generalized Suffix Tree