Sparse suffix tree construction in optimal time and space

DOI10.1137/1.9781611974782.27MaRDI QIDQ4575764zbMATH OpenOpenAlexWikidataFDO

Authors Paweł Gawrychowski, Tomasz Kociumaka

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographical order. In some applications, we work with a subset of $b$ interesting suffixes, which are stored in the so-called sparse suffix tree. Because the size of this structure is $Theta(b)$, it is natural to seek a construction algorithm using only $O(b)$ words of space assuming read-only random access to the text. We design a linear-time Monte Carlo algorithm for this problem, hence resolving an open question explicitly stated by Bille et al. [TALG 2016]. The best previously known algorithm by I et al. [STACS 2014] works in $O(nlogb)$ time. Our solution proceeds in $n/b$ rounds; in the $r$-th round, we consider all suffixes starting at positions congruent to $r$ modulo $n/b$. By maintaining rolling hashes, we lexicographically sort all interesting suffixes starting at such positions, and then we merge them with the already considered suffixes. For efficient merging, we also need to answer LCE queries in small space. By plugging in the structure of Bille et al. [CPM 2015] we obtain $O(n+blogb)$ time complexity. We improve this structure, which implies a linear-time sparse suffix tree construction algorithm. We complement our Monte Carlo algorithm with a deterministic verification procedure. The verification takes $O(nsqrtlogb)$ time, which improves upon the bound of $O(nlogb)$ obtained by I et al. [STACS 2014]. This is obtained by first observing that the pruning done inside the previous solution has a rather clean description using the notion of graph spanners with small multiplicative stretch. Then, we are able to decrease the verification time by applying difference covers twice. Combined with the Monte Carlo algorithm, this gives us an $O(nsqrtlogb)$-time and $O(b)$-space Las Vegas algorithm.

Recommendations

• Sparse suffix tree construction in small space
• Sparse text indexing in small space
• Faster sparse suffix sorting
• In-place sparse suffix sorting
• Space efficient suffix trees

Cited in

(20)

• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Universal compressed text indexing
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Tight lower bounds for the longest common extension problem
• Deterministic Sparse Suffix Sorting on Rewritable Texts
• Faster sparse suffix sorting
• scientific article; zbMATH DE number 2102777 (Why is no real title available?)
• Sparse text indexing in small space
• Optimal Substring Equality Queries with Applications to Sparse Text Indexing
• Sparse suffix tree construction in small space
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Sparse suffix trees
• Space-efficient conversions from SLPs
• Sparse suffix and LCP array: simple, direct, small, and fast
• 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
• Longest common extensions with wildcards: trade-off and applications
• Sparse suffix and LCP array: simple, direct, small, and fast
• Strictly in-place algorithms for permuting and inverting permutations

This page was built for publication: Sparse suffix tree construction in optimal time and space

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