Self-Indexed Grammar-Based Compression
From MaRDI portal
Publication:3225703
DOI10.3233/FI-2011-565zbMath1237.68072OpenAlexW1553071595MaRDI QIDQ3225703
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
data structuresstraight-line programspattern matchinggrammar-based compressionself-indexescompressed text databaseshighly repetitive sequences
Related Items
Document listing on repetitive collections with guaranteed performance ⋮ Grammar index by induced suffix sorting ⋮ An LMS-based grammar self-index with local consistency properties ⋮ Fingerprints in compressed strings ⋮ Grammar-compressed indexes with logarithmic search time ⋮ LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding ⋮ Compact binary relation representations with rich functionality ⋮ On compressing and indexing repetitive sequences ⋮ Wavelet trees for all ⋮ Universal compressed text indexing ⋮ siEDM: an efficient string index and search algorithm for edit distance with moves ⋮ 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 ⋮ Unnamed Item ⋮ LZ77 computation based on the run-length encoded BWT ⋮ Dynamic index and LZ factorization in compressed space ⋮ Top tree compression of tries ⋮ Finger search in grammar-compressed strings ⋮ A Space-Optimal Grammar Compression. ⋮ Orthogonal Range Searching for Text Indexing ⋮ Faster Compressed Suffix Trees for Repetitive Collections
