Optimal In-Place Suffix Sorting

Suffix array is a fundamental data structure for many applications that involve string searching and data compression. We obtain the \emph{first} linear time in-place suffix array construction algorithm which is optimal both in time and space for read-only integer alphabets. Our algorithm settles th...

Full description

Saved in:
Bibliographic Details
Main Authors: Li, Zhize, Li, Jian, Huo, Hongwei
Format: Conference Proceeding
Language:English
Subjects:
Arrays
Data compression
Data structures
Heuristic algorithms
In Place
Indexing
Information retrieval
Sorting
Suffix array
Suffix sorting
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suffix array is a fundamental data structure for many applications that involve string searching and data compression. We obtain the \emph{first} linear time in-place suffix array construction algorithm which is optimal both in time and space for read-only integer alphabets. Our algorithm settles the open problem posed by [Franceschini and Muthukrishnan, ICALP'07]. The open problem asked to design in-place algorithms in o(n\log n) time and ultimately, in O(n) time for integer alphabets with |ς|≤ n. Our result is in fact slightly stronger since we allow |ς|=O(n). Besides, we extend it to obtain an optimal O(n\log n) time in-place suffix sorting algorithm for read-only general alphabets (i.e., only comparisons are allowed).
ISSN:2375-0359
DOI:10.1109/DCC.2018.00075