_Algorithms_**2010**, \(3\), 145 - 167; doi:10.3390/a3020145  
_Article_  
**Suffix-Sorting _via_ Shannon-Fano-Elias Codes**  
**[PERSON] \({}^{\star}\) and [PERSON]**  
Lane Department of Computer Science and Electrical Engineering, West Virginia University,  
Morgantown, WV 26506-6109, USA; E-Mail: [EMAIL_ADDRESS]  
\({}^{\star}\) Author to whom correspondence should be addressed; e-mail: [EMAIL_ADDRESS];  
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_{0}t_{1}\ldots t_{n-1}\) of size \(n=|T|\), with symbols from a fixed alphabet \(\Sigma\), (\(|\Sigma|\leq 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 \((1\frac{2}{3}n\log n-n\log|\Sigma|+O(1))\) bits in memory space. This implies \(5\frac{2}{3}n+O(1)\) bytes for total space requirement, (including space for both the output suffix array and the input sequence \(T\)) assuming \(n\leq 2^{32},|\Sigma|\leq 256\), and 4 bytes per integer. The basis of our algorithm is an extension of Shannon-Fano-Elias codes used in source coding and information theory. This is the first time information-theoretic methods have been used as the basis for solving the suffix sorting problem. **Keywords:** suffix sorting; suffix arrays; suffix tree; Shannon-Fano-Elias codes; source codingIntroduction  
The suffix array provides a compact representation of all the \(n\) suffixes of \(T\) in a lexicographic order. The sequence of positions in \(T\) of the first symbols from the sorted suffixes in this lexicographic order is the suffix array for the sequence. The suffix sorting problem is to construct the suffix array of \(T\). [PERSON] and [PERSON] [1] were the first to propose an \(O(n\log n)\) algorithm to construct the suffix array with three to five times less space than the traditional suffix tree. Other methods for fast suffix sorting in \(O(n\log n)\) time have been reported in [2], while memory efficient constructions were considered in [3]. [PERSON] _et al._[4] provide a detailed comparison of different recently proposed linear time algorithms for suffix sorting. Suffix trees and suffix arrays have drawn a significant attention in recent years due to their theoretical linear time and linear space construction, and their logarithmic search performance. [PERSON] [5] provides a detailed study on the use of suffix trees in the analysis of biological sequences. Suffix sorting is also an important problem in data compression, especially for compression schemes that are based on the Burrows-Wheeler Transform [6; 7]. In fact, it is known that the suffix sorting stage is a major bottleneck in BWT-based compression schemes[6; 7; 8]. The suffix array is usually favored over suffix trees due to its smaller memory footprint. This is important given that the applications of suffix trees and suffix arrays (such as in whole-genome sequence analysis) often involve huge data sets. An important problem therefore is to construct suffix arrays in linear time, while requiring space for the input sequence, in addition to \(n\log n\) bits, the minimal space required to hold the suffix array. This translates to \(5n\) bytes of total space requirment, assuming \(n\leq 2^{32},|\Sigma|\) = 256, and 4 bytes per integer.