Fully dynamic data structure for LCE queries in compressed space

DOI10.4230/LIPICS.MFCS.2016.72zbMATH Open1398.68110arXiv1605.01488OpenAlexW2963197538MaRDI QIDQ4608635FDOQ4608635

Authors: Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomohiro I 

Publication date: 21 March 2018

Abstract: A Longest Common Extension (LCE) query on a text $T$ of length $N$ asks for the length of the longest common prefix of suffixes starting at given two positions. We show that the signature encoding $mathcalG$ of size $w=O(min(zlogNlo{g}^{\ast }M,N))$ [Mehlhorn et al., Algorithmica 17(2):183-198, 1997] of $T$, which can be seen as a compressed representation of $T$, has a capability to support LCE queries in $O(logN+logelllo{g}^{\ast }M)$ time, where $ell$ is the answer to the query, $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of $T$, and $Mgeq4N$ is an integer that can be handled in constant time under word RAM model. In compressed space, this is the fastest deterministic LCE data structure in many cases. Moreover, $mathcalG$ can be enhanced to support efficient update operations: After processing $mathcalG$ in $O(w{f}_{mathcalA})$ time, we can insert/delete any (sub)string of length $y$ into/from an arbitrary position of $T$ in $O((y+logNlo{g}^{\ast }M)f_{mathcalA})$ time, where $f_{mathcalA}=O(minfracloglogMloglogwlogloglogM,sqrtfraclogwloglogw)$. This yields the first fully dynamic LCE data structure. We also present efficient construction algorithms from various types of inputs: We can construct $mathcalG$ in $O(N{f}_{mathcalA})$ time from uncompressed string $T$; in $O(nloglognlogNlo{g}^{\ast }M)$ time from grammar-compressed string $T$ represented by a straight-line program of size $n$; and in $O(z{f}_{mathcalA}logNlo{g}^{\ast }M)$ time from LZ77-compressed string $T$ with $z$ factors. On top of the above contributions, we show several applications of our data structures which improve previous best known results on grammar-compressed string processing.

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

Recommendations

• Longest common extensions with recompression
• Small-space LCE data structure with constant-time queries
• Deterministic sub-linear space LCE data structures with efficient construction
• Longest common extensions in sublinear space
• Time-space trade-offs for longest common extensions

zbMATH Keywords

straight-line programdynamic textslongest common extension (LCE) queries

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (18)

• Finger search in grammar-compressed strings
• Deterministic sub-linear space LCE data structures with efficient construction
• Title not available (Why is that?)
• Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• LZ77 computation based on the run-length encoded BWT
• A separation between RLSLPs and LZ77
• Document listing on repetitive collections with guaranteed performance
• Locally maximal common factors as a tool for efficient dynamic string algorithms
• Small-space LCE data structure with constant-time queries
• Faster repetition-aware compressed suffix trees based on block trees
• Longest common extensions with recompression
• A compressed dynamic self-index for highly repetitive text collections
• A space-optimal grammar compression
• Balancing run-length straight-line programs
• Universal compressed text indexing
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Dynamic index and LZ factorization in compressed space

This page was built for publication: Fully dynamic data structure for LCE queries in compressed space

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