Deterministic Sparse Suffix Sorting on Rewritable Texts

DOI10.1007/978-3-662-49529-2_36MaRDI QIDQ2802962zbMATH OpenOpenAlexFDO

Authors Johannes Fischer, Dominik Köppl, Tomohiro I

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Algorithms on strings (68W32)

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(csqrtlgn+mlgmlgnl{g}^{\ast }n)$ time with $O(m)$ words of space under the premise that the space of $T$ is rewritable, where $mlen$ is the number of suffixes to be sorted (provided online and arbitrarily), and $c$ is the number of characters with $mleclen$ that must be compared for distinguishing the designated suffixes.

Recommendations

• Deterministic Sparse Suffix Sorting in the Restore Model
• Faster sparse suffix sorting
• In-place sparse suffix sorting
• An efficient, versatile approach to suffix sorting
• Sparse suffix tree construction in optimal time and space
• A categorization theorem on suffix arrays with applications to space efficient text indexes
• Parallel suffix sorting for large string analytics
• Sparse suffix tree construction in small space
• Combinatorial Pattern Matching

Cited in

(6)

• Deterministic Sparse Suffix Sorting in the Restore Model
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Tight lower bounds for the longest common extension problem
• Space efficient construction of Lyndon arrays in linear time
• Construction of sparse suffix trees and LCE indexes in optimal time and space
• Locally consistent parsing for text indexing in small space

This page was built for publication: Deterministic Sparse Suffix Sorting on Rewritable Texts

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