{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T04:19:24Z","timestamp":1770524364242,"version":"3.49.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T00:00:00Z","timestamp":1712966400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["OH 53\/7-1"],"award-info":[{"award-number":["OH 53\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            The suffix array is arguably one of the most important data structures in sequence analysis and consequently there is a multitude of suffix sorting algorithms. However, to this date the\n            <jats:monospace>GSACA<\/jats:monospace>\n            algorithm introduced in 2015 is the only known non-recursive linear-time suffix array construction algorithm (SACA). Despite its interesting theoretical properties, there has been little effort in improving\n            <jats:monospace>GSACA<\/jats:monospace>\n            \u2019s non-competitive real-world performance. There is a super-linear algorithm\n            <jats:monospace>DSH<\/jats:monospace>\n            , which relies on the same sorting principle and is faster than\n            <jats:monospace>DivSufSort<\/jats:monospace>\n            , the fastest SACA for over a decade. The purpose of this article is twofold: We analyse the sorting principle used in\n            <jats:monospace>GSACA<\/jats:monospace>\n            and\n            <jats:monospace>DSH<\/jats:monospace>\n            and exploit its properties to give an optimised linear-time algorithm, and we show that it can be very elegantly used to compute both the original extended Burrows-Wheeler transform (\n            <jats:monospace>eBWT<\/jats:monospace>\n            ) and a bijective version of the Burrows-Wheeler transform (\n            <jats:monospace>BBWT<\/jats:monospace>\n            ) in linear time. We call the algorithm \u201cgeneric,\u201d since it can be used to compute the regular suffix array and the variants used for the\n            <jats:monospace>BBWT<\/jats:monospace>\n            and\n            <jats:monospace>eBWT<\/jats:monospace>\n            . Our suffix array construction algorithm is not only significantly faster than\n            <jats:monospace>GSACA<\/jats:monospace>\n            but also outperforms\n            <jats:monospace>DivSufSort<\/jats:monospace>\n            and\n            <jats:monospace>DSH<\/jats:monospace>\n            . Our\n            <jats:monospace>BBWT<\/jats:monospace>\n            -algorithm is faster than or competitive with all other tested\n            <jats:monospace>BBWT<\/jats:monospace>\n            construction implementations on large or repetitive data, and our\n            <jats:monospace>eBWT<\/jats:monospace>\n            -algorithm is faster than all other programs on data that is not extremely repetitive.\n          <\/jats:p>","DOI":"10.1145\/3641854","type":"journal-article","created":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T12:05:55Z","timestamp":1707393955000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Generic Non-recursive Suffix Array Construction"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3291-7342","authenticated-orcid":false,"given":"Jannik","family":"Olbrich","sequence":"first","affiliation":[{"name":"University of Ulm, Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3937-3652","authenticated-orcid":false,"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[{"name":"University of Ulm, Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9273-5439","authenticated-orcid":false,"given":"Thomas","family":"B\u00fcchler","sequence":"additional","affiliation":[{"name":"University of Ulm, Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,13]]},"reference":[{"key":"e_1_3_3_2_1","volume-title":"Linear-time Suffix Sorting","author":"Baier Uwe","year":"2015","unstructured":"Uwe Baier. 2015. Linear-time Suffix Sorting. Master\u2019s Thesis. Ulm University."},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2016.23"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.18725\/OPARU-35218"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2021.7"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.15"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.14"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2975593"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114400309"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-86692-1_11"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-019-0148-5"},{"key":"e_1_3_3_12_1","article-title":"A block-sorting lossless data compression algorithm","volume":"124","author":"Burrows Michael","year":"1994","unstructured":"Michael Burrows and David Wheeler. 1994. A block-sorting lossless data compression algorithm. Digital SRC Res. Rep. 124 (1994).","journal-title":"Digital SRC Res. Rep."},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2022.25"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970044"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30442-2_6"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90017-2"},{"key":"e_1_3_3_17_1","first-page":"62","volume-title":"Proceedings of the Prague Stringology Conference","author":"Fischer Johannes","year":"2017","unstructured":"Johannes Fischer and Florian Kurpicz. 2017. Dismantling DivSufSort. In Proceedings of the Prague Stringology Conference, Jan Holub and Jan \u017d\u010f\u00e1rek (Eds.). Czech Technical University in Prague, Czech Republic, 62\u201376."},{"key":"e_1_3_3_18_1","first-page":"172","volume-title":"Proceedings of the Prague Stringology Conference","author":"Franek Frantisek","year":"2016","unstructured":"Frantisek Franek, A. S. M. Sohidull Islam, M. Sohel Rahman, and William F. Smyth. 2016. Algorithms to compute the Lyndon array. In Proceedings of the Prague Stringology Conference, Jan Holub and Jan \u017d\u010f\u00e1rek (Eds.). Czech Technical University in Prague, Czech Republic, 172\u2013184."},{"key":"e_1_3_3_19_1","first-page":"77","volume-title":"Proceedings of the Prague Stringology Conference","author":"Franek Frantisek","year":"2017","unstructured":"Frantisek Franek, Asma Paracha, and William F. Smyth. 2017. The linear equivalence of the suffix array and the partially sorted Lyndon array. In Proceedings of the Prague Stringology Conference, Jan Holub and Jan \u017d\u010f\u00e1rek (Eds.). Czech Technical University in Prague, Czech Republic, 77\u201384."},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","unstructured":"Joseph Yossi Gil and David Allen Scott. 2012. A Bijective String Sorting Transform. Retrieved from https:\/\/arxiv.org\/abs\/1201.3077. DOI:10.48550\/ARXIV.1201.3077","DOI":"10.48550\/ARXIV.1201.3077"},{"key":"e_1_3_3_21_1","first-page":"111","volume-title":"Proceedings of the Prague Stringology Conference","author":"Goto Keisuke","year":"2019","unstructured":"Keisuke Goto. 2019. Optimal time and space construction of suffix arrays and LCP arrays for integer alphabets. In Proceedings of the Prague Stringology Conference, Jan Holub and Jan \u017d\u010f\u00e1rek (Eds.). Czech Technical University in Prague, Czech Republic, 111\u2013125."},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_21"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_28"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44888-8_15"},{"key":"e_1_3_3_25_1","first-page":"65","volume-title":"Proceedings of the Prague Stringology Conference","author":"Kufleitner Manfred","year":"2009","unstructured":"Manfred Kufleitner. 2009. On bijective variants of the burrows-wheeler transform. In Proceedings of the Prague Stringology Conference, Jan Holub and Jan \u017d\u010f\u00e1rek (Eds.). Czech Technical University in Prague, Czech Republic, 65\u201379."},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2017.04.001"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104818"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320218"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496656_16"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2493175.2493180"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2009.42"},{"key":"e_1_3_3_32_1","volume-title":"Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.","author":"Ohlebusch Enno","year":"2013","unstructured":"Enno Ohlebusch. 2013. Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.Oldenbusch Verlag."},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20643-6_8"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90013-4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3641854","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3641854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:03Z","timestamp":1750291443000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3641854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,13]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3641854"],"URL":"https:\/\/doi.org\/10.1145\/3641854","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,13]]},"assertion":[{"value":"2022-12-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}