suffix-sorting via shannon-fano-elias codes通过shannon-fano-elias suffix-sorting代码.pdfVIP

Algorithms 2010, 3, 145 - 167; doi:10.3390/a3020145 OPEN ACCESS algorithms ISSN 1999-4893 /journal/algorithms Article Suffix-Sorting via Shannon-Fano-Elias Codes Donald Adjeroh and Fei Nan Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV 26506-6109, USA; E-Mail: fnan@ Author to whom correspondence should be addressed; e-mail: don@; Tel.: +1-304-293-9681. Received: 23 December 2009; in revised form: 18 March 2010 / Accepted: 18 March 2010 / Published: 1 April 2010 Abstract: Given a sequence T = t t . . . t of size n = T , with symbols from a 0 1 n1 fixed alphabet Σ, (Σ n), the suffix array provides a listing of all the suffixes of T in a lexicographic order. Given T , the suffix sorting problem is to construct its suffix array. The direct suffix sorting problem is to construct the suffix array of T directly without using the suffix tree data structure. While algorithims for linear time, linear space direct suffix sorting have been proposed, the actual constant in the linear space is still a major concern, given that the applications of suffix trees and suffix arrays (such as in whole-genome analysis) often involve huge data sets. In this work, we reduce the gap between current results and the minimal space requirement. We introduce an algorithm for the direct suffix sorting problem with worst case time complexity in O(n), requiring only (12 n log n n log Σ + O(1)) bits