Self-indexed Text Compression Using Straight-Line Programs

DOI10.1007/978-3-642-03816-7_21MaRDI QIDQ3182928zbMATH OpenOpenAlexFDO

Authors Francisco Claude, Gonzalo Navarro

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_21

Mathematics Subject Classification ID

Database theory (68P15) Grammars and rewriting systems (68Q42)

Recommendations

• Self-indexed grammar-based compression
• Grammar-compressed indexes with logarithmic search time
• A succinct grammar compression
• A faster grammar-based self-index
• Efficient LZ78 factorization of grammar compressed text

Cites work

• scientific article; zbMATH DE number 1045405 (Why is no real title available?)
• scientific article; zbMATH DE number 1998342 (Why is no real title available?)
• scientific article; zbMATH DE number 2038722 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Collage system: A unifying framework for compressed pattern matching.
• Compressed representations of sequences and full-text indexes
• Compression of individual sequences via variable-rate coding
• Grammar-based codes: a new class of universal lossless source codes
• Indexing compressed text
• Indexing text using the Ziv--Lempel trie
• On the sorting-complexity of suffix tree construction
• Rank and select revisited and extended
• Rank/select operations on large alphabets
• Representing trees of higher degree
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• The Smallest Grammar Problem
• The level ancestor problem simplified

Cited in

(11)

• Practical compressed suffix trees
• Faster subsequence and don't-care pattern matching on compressed texts
• Self-indexed grammar-based compression
• On compressing and indexing repetitive sequences
• New algorithms on wavelet trees and applications to information retrieval
• A faster grammar-based self-index
• Random access to grammar-compressed strings and trees
• Grammar-compressed indexes with logarithmic search time
• Showcasing straight-line programs with memory via matrix Bruhat decomposition
• Fast relative Lempel-Ziv self-index for similar sequences
• A succinct grammar compression

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: Self-indexed Text Compression Using Straight-Line Programs

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