A Taxonomy of Suffix Array Construction Algorithms
đź“ś Abstract
In 1990 Manber & Myers proposed suffix arrays as a space-saving alternative to suffix trees and described the first algorithms for suffix array construction and use. Since that time, and especially in the last few years, suffix array construction algorithms have proliferated in bewildering abundance. This survey paper attempts to provide simple high-level descriptions of these numerous algorithms that highlight both their distinctive features and their commonalities, while avoiding as much as possible the complexities of implementation details. New hybrid algorithms are also described. We provide comparisons of the algorithms’ worst-case time complexity and use of additional space, together with results of recent experimental test runs on many of their implementations.
✨ Summary
Overview
This survey organizes suffix array construction algorithms into three principal families: prefix-doubling, recursive, and induced-copying methods. Prefix-doubling algorithms repeatedly refine partial suffix orderings and generally require (O(n\log n)) worst-case time. Recursive algorithms reduce construction to sorting a smaller derived string and can achieve linear worst-case time. Induced-copying algorithms completely sort a selected subset of suffixes and use that order to induce the remaining suffixes; they are typically lightweight and fast in practice, although several have superlinear worst-case bounds.
The paper introduces a common vocabulary for comparing these algorithms, including h-orderings, h-groups, approximate suffix arrays, inverse suffix arrays, and longest-common-prefix statistics. It also describes hybrid algorithms that combine prefix-doubling, recursive sampling, and induced copying. The experimental comparison found that the practical leaders in the tested implementations were the induced-copying algorithms MP and M, with MP reported as the fastest or tied for fastest across the test corpus while using close to the minimum storage required for the input and suffix array. The study also found that theoretically linear recursive algorithms could be slower in practice because of memory-use and cache-behavior costs. The central unresolved design goal identified by the paper was a suffix-array construction algorithm that is simultaneously lightweight, worst-case linear, and fast in practice.
Influence
The paper has functioned as a reference survey for subsequent work on suffix-array construction and related text-indexing algorithms. Later research continues to use its classification of construction strategies—particularly prefix doubling, recursion, and induced sorting—as background for new algorithms and analyses. For example, later work on formally verified suffix-array construction cites the survey when situating newer algorithms within the established construction literature. (link.springer.com)
Its terminology and taxonomy have also been propagated into reference material on suffix arrays, including the U.S. National Institute of Standards and Technology’s Dictionary of Algorithms and Data Structures, which cites the paper as a source for suffix-array construction information. (xlinux.nist.gov) Bibliographic records identify the journal version as a 2007 ACM Computing Surveys article and the earlier version as a 2005 Prague Stringology Conference paper, indicating that the work served both as a conference survey and as a later expanded journal reference. (researchportal.murdoch.edu.au)