Exposition and Analysis of a Suffix Sorting Algorithm

摘要: This paper focuses on the suffix sorting algorithm of Maniscalco [10], which at time writing is available only as C++ source code Internet. We will refer to program MSufSort. MSufSort computes Inverse Suffix Array (ISA) an input string, equivalent computing (converting one other discussed in section 8). Recall that for i ∈ [0..n − 1], ISA[i] gives lexicographic rank x[i..n 1] amongst all suffixes string x[0..n 1]. Experiments summarized [10] suggest outperforms fastest known programs, while using little extra space aside from 4n bytes hold array and n (in terms [11] it would be lightweight). It also purported perform well periodic strings, are catastrophic worst cases some algorithms. addresses need a more formal examination what appears very robust sorter. examine describe inner workings algorithm, try explain why performs by analyzing its asymptotic behavior. As published crosses several classes files not easy absorb single sitting. The presented this constitutes complete rewrite original just few C functions, included optimization, but rather aid explanation approach. After introducing notation Section 2, basic described 3 before two powerful heuristics introduced Sections 4 5. 6 7 consider usage. 8 discusses ISA SA transformation. In 9 we extensively test compare performance leading sorters. Possible areas future work outlined 10 11, brief conclusions offered 12. assumed reader familiar with concept applications, particularly Burrows-Wheeler Transformation (BWT).