Self-indexed grammar-based compression

DOI10.3233/FI-2011-565MaRDI QIDQ3225703zbMATH OpenOpenAlexFDO

Authors Francisco Claude, Gonzalo Navarro

Publication date 22 March 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2011-565

zbMATH Keywords

compressed text databasesdata structuresgrammar-based compressionhighly repetitive sequencespattern matchingself-indexesstraight-line programs

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15) Grammars and rewriting systems (68Q42)

Recommendations

• Grammar-compressed indexes with logarithmic search time
• Self-indexed Text Compression Using Straight-Line Programs
• Self-indexing based on LZ77
• A faster grammar-based self-index
• On compressing and indexing repetitive sequences

Cited in

(36)

• Universal compressed text indexing
• siEDM: an efficient string index and search algorithm for edit distance with moves
• Top tree compression of tries
• Grammar index by induced suffix sorting
• An LMS-based grammar self-index with local consistency properties
• Dynamic index and LZ factorization in compressed space
• Finger search in grammar-compressed strings
• Grammar compressed sequences with rank/select support
• Wavelet trees for all
• Document listing on repetitive collections with guaranteed performance
• Grammar-compressed indexes with logarithmic search time
• Orthogonal range searching for text indexing
• Indexing highly repetitive collections
• A faster grammar-based self-index
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• Self-indexing based on LZ77
• Self-indexed Text Compression Using Straight-Line Programs
• Grammar-Based Compression in a Streaming Model
• Compact binary relation representations with rich functionality
• On compressing and indexing repetitive sequences
• A succinct grammar compression
• Entropy lower bounds for dictionary compression
• A space-optimal grammar compression
• On two LZ78-style grammars: compression bounds and compressed-space computation
• A self-index on block trees
• Linear-size CDAWG: new repetition-aware indexing and grammar compression
• Faster compressed suffix trees for repetitive collections
• Grammar Compression by Induced Suffix Sorting
• Practical Random Access to SLP-Compressed Texts
• Rpair: rescaling RePair with Rsync
• Computing all-vs-all MEMs in grammar-compressed text
• Constant-delay enumeration for SLP-compressed documents
• LZ77 computation based on the run-length encoded BWT
• Counting on general run-length grammars
• Grammar index by induced suffix sorting
• A compressed dynamic self-index for highly repetitive text collections

This page was built for publication: Self-indexed grammar-based compression

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