Longest common extensions with recompression

DOI10.4230/LIPICS.CPM.2017.18MaRDI QIDQ5110882zbMATH OpenOpenAlexFDO

Authors Itagaki Tomohiro

Publication date 25 May 2020

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

zbMATH Keywords

compressed data structurelongest common extension (LCE) queriesgrammar compressed stringsstraight-line program (SLP)

Mathematics Subject Classification ID

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

Abstract: Given two positions $i$ and $j$ in a string $T$ of length $N$, a longest common extension (LCE) query asks for the length of the longest common prefix between suffixes beginning at $i$ and $j$. A compressed LCE data structure is a data structure that stores $T$ in a compressed form while supporting fast LCE queries. In this article we show that the recompression technique is a powerful tool for compressed LCE data structures. We present a new compressed LCE data structure of size $O(zlg(N/z))$ that supports LCE queries in $O(lgN)$ time, where $z$ is the size of Lempel-Ziv 77 factorization without self-reference of $T$. Given $T$ as an uncompressed form, we show how to build our data structure in $O(N)$ time and space. Given $T$ as a grammar compressed form, i.e., an straight-line program of size n generating $T$, we show how to build our data structure in $O(nlg(N/n))$ time and $O(n+zlg(N/z))$ space. Our algorithms are deterministic and always return correct answers.

Recommendations

• Fully dynamic data structure for LCE queries in compressed space
• Small-space LCE data structure with constant-time queries
• Longest common extensions in sublinear space
• Longest common extensions in trees
• Generalized substring compression

Cited in

(20)

• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Longest common extensions in trees
• Longest common extensions in trees
• Longest Common Extensions in Partial Words
• Lyndon factorization of grammar compressed texts revisited
• Linear-time text compression by longest-first substitution
• Internal dictionary matching
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• Dynamic longest common substring in polylogarithmic time
• Small-space LCE data structure with constant-time queries
• Fully dynamic data structure for LCE queries in compressed space
• Grammar-compressed indexes with logarithmic search time
• Longest common extensions with wildcards: trade-off and applications
• Construction of sparse suffix trees and LCE indexes in optimal time and space
• Sensitivity of string compressors and repetitiveness measures
• Generalized substring compression
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Locally consistent parsing for text indexing in small space
• Space-efficient conversions from SLPs

This page was built for publication: Longest common extensions with recompression

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