Fully dynamic data structure for LCE queries in compressed space

DOI10.4230/LIPICS.MFCS.2016.72MaRDI QIDQ4608635zbMATH OpenOpenAlexFDO

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

Publication date 21 March 2018

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

zbMATH Keywords

dynamic textslongest common extension (LCE) queriesstraight-line program

Mathematics Subject Classification ID

Data structures (68P05)

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.

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

Cited in

(29)

• A separation between RLSLPs and LZ77
• Universal compressed text indexing
• Dynamic index and LZ factorization in compressed space
• Finger search in grammar-compressed strings
• Document listing on repetitive collections with guaranteed performance
• Faster repetition-aware compressed suffix trees based on block trees
• Longest common substring made fully dynamic
• Longest common extensions with recompression
• Small-space LCE data structure with constant-time queries
• A space-optimal grammar compression
• Locally maximal common factors as a tool for efficient dynamic string algorithms
• Deterministic sub-linear space LCE data structures with efficient construction
• Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• scientific article; zbMATH DE number 7765421 (Why is no real title available?)
• Balancing run-length straight-line programs
• A textbook solution for dynamic strings
• Maintaining the size of LZ77 on semi-dynamic strings
• Repetitiveness measures based on string morphisms
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• LZ77 computation based on the run-length encoded BWT
• Height-bounded Lempel-Ziv encodings
• Longest common extensions with wildcards: trade-off and applications
• A textbook solution for dynamic strings
• Two-dimensional longest common extension queries in compact space
• Counting on general run-length grammars
• Pattern matching on run-length grammar-compressed strings in linear time
• A compressed dynamic self-index for highly repetitive text collections

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)