Optimal in-place suffix sorting

Autor: Jian Li, Hongwei Huo, Zhize Li
Rok vydání: 2022
Předmět:
FOS: Computer and information sciences
Open problem
0102 computer and information sciences
02 engineering and technology
Data_CODINGANDINFORMATIONTHEORY
01 natural sciences
Theoretical Computer Science
law.invention
Combinatorics
law
020204 information systems
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Data Structures and Algorithms (cs.DS)
Computer Science::Data Structures and Algorithms
Time complexity
Mathematics
Discrete mathematics
Spacetime
String (computer science)
Sorting
Suffix array
Binary logarithm
Data structure
Computer Science Applications
Computational Theory and Mathematics
010201 computation theory & mathematics
Computer Science::Formal Languages and Automata Theory
Information Systems
Data compression
Integer (computer science)
Zdroj: String Processing and Information Retrieval ISBN: 9783030004781
SPIRE
ISSN: 0890-5401
DOI: 10.1016/j.ic.2021.104818
Popis: 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(n\log n)$ time and ultimately, in $O(n)$ time for (read-only) integer alphabets with $|\Sigma| \leq n$. 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(n\log n)$ 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.
Comment: 36 pages. A disclaimer: https://suffixsorting.github.io/
Databáze: OpenAIRE
Externí odkaz: