Suffix Array Construction: Time and Space Efficient Algorithms

Abstract

We have an introduction in this talk to several newly proposed linear-time suffix array construction algorithms (SACAs) based on a technique known as induced sorting. With the algorithms called SA-IS and SA-DS, we can solve the problem of SA construction time and space efficiently, in the sense of that they achieve not only linear times but also very small workspaces. Moreover, two more new algorithms called SACA-K and EM-SA-DS have been recently further developed based on SA-IS and SA-DS, respectively. In particular, for a size-n input string over an alphabet of size K, SACA-K can construct the SA in time O(n) and workspace K words, and EM-SA-DS can construct the SA in external memory with linear I/O complexity of O(dn/B), where d is a constant of type value 2 or 3, and B is the block size for each I/O. Experiment results are also given to demonstrate the time and space performance of these algorithms.