Suffix Array
Subject: Computer and Technology noun /ˈsʌf.ɪks əˈreɪ/ 1 definition
- data-structures
- string-processing
- search-algorithms
- computer-science
-
Definition (noun)
Entry #280 · UpdatedA Suffix Array is a space-efficient string-indexing data structure consisting of an integer array that stores the starting offsets of every suffix of a text sorted in lexicographical order. Constructed in
O(n)orO(n log n)time using algorithms such as induced sorting (SA-IS) or prefix doubling, it arranges all suffixes into a single contiguous array so that every occurrence of any matching substring occupies a consecutive index range. Because every substring of a text is a prefix of at least one suffix, binary search locates all occurrences of a pattern of lengthminO(m log n)time—orO(m + log n)time when paired with a Longest Common Prefix (LCP) array—using far less memory than pointer-heavy suffix trees. Its primary purpose and boundary lie in static or batch-built text indexing, bioinformatics, and data compression where compact memory footprint and CPU cache locality matter most, as suffix arrays do not natively support incremental character insertions or deletions without rebuilding the index.Common Types
Standard Suffix Array: Stores only the sorted suffix starting offsets for a single string in a flat integer array, supporting
O(m log n)binary-search substring queries with minimal structural overhead.Enhanced Suffix Array (ESA): Pairs the suffix array with auxiliary tables—such as the Longest Common Prefix (LCP) array and child tables—to simulate full suffix-tree traversals and achieve
O(m)pattern matching for constant-size alphabets without pointer overhead.Compressed Suffix Array (CSA): Encodes suffix-order relationships using rank/select bitvectors, wavelet trees, or Burrows-Wheeler Transform (FM-index) structures to shrink space consumption from
O(n log n)bits down toward the text's empirical entropy.Generalized Suffix Array (GSA): Indexes all suffixes across a collection of multiple concatenated strings separated by distinct sentinels, enabling cross-document substring search, longest common substring discovery, and multi-sequence genomic alignment.
Example
A genomic read-alignment engine indexes the sentinel-terminated DNA sequence
"ACGTAC$"into the suffix array[6, 4, 0, 5, 1, 2, 3], sorting every suffix from"$"(6) through"TAC$"(3). When a query searches for the motif"AC", binary search narrows directly onto the contiguous slice[4, 0], returning both match offsets (0and4) without traversing pointer-heavy tree nodes.