Compressed indexing with signature grammars

DOI10.1007/978-3-319-77404-6_25zbMATH Open1485.68081arXiv1711.08217OpenAlexW2964082949MaRDI QIDQ2294697FDOQ2294697

Authors: Anders Roy Christiansen, Mikko Berggren Ettienne 

Publication date: 12 February 2020

Abstract: The compressed indexing problem is to preprocess a string $S$ of length $n$ into a compressed representation that supports pattern matching queries. That is, given a string $P$ of length $m$ report all occurrences of $P$ in $S$. We present a data structure that supports pattern matching queries in $O(m+occ(lglgn+l{g}^{e}psilonz))$ time using $O(zlg(n/z))$ space where $z$ is the size of the LZ77 parse of $S$ and $epsilon>0$ is an arbitrarily small constant, when the alphabet is small or $z=O(n^{1-delta})$ for any constant $delta>0$. We also present two data structures for the general case; one where the space is increased by $O(zlglgz)$, and one where the query time changes from worst-case to expected. These results improve the previously best known solutions. Notably, this is the first data structure that decides if $P$ occurs in $S$ in $O(m)$ time using $O(zlg(n/z))$ space. Our results are mainly obtained by a novel combination of a randomized grammar construction algorithm with well known techniques relating pattern matching to 2D-range reporting.

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

Recommendations

• Time-space trade-offs for Lempel-Ziv compressed indexing
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Indexing compressed text
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Cited In (6)

• Document listing on repetitive collections with guaranteed performance
• Grammar-compressed indexes with logarithmic search time
• A compressed dynamic self-index for highly repetitive text collections
• Top tree compression of tries
• Rpair: rescaling RePair with Rsync
• Dynamic index and LZ factorization in compressed space

This page was built for publication: Compressed indexing with signature grammars

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