On compressing and indexing repetitive sequences
From MaRDI portal
Publication:390894
DOI10.1016/J.TCS.2012.02.006zbMATH Open1292.68061OpenAlexW2101881908MaRDI QIDQ390894FDOQ390894
Authors: Sebastian Kreft, Gonzalo Navarro 
Publication date: 9 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.006
Recommendations
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Cites Work
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Stronger Lempel-Ziv based compressed text indexing
- Compressed representations of sequences and full-text indexes
- An analysis of the Burrows-Wheeler transform
- Indexing compressed text
- Optimal succinctness for range minimum queries
- Title not available (Why is that?)
- Compression of individual sequences via variable-rate coding
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Title not available (Why is that?)
- Fully-functional succinct trees
- Fully-Compressed Suffix Trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Representing trees of higher degree
- Random access to grammar-compressed strings
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Suffix Arrays: A New Method for On-Line String Searches
- Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
- Title not available (Why is that?)
- Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Rank and select revisited and extended
- Self-indexed grammar-based compression
- Title not available (Why is that?)
- Title not available (Why is that?)
- Faster entropy-bounded compressed suffix trees
- Self-indexing based on LZ77
- Self-indexed Text Compression Using Straight-Line Programs
- An Online Algorithm for Finding the Longest Previous Factors
- Squeezing succinct data structures into entropy bounds
- Breaking a time-and-space barrier in constructing full-text indices
- Title not available (Why is that?)
- Upper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the Lempel-Ziv algorithm
- Title not available (Why is that?)
- Title not available (Why is that?)
- New text indexing functionalities of the compressed suffix arrays
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- Reducing the Space Requirement of LZ-Index
- Implementing the LZ-index, theory versus practice
- Title not available (Why is that?)
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- Large alphabets and incompressibility
- Indexing text using the Ziv--Lempel trie
- Lempel-Ziv factorization using less time \& space
Cited In (55)
- Iterated straight-line programs
- Storage and Retrieval of Individual Genomes
- Fast relative Lempel-Ziv self-index for similar sequences
- Block trees
- Interval-based approach to lexicographic representation and compression of numeric data
- Grammar compressed sequences with rank/select support
- Efficient fully-compressed sequence representations
- Compressed Data Structures for Dynamic Sequences
- Comparison of LZ77-type parsings
- Flexible indexing of repetitive collections
- Block graphs in practice
- Faster repetition-aware compressed suffix trees based on block trees
- Self-indexed grammar-based compression
- Computational graph pangenomics: a tutorial on data structures and their applications
- A new class of searchable and provably highly compressible string transformations
- Self-indexing based on LZ77
- LZ77 computation based on the run-length encoded BWT
- FM-index of alignment: a compressed index for similar strings
- A separation between RLSLPs and LZ77
- Document listing on repetitive collections with guaranteed performance
- Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
- Compression with the tudocomp framework
- An LMS-based grammar self-index with local consistency properties
- String Indexing with Compressed Patterns
- Compact binary relation representations with rich functionality
- Composite repetition-aware data structures
- Lempel-Ziv compressed structures for document retrieval
- Relations between greedy and bit-optimal LZ77 encodings
- Grammar-compressed indexes with logarithmic search time
- Orthogonal range searching for text indexing
- Title not available (Why is that?)
- On the approximation ratio of LZ-end to LZ77
- Near-optimal search time in \(\delta \)-optimal space
- Indexing highly repetitive collections
- Faster repetition-aware compressed suffix trees based on block trees
- A compressed dynamic self-index for highly repetitive text collections
- Linear-size CDAWG: new repetition-aware indexing and grammar compression
- Bicriteria data compression
- A space-optimal grammar compression
- Sensitivity of string compressors and repetitiveness measures
- Time-space trade-offs for Lempel-Ziv compressed indexing
- FM-index of alignment with gaps
- Fast relative Lempel-Ziv self-index for similar sequences
- On two LZ78-style grammars: compression bounds and compressed-space computation
- Faster compressed suffix trees for repetitive collections
- Universal compressed text indexing
- LZ-End Parsing in Linear Time
- Hybrid indexes for repetitive datasets
- A self-index on block trees
- \(r\)-indexing the eBWT
- New advances in rightmost Lempel-Ziv
- On the number of factors in the LZ-End factorization
- Sublinear time Lempel-Ziv (LZ77) factorization
- Lazy Lempel-Ziv factorization algorithms
- Near-optimal search time in \(\delta \)-optimal space, and vice versa
Uses Software
This page was built for publication: On compressing and indexing repetitive sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390894)
