@inproceedings{c5c080a4b5fc4a9e97b05ade769b7f69,
title = "Linear Suffix Array Construction by Almost Pure Induced-Sorting",
abstract = "We present a linear time and space suffix array (SA) construction algorithm called the SA-IS algorithm.The SA-IS algorithm is novel because of the LMS-substrings used for the problem reduction and the pure induced-sorting (specially coined for this algorithm)used to propagate the order of suffixes as well as that of LMS-substrings, which makes the algorithm almost purely relying on induced sorting at both its crucial steps.The pure induced-sorting renders the algorithm an elegant design and in turn a surprisingly compact implementation which consists of less than 100 lines of C code.The experimental results demonstrate that this newly proposed algorithm yields noticeably better time and space efficiencies than all the currently published linear time algorithms for SA construction.",
keywords = "Sorting, Educational institutions, Algorithm design and analysis, Data compression, Computer science, Sun, Mathematics, Data structures, Indexing, Information retrieval",
author = "Ge Nong and Sen Zhang and Chan, {Wai Hong}",
note = "Funding Information: Nong was partially supported by the National Science Foundation of P.R.C. (Grant No. 60873056). Zhang was partially supported by the SUNY College Oneonta W.B. Ford Grant. Chan was partially supported by the Faculty Research Grant (FRG/07-08/II-30), HKBU. Publisher copyright: {\textcopyright} 2008 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.; 2009 Data Compression Conference ; Conference date: 16-03-2009 Through 18-03-2009",
year = "2009",
month = mar,
day = "16",
doi = "10.1109/DCC.2009.42",
language = "English",
isbn = "9780769535920",
series = "Data Compression Conference (DCC) ",
publisher = "IEEE Computer Society",
pages = "193--202",
editor = "Storer, {James A.} and Marcellin, {Michael W.}",
booktitle = "2009 Data Compression Conference",
address = "United States",
}