Optimal in-place suffix sorting

DOI10.1007/978-3-030-00479-8_22MaRDI QIDQ6109748zbMATH OpenOpenAlexFDO

Authors Zhize Li, Jian Li, Hongwei Huo

Publication date 28 July 2023

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

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

zbMATH Keywords

in-place algorithmsuffix arraysuffix sorting

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: The suffix array is a fundamental data structure for many applications that involve string searching and data compression. Designing time/space-efficient suffix array construction algorithms has attracted significant attention and considerable advances have been made for the past 20 years. We obtain the emph{first} in-place suffix array construction algorithms that are optimal both in time and space for (read-only) integer alphabets. Concretely, we make the following contributions: 1. For integer alphabets, we obtain the first suffix sorting algorithm which takes linear time and uses only $O(1)$ workspace (the workspace is the total space needed beyond the input string and the output suffix array). The input string may be modified during the execution of the algorithm, but should be restored upon termination of the algorithm. 2. We strengthen the first result by providing the first in-place linear time algorithm for read-only integer alphabets with $|Sigma|=O(n)$ (i.e., the input string cannot be modified). This algorithm settles the open problem posed by Franceschini and Muthukrishnan in ICALP 2007. The open problem asked to design in-place algorithms in $o(nlogn)$ time and ultimately, in $O(n)$ time for (read-only) integer alphabets with $|Sigma|leqn$. Our result is in fact slightly stronger since we allow $|Sigma|=O(n)$. 3. Besides, for the read-only general alphabets (i.e., only comparisons are allowed), we present an optimal in-place $O(nlogn)$ time suffix sorting algorithm, recovering the result obtained by Franceschini and Muthukrishnan which was an open problem posed by Manzini and Ferragina in ESA 2002.

Recommendations

• Optimal in-place suffix sorting
• In-Place Suffix Sorting
• In-place sparse suffix sorting
• Space efficient linear time construction of suffix arrays
• Space efficient linear time construction of suffix arrays

Cited in

(8)

• Fast stable in-place sorting with \(O(n)\) data moves
• Optimal in-place suffix sorting
• In-place sparse suffix sorting
• In-Place Suffix Sorting
• A Fast Suffix-Sorting Algorithm
• Classical and quantum algorithms for constructing text from dictionary problem
• On the optimisation of the GSACA suffix array construction algorithm
• Constructing and indexing the bijective and extended Burrows-Wheeler transform

This page was built for publication: Optimal in-place suffix sorting

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