✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-203

Suffix 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.

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.

Example or application

Text

BANANA$

Suffixes In Sorted Order

IndexSuffix

6

$

5

A$

3

ANA$

1

ANANA$

0

BANANA$

4

NA$

2

NANA$

Suffix Array

  • 6

  • 5

  • 3

  • 1

  • 0

  • 4

  • 2

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