Introduction

In 1990, the concept of suffix arrays was introduced by Udi Manber and Gene Myers as a new data structure for efficiently searching large bodies of text. The original paper titled "Suffix arrays: A new method for on-line string searches" is considered foundational in the field of string processing. However, like many pioneering works, it contains some errata that researchers should be aware of. This article clarifies these errata, providing deeper insights and corrections alongside technical explanations.

Overview of Suffix Arrays

Suffix arrays are a space-efficient alternative to suffix trees. They store all suffixes of a string sorted lexicographically. This sorted array of suffixes allows for efficient pattern matching and string processing tasks. Given a string $S$ of length $n$, a suffix array $SA$ is defined such that $SA[i]$ stores the starting index of the $i$-th smallest suffix of $S$ in lexicographic order.

For example, the string "banana" has suffixes: "banana", "anana", "nana", "ana", "na", "a". Sorted lexicographically, the suffix array is $[5, 3, 1, 0, 4, 2]$, corresponding to "a", "ana", "anana", "banana", "na", "nana".

Errata in the Original Paper

1. Incorrect Time Complexity Notation

Issue: The original paper states that suffix array construction requires $O(n \log n)$ time, with $n$ being the length of the string. This bound arises from comparison-based sorting of suffixes using the algorithm described in the paper.

Correction: While the $O(n \log n)$ bound is correct for the algorithm presented in the paper, subsequent research demonstrated that suffix arrays can be constructed in $O(n)$ time. Linear-time algorithms include the DC3/skew algorithm by Karkkainen, Sanders, and Burkhardt (2003) and the SA-IS algorithm by Nong, Zhang, and Chan (2009). The original paper did not anticipate these advances, and readers should not interpret $O(n \log n)$ as a fundamental lower bound for suffix array construction.

Explanation: The original construction sorts suffixes by repeatedly doubling the comparison length, achieving $O(n \log n)$ comparisons. Later algorithms use induced sorting and recursive decomposition to eliminate the $\log n$ factor entirely.

2. Misinterpretation of Space Requirements

Issue: The paper implies that suffix arrays are significantly more space-efficient alternatives to suffix trees, which may lead to overly optimistic expectations about memory usage.

Correction: Suffix arrays do use less space than suffix trees in practice. A suffix tree typically requires 10 to 20 times the text size, while a basic suffix array requires $4n$ bytes (one 32-bit integer per suffix) or $8n$ bytes with 64-bit integers. However, for practical pattern matching, suffix arrays are often augmented with a Longest Common Prefix (LCP) array (another $4n$ bytes) and possibly inverse suffix arrays. The combined structures use roughly $12n$ to $16n$ bytes, which is still less than suffix trees but more than the paper might suggest.

Additional Insight: The advent of compressed suffix arrays (such as the FM-index) later achieved space usage close to the entropy of the text while maintaining efficient query times, representing a much larger space improvement than classical suffix arrays alone.

3. Ambiguities in Radix Sort Description

Issue: The paper describes using radix sort to achieve the $O(n \log n)$ construction time, but the description of how radix sort applies to suffix sorting contains ambiguities regarding alphabet size dependencies.

Correction: The $O(n \log n)$ bound assumes a constant-sized alphabet $\Sigma$. For integer alphabets of arbitrary size, an initial renaming step is needed to map characters to a range of $[0, n)$, after which radix sort proceeds in $O(n)$ per round. The original paper does not clearly articulate this dependency. For large alphabets (such as Unicode), this renaming step adds a one-time $O(n \log n)$ cost for comparison-based initial sorting.

Example: For DNA sequences with $|\Sigma| = 4$, radix sort is straightforward. For natural language text with $|\Sigma|$ in the thousands, the alphabet must first be compressed.

Clarifications on Algorithm Design

• Suffix Array Initialization: The paper assumes 1-based indexing in some places and 0-based in others. Modern implementations consistently use 0-based indexing.
• LCP Array: The construction of the LCP array, essential for operations like finding the longest repeated substring and performing range minimum queries for pattern matching, was not comprehensively detailed in the original paper. Kasai's algorithm (2001) later provided an $O(n)$ method for LCP construction from the suffix array.

Key Points Summary

Further Considerations

Practical Implementations

In practice, many libraries provide optimized suffix array implementations. The divsufsort library is widely regarded as one of the fastest practical implementations, using a combination of induced sorting and multikey quicksort. For bioinformatics applications, the SA-IS algorithm is popular due to its linear time guarantee and reasonable constant factors.

Broader Implications

Understanding the caveats of the original paper is important for researchers and practitioners. Erroneous assumptions about complexity and space can lead to suboptimal algorithm choices in systems built on these data structures.

Summary

The errata in the original suffix array paper concern the time complexity of construction (not a fundamental $O(n \log n)$ lower bound), space requirements (augmented structures add overhead), and ambiguities in the radix sort description (alphabet size matters). Recognizing these corrections is crucial for utilizing suffix arrays effectively. As with many foundational works, subsequent research has both corrected and extended the original contributions significantly.