Deterministic Sparse Suffix Sorting in the Restore Model
Authors:
Open Access
- 12 July 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 16 (4) , 1-53
Abstract
Given a text T of length n , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O( c √ lg n + m lg m lg n lg * n ) time with O( m ) words of space under the premise that the space of T is rewritable, where m ≤ n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m ≤ c ≤ n that must be compared for distinguishing the designated suffixes.Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science (JP19K20213, JP18F18120)
This publication has 18 references indexed in Scilit:
- Time–space trade-offs for longest common extensionsJournal of Discrete Algorithms, 2014
- Selection and Sorting in the “Restore” Model2013
- essaMEM: finding maximal exact matches using enhanced sparse suffix arraysBioinformatics, 2013
- ESP-index: A compressed index based on edit-sensitive parsingJournal of Discrete Algorithms, 2013
- A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arraysBioinformatics, 2009
- A Space-Saving Approximation Algorithm for Grammar-Based CompressionIEICE Transactions on Information and Systems, 2009
- A taxonomy of suffix array construction algorithmsACM Computing Surveys, 2007
- Linear work suffix array constructionJournal of the ACM, 2006
- Low Redundancy in Static Dictionaries with Constant Query TimeSIAM Journal on Computing, 2001
- Quorums from difference coversInformation Processing Letters, 2000