{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T08:48:13Z","timestamp":1758703693625,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>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\u2014by 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.<\/jats:p>","DOI":"10.1145\/1227161.1278374","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-23","source":"Crossref","is-referenced-by-count":10,"title":["An efficient, versatile approach to suffix sorting"],"prefix":"10.1145","volume":"12","author":[{"given":"Michael A.","family":"Maniscalco","sequence":"first","affiliation":[{"name":"Independent Researcher"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Curtin University of Technology, Perth, Australia"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/S1570-8667(03)00065-0"},{"doi-asserted-by":"publisher","unstructured":"Andersson A. and Nilsson S. 1998. Implementing radix sort. ACM Journal of Experimental Algorithmics 3. 10.1145\/297096.297136","key":"e_1_2_1_2_1","DOI":"10.1145\/297096.297136"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1002\/spe.4380231105"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.5555\/314161.314321"},{"key":"e_1_2_1_5_1","volume-title":"Tech. Rep. 124","author":"Burrows M.","year":"1994","unstructured":"Burrows, M. and Wheeler, D. J. 1994. A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation, Palo Alto, CA."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.5555\/795666.796543"},{"key":"e_1_2_1_7_1","volume-title":"Poster Proceedings","volume":"38","author":"Gonz\u00e1lez R.","unstructured":"Gonz\u00e1lez, R., Grabowski, S., M\u00e4kinen, V., and Navarro, G. 2005. Practical implementation of rank and select queries. In Poster Proceedings Volume of Fourth Workshop on Efficient and Experimental Algorithms (WEA'05). CTI Press and Ellinika Grammata, Greece. 27--38."},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/S0097539702402354"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/519452.830768"},{"key":"e_1_2_1_10_1","volume-title":"Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, R. Baeza-Yates, E. Ch\u00e1vez, and M. Crochemore, Eds. Lecture Notes in Computer Science","volume":"2676","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen, J. and Burkhardt, S. 2003. Fast lightweight suffix array construction and checking. In Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, R. Baeza-Yates, E. Ch\u00e1vez, and M. Crochemore, Eds. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag, Berlin. 55--69."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th International Colloq. Automata, Languages and Programming. Lecture Notes in Computer Science","volume":"2971","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen, J. and Sanders, P. 2003. Simple linear work suffix array construction. In Proceedings of the 30th International Colloq. Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2971. Springer-Verlag, Berlin. 943--955."},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/800152.804905"},{"key":"e_1_2_1_13_1","volume-title":"Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, R. Baeza-Yates, E. Ch\u00e1vez, and M. Crochemore, Eds. Lecture Notes in Computer Science","volume":"2676","author":"Kim D. K., S., S. J.","unstructured":"Kim, D. K., S., S. J., Park, H., and Park, K. 2003. Linear-time construction of suffix arrays. In Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, R. Baeza-Yates, E. Ch\u00e1vez, and M. Crochemore, Eds. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag, Berlin. 186--199."},{"key":"e_1_2_1_14_1","volume-title":"Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, R. Baeza-Yates, E. Ch\u00e1vez, and M. Crochemore, Eds. Lecture Notes in Computer Science","volume":"2676","author":"Ko P.","unstructured":"Ko, P. and Aluru, S. 2003. Space efficient linear time construction of suffix arrays. In Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, R. Baeza-Yates, E. Ch\u00e1vez, and M. Crochemore, Eds. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag, Berlin. 200--210."},{"key":"e_1_2_1_15_1","volume-title":"Tech. Rep. LU-CS-TR:99-214 {LUNFD6\/(NFCS-3140)\/1-20\/(1999)}, Department of Computer Science","author":"Larsson N. J.","year":"1999","unstructured":"Larsson, N. J. and Sadakane, K. 1999. Faster suffix--sorting. Tech. Rep. LU-CS-TR:99-214 {LUNFD6\/(NFCS-3140)\/1-20\/(1999)}, Department of Computer Science, Lund University, Sweden."},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.5555\/1195881.1195885"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1137\/0222058"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/978-3-540-27810-8_32"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1007\/s00453-004-1094-1"},{"key":"e_1_2_1_20_1","first-page":"5","article-title":"Engineering radix sort","volume":"6","author":"McIlroy P. M.","year":"1993","unstructured":"McIlroy, P. M., Bostic, K., and McIlroy, M. D. 1993. Engineering radix sort. Computing Systems 6, 1, 5--27.","journal-title":"Computing Systems"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/1073691.1710491"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/261387.261395"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1109\/DCC.2005.87"},{"doi-asserted-by":"publisher","unstructured":"Puglisi S. J. Smyth W. F. and Turpin A. H. 2007. A taxonomy of suffix array construction algorithms. ACM Computing Surveys. 39 2 Article 1. 10.1145\/1242471.1242472","key":"e_1_2_1_25_1","DOI":"10.1145\/1242471.1242472"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.5555\/874052.874842"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.5555\/545381.545410"},{"unstructured":"Schindler M. 2002. szip homepage. http:\/\/www.compressconsult.com\/szip\/. Available Online.","key":"e_1_2_1_28_1"},{"volume-title":"Proceedings of The Seventh Workshop on Algorithm Engineering and Experiments (ALENEX'05)","author":"Sch\u00fcrmann K.","unstructured":"Sch\u00fcrmann, K. and Stoye, J. 2005. An incomplex algorithm for fast suffix array construction. In Proceedings of The Seventh Workshop on Algorithm Engineering and Experiments (ALENEX'05). SIAM. 77--85.","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.5555\/789087.789805"},{"unstructured":"Seward J. 2004. The bzip2 and libbzip2 home page. http:\/\/sources.redhat.com\/bzip2\/. Available Online.","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","unstructured":"Sinha R. and Zobel J. 2004. Cache-conscious sorting of large sets of strings with dynamic tries. ACM Journal of Experimental Algorithmics 9. 10.1145\/1005813.1041517","key":"e_1_2_1_32_1","DOI":"10.1145\/1005813.1041517"},{"volume-title":"Computing Patterns in Strings","author":"Smyth W. F.","unstructured":"Smyth, W. F. 2003. Computing Patterns in Strings. Addison-Wesley-Pearson Education Limited, Essex, England.","key":"e_1_2_1_33_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/294188.294194"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1278374","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1278374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1278374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":33,"alternative-id":["10.1145\/1227161.1278374"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1278374","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}