China Science

In 1990, Manber and Myers proposed suffix arrays as a space-savingalternative to suffix trees and described the first algorithms for suffix array construction anduse. Since that time, and especially in the last few years, suffix array construction algorithmshave proliferated in bewildering abundance. This survey paper attempts to provide simple high-leveldescriptions of these numerous algorithms that highlight both their distinctive features and theircommonalities, while avoiding as much as possible the complexities of implementation details. Newhybrid algorithms are also described. We provide comparisons of the algorithms’ worst-case timecomplexity and use of additional space, together with results of recent experimental test runs onmany of their implementations.

SIMON J. PUGLISI　W. F. SMYTH　ANDREW H. TURPIN
School of Computer Science and Information Technology, RMIT University, GPOBox 2476V, Melbourne V 3001, Australia

suffix array　 suffix tree suffix sorting burrows-wheeler transform