On the optimisation of the GSACA suffix array construction algorithm

DOI10.1007/978-3-031-20643-6_8MaRDI QIDQ6166977zbMATH OpenFDO

Authors Jannik Olbrich, Enno Ohlebusch, Thomas Büchler

Publication date 4 August 2023

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.12222

zbMATH Keywords

string algorithmssuffix arraysuffix sorting

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Algorithms on strings (68W32)

Abstract: 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 GSACA 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 the algorithm's subpar real-world performance. There is a super-linear algorithm DSH which relies on the same sorting principle and is faster than DivSufSort, the fastest SACA for over a decade. This paper is concerned with analysing the sorting principle used in GSACA and DSH and exploiting its properties in order to give an optimised linear-time algorithm. Our resulting algorithm is not only significantly faster than GSACA but also outperforms DivSufSort and DSH.

Recommendations

• Linear-time suffix sorting -- a new approach for suffix array construction
• An elegant algorithm for the construction of suffix arrays
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Optimal in-place suffix sorting

Cites work

• scientific article; zbMATH DE number 432779 (Why is no real title available?)
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Factorizing words over an ordered alphabet
• Linear-time suffix sorting -- a new approach for suffix array construction
• Lyndon Words Accelerate Suffix Sorting.
• Optimal in-place suffix sorting

This page was built for publication: On the optimisation of the GSACA suffix array construction algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166977)