LInear Time Construction of Suffix Arrays







Deposit Papers 


Ko, Pang and Aluru, Srinivas (2002) LInear Time Construction of Suffix Arrays. Technical Report, Computer Science, Iowa State University.

Full text available as:Adobe PDF


We present a linear time algorithm to sort all the suffixes of a string over a large alphabet of integers. The sorted order of suffixes of a string is also called suffix array, a data structure introduced by Manber and Myers that has numerous applications in computational biology. Though the suffix tree of a string can be constructed in linear time and the sorted order of suffixes derived from it, a direct algorithm for suffix sorting is of great interest due to the space requirements of suffix trees. Our result improves upon the best known direct algorithm for suffix sorting, which takes O(n log n) time. We also show how to construct suffix trees in linear time from our suffix sorting result. Apart from being simple and applicable for alphabets not necessarily of fixed size, this method of constructing suffix trees is more space efficient.

Keywords:computational biology, suffix sorting, suffix arrays, suffix trees
Subjects:Theory of Computation: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3): Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Computing Methodologies: DOCUMENT AND TEXT PROCESSING (H.4-5)
Computer Applications: LIFE AND MEDICAL SCIENCES
ID code:00000292
Deposited by:Srinivas Aluru on 12 December 2002

Contact site administrator at: