Back to Search
Start Over
An efficient, versatile approach to suffix sorting
- Source :
- ACM Journal of Experimental Algorithmics. 12:1-23
- Publication Year :
- 2008
- Publisher :
- Association for Computing Machinery (ACM), 2008.
-
Abstract
- Sorting the suffixes of a string into lexicographical order is a fundamental task in a number of contexts, most notably lossless compression (Burrows--Wheeler transformation) and text indexing (suffix arrays). Most approaches to suffix sorting produce a sorted array of suffixes directly, continually moving suffixes into their final place in the array until the ordering is complete. In this article, we describe a novel and resource-efficient (time and memory) approach to suffix sorting, which works in a complementary way—by assigning each suffix its rank in the final ordering, before converting to a sorted array, if necessary, once all suffixes are ranked. We layer several powerful extensions on this basic idea and show experimentally that our approach is superior to other leading algorithms in a variety of real-world contexts.
Details
- ISSN :
- 10846654
- Volume :
- 12
- Database :
- OpenAIRE
- Journal :
- ACM Journal of Experimental Algorithmics
- Accession number :
- edsair.doi...........208025cd1f7bc1b7d74b401dc560af45