A Taxonomy of Suffix Array Construction Algorithms
Simon Puglisi
Department of Computing,
Curtin University of Technology,
Perth, Australia
Bill Smyth
Department of Computer Science,
McMaster University,
Canada.
Andrew Turpin
School of Computer Science and Information Technology,
RMIT University,
Melbourne, Australia.
Status
Invited talk by Prof W. F. Smyth at the
Prague Stringology Conference '05, the
10th event of the Prague Stringology Club. August 2005
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.
We also 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.