Two efficient algorithms for linear time suffix array construction

Ge NONG, Sen ZHANG, Wai Hong CHAN

Research output: Contribution to journalArticle

80 Citations (Scopus)

Abstract

We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1=10 of the implementation of the KA [1] algorithm and comparable to that of the KS [2] algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs. Copyright © 2011 IEEE. The journal web site is located at http://www.computer.org/portal/web/tc
Original languageEnglish
Pages (from-to)1471-1484
JournalIEEE Transactions on Computers
Volume60
Issue number10
DOIs
Publication statusPublished - Oct 2011

Citation

Nong, G., Zhang, S., & Chan, W. H. (2011). Two efficient algorithms for linear time suffix array construction. IEEE Transactions on Computers, 60(10), 1471-1484.

Keywords

  • Suffix array
  • Linear time
  • Divide-and-conquer

Fingerprint Dive into the research topics of 'Two efficient algorithms for linear time suffix array construction'. Together they form a unique fingerprint.