The Performance of Linear Time Suffix Sorting Algorithms

Simon Puglisi Department of Computing Curtin University of Technology Perth, Australia

Bill Smyth
Department of Computer Science, McMaster University, Canada.

Andrew Turpin
Department of Computer Science and Software Engineering, The University of Melbourne, Parkville 3052, Australia.

Status

Abstract

We compare several linear and non-linear time algorithms for sorting suffixes. We suggest several improvements to the linear time suffix array construction algorithms, but they are still slower in practice than the O(n^2log n) algorithms.

The algorithms involved are:

Stefan Burkhardt and Juha Karkkainen, Fast lightweight suffix array construction and checking, Proc. 14th CPM, R. Baeza-Yates, E. Chavez and M. Crochemore (eds.), LNCS 2676, Springer-Verlag (2003) 55--69.

Pang Ko and Srinivas Aluru, Space efficient linear time construction of suffix arrays, Proc. 14th CPM, R. Baeza-Yates, E. Chavez and M. Crochemore (eds.), LNCS 2676, Springer-Verlag (2003) 200--210.

Giovanni Manzini and Paolo Ferragina, Engineering a lightweight suffix array construction algorithm, Algorithmica 40 (2004), 33--50.

Stefan Kurtz, Reducing the space requirement of suffix trees, SPE 29--13 (1999) 1149--1171.

N. Jesper Larsson and Kunihiko Sadakane, Faster Suffix Sorting, Technical Report LU--CS--TR:99--214, Lund University (1999) 20 pp.