A faster grammar-based self-index

DOI10.1007/978-3-642-28332-1_21MaRDI QIDQ2890196zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, Simon J. Puglisi

Publication date 8 June 2012

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on grammars. In this paper we show how, given a straight-line program with $r$ rules for a string (S [1..n]) whose LZ77 parse consists of $z$ phrases, we can store a self-index for $S$ in $Ohr+zloglogn$ space such that, given a pattern (P [1..m]), we can list the $occ$ occurrences of $P$ in $S$ in $Oh{m}^2+occloglogn$ time. If the straight-line program is balanced and we accept a small probability of building a faulty index, then we can reduce the $Oh{m}^2$ term to $Ohmlogm$. All previous self-indexes are larger or slower in the worst case.

Recommendations

• LZ77-based self-indexing with faster pattern matching
• Self-indexed grammar-based compression
• Self-indexing based on LZ77
• Self-indexed Text Compression Using Straight-Line Programs
• Grammar-compressed indexes with logarithmic search time

Cited in

(29)

• Time-space trade-offs for Lempel-Ziv compressed indexing
• Universal compressed text indexing
• Top tree compression of tries
• Grammar index by induced suffix sorting
• An LMS-based grammar self-index with local consistency properties
• On the approximation ratio of LZ-end to LZ77
• Dynamic index and LZ factorization in compressed space
• Refining the \(r\)-index
• Finger search in grammar-compressed strings
• Approximate pattern matching in LZ77-compressed texts
• Fast relative Lempel-Ziv self-index for similar sequences
• Document listing on repetitive collections with guaranteed performance
• Grammar-compressed indexes with logarithmic search time
• Orthogonal range searching for text indexing
• Self-indexed Text Compression Using Straight-Line Programs
• Self-indexed grammar-based compression
• LZ-End Parsing in Linear Time
• A space-optimal grammar compression
• On two LZ78-style grammars: compression bounds and compressed-space computation
• A self-index on block trees
• Lazy Lempel-Ziv factorization algorithms
• Faster compressed suffix trees for repetitive collections
• LZ77-based self-indexing with faster pattern matching
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Random access in persistent strings and segment selection
• Matching statistics -- a survey
• Lempel-Ziv factorization powered by space efficient suffix trees
• Counting on general run-length grammars
• Grammar index by induced suffix sorting

This page was built for publication: A faster grammar-based self-index

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