concept · INFO-CS-ADS-203Suffix Arrays
Learn how suffix arrays store the starting positions of a string's suffixes in lexicographical order to support efficient substring searching and text analysis.
Explanation
Overview
A Suffix Array is an array of integers that represents the starting positions of all suffixes of a text, arranged in lexicographical order. Instead of storing complete suffix strings in a tree, it stores their starting indices, making it a compact alternative for many string-indexing tasks.
Key concepts
Suffixes; Lexicographical ordering; Suffix indexing; Prefix doubling; Binary search; Longest Common Prefix
Variables
text: The original string being indexed.; n: The length of the text.; SA: The suffix array containing sorted suffix starting positions.; SA[i]: The starting index of the suffix at sorted position i.; LCP: The Longest Common Prefix array, which records common-prefix lengths between adjacent sorted suffixes.
Complexity
naiveConstruction: Typically O(n^2 log n) time when comparing suffix strings directly, with potentially O(n^2) storage for materialized suffixes.; prefixDoubling: Common implementations achieve O(n log n) time with efficient sorting and ranking techniques.; patternSearch: O(m log n) character-comparison time in a straightforward binary-search approach, where m is the pattern length.; space: O(n) for the suffix array, excluding auxiliary construction structures.
Example
text: BANANA$; suffixesInSortedOrder: index: 6; suffix: $; index: 5; suffix: A$; suffixArray: 6; 5; explanation: Every suffix is ordered alphabetically, and the suffix array stores only its starting index.
Pseudocode
function buildSuffixArray(text):
suffixes = []
for i = 0 to length(text) - 1:
suffixes.append((text[i to end], i))
sort suffixes lexicographically by suffix
SA = []
for item in suffixes:
SA.append(item.index)
return SA
Applications
Full-text indexing.; Genome sequence analysis.; Repeated substring detection.; Text compression.; Search engines.; Large-scale string processing.
Variables
Text
The original string being indexed.
SA
The suffix array containing sorted suffix starting positions.
SA[i]
The starting index of the suffix at sorted position i.
LCP
The Longest Common Prefix array, which records common-prefix lengths between adjacent sorted suffixes.
Example or application
Suffixes In Sorted Order
| Index | Suffix |
|---|
6 | $ |
5 | A$ |
3 | ANA$ |
1 | ANANA$ |
0 | BANANA$ |
4 | NA$ |
2 | NANA$ |
Explanation
Every suffix is ordered alphabetically, and the suffix array stores only its starting index.
Definition
A Suffix Array is an array of integers that represents the starting positions of all suffixes of a text, arranged in lexicographical order. Instead of storing complete suffix strings in a tree, it stores their starting indices, making it a compact alternative for many string-indexing tasks.
Mathematical Representation
SA[i] = the starting position of the i-th lexicographically smallest suffix of the text.
Construction Methods
Naive
Generate every suffix and sort them lexicographically. This is easy to understand but can require substantial time and memory.
Prefix Doubling
Sort suffixes using progressively larger prefix lengths, doubling the comparison length at each stage.
Advanced
Specialized algorithms can construct suffix arrays in linear or near-linear time under suitable assumptions.
Common Operations
Construction
Build an array containing the starting positions of suffixes in sorted order.
Pattern Search
Use binary search to locate the range of suffixes beginning with a given pattern.
Longest Repeated Substring
Use adjacent suffixes and their LCP values to identify repeated prefixes.
Longest Common Substring
Combine suffix arrays and LCP information from multiple strings with suitable separators.
Pseudocode
function buildSuffixArray(text):
suffixes = []
for i = 0 to length(text) - 1:
suffixes.append((text[i to end], i))
sort suffixes lexicographically by suffix
SA = []
for item in suffixes:
SA.append(item.index)
return SA
Complexity
Naive Construction
Typically O(n^2 log n) time when comparing suffix strings directly, with potentially O(n^2) storage for materialized suffixes.
Prefix Doubling
Common implementations achieve O(n log n) time with efficient sorting and ranking techniques.
Pattern Search
O(m log n) character-comparison time in a straightforward binary-search approach, where m is the pattern length.
Space
O(n) for the suffix array, excluding auxiliary construction structures.
Key Concepts
Suffixes
Lexicographical ordering
Suffix indexing
Prefix doubling
Binary search
Longest Common Prefix
Text indexing
Advantages
Usually more memory-efficient than a suffix tree.
Supports efficient substring searching.
Can identify repeated substrings using LCP information.
Provides a useful foundation for advanced text indexes.
Can be constructed using efficient sorting-based algorithms.
Limitations
Naive construction can be expensive.
Pattern searches may require additional LCP or acceleration structures for better performance.
The array itself does not directly store the suffix strings.
Advanced construction and indexing methods can be difficult to implement.
Applications
Full-text indexing.
Genome sequence analysis.
Repeated substring detection.
Text compression.
Search engines.
Large-scale string processing.
Related Topics
Suffix Trees
Trie Data Structure
LCP Array
String Algorithms
Practice Question
What does each element of a suffix array represent?
Practice Answer
The starting index of a suffix in lexicographical order.
Learning Objectives
Explain the central idea and purpose of suffix arrays.
Identify the assumptions, inputs, and conditions relevant to suffix arrays.
Evaluate an application of suffix arrays for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- String Algorithms and Pattern Matching
Suggest a correction or source · More in Algorithms & Data Structures