Two Efficient Algorithms for Linear Time Suffix Array Construction

TLDR

The paper introduces two efficient linear‑time algorithms for constructing suffix arrays. The algorithms achieve linear time by using divide‑and‑conquer recursion, sampling variable‑length LMS substrings and fixed‑length d‑critical substrings, and sorting them with induced sorting and radix sorting. Experiments show the algorithms achieve the best time and space efficiency among linear‑time suffix‑array construction methods, with implementations requiring only about 100 lines of C code.

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 algorithm and comparable to that of the KS 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.