Small-space LCE data structure with constant-time queries

DOI10.4230/LIPICS.MFCS.2017.10zbMATH Open1441.68026arXiv1702.07458OpenAlexW2773679974MaRDI QIDQ5111224FDOQ5111224

Hideo Bannai, Takaaki Nishimoto, Yuka Tanimura, Shunsuke Inenaga, Masayuki Takeda

Publication date: 26 May 2020

Abstract: The emph{longest common extension} (emph{LCE}) problem is to preprocess a given string $w$ of length $n$ so that the length of the longest common prefix between suffixes of $w$ that start at any two given positions is answered quickly. In this paper, we present a data structure of $O(za{u}^2+fracnau)$ words of space which answers LCE queries in $O(1)$ time and can be built in $O(nlogsigma)$ time, where $1leqauleqsqrtn$ is a parameter, $z$ is the size of the Lempel-Ziv 77 factorization of $w$ and $sigma$ is the alphabet size. This is an emph{encoding} data structure, i.e., it does not access the input string $w$ when answering queries and thus $w$ can be deleted after preprocessing. On top of this main result, we obtain further results using (variants of) our LCE data structure, which include the following: - For highly repetitive strings where the $za{u}^2$ term is dominated by $fracnau$, we obtain a emph{constant-time and sub-linear space} LCE query data structure. - Even when the input string is not well compressible via Lempel-Ziv 77 factorization, we still can obtain a emph{constant-time and sub-linear space} LCE data structure for suitable $au$ and for $sigmaleq{2}^{o(logn)}$. - The time-space trade-off lower bounds for the LCE problem by Bille et al. [J. Discrete Algorithms, 25:42-50, 2014] and by Kosolobov [CoRR, abs/1611.02891, 2016] can be "surpassed" in some cases with our LCE data structure.

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

Recommendations

• Longest common extensions in sublinear space
• Deterministic sub-linear space LCE data structures with efficient construction
• Time-space trade-offs for longest common extensions
• Fully dynamic data structure for LCE queries in compressed space
• Time-Space Trade-Offs for Longest Common Extensions

zbMATH Keywords

longest common extension\(t\)-coverstruncated suffix trees

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Algorithms on Strings, Trees and Sequences
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Linear work suffix array construction
• Title not available (Why is that?)
• Title not available (Why is that?)
• The level ancestor problem simplified
• A universal algorithm for sequential data compression
• Title not available (Why is that?)
• Suffix Arrays: A New Method for On-Line String Searches
• Surpassing the information theoretic bound with fusion trees
• Finding level-ancestors in trees
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Time-space trade-offs for longest common extensions
• Longest Common Extensions in Sublinear Space
• Title not available (Why is that?)
• Fast Algorithms for Finding Nearest Common Ancestors
• Incremental String Comparison
• Longest Common Extensions with Recompression.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Searching for gapped palindromes
• Efficient string matching with k mismatches
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• A new characterization of maximal repetitions by Lyndon trees
• Fast Lightweight Suffix Array Construction and Checking
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Efficiently Finding All Maximal alpha-gapped Repeats
• Truncated suffix trees and their application to data compression.
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
• Faster Longest Common Extension Queries in Strings over General Alphabets
• Fingerprints in compressed strings
• Title not available (Why is that?)
• Computing Longest Single-arm-gapped Palindromes in a String
• Finger Search in Grammar-Compressed Strings
• Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree
• Tight lower bounds for the longest common extension problem
• Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction

Cited In (3)

• Internal shortest absent word queries in constant time and linear space
• A compressed dynamic self-index for highly repetitive text collections
• Title not available (Why is that?)

This page was built for publication: Small-space LCE data structure with constant-time queries

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