On compressing and indexing repetitive sequences
From MaRDI portal
Publication:390894
DOI10.1016/j.tcs.2012.02.006zbMath1292.68061MaRDI QIDQ390894
Gonzalo Navarro, Sebastian Kreft
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
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68W32: Algorithms on strings
Related Items
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, A new class of searchable and provably highly compressible string transformations, A Space-Optimal Grammar Compression., Bicriteria Data Compression, LZ-End Parsing in Linear Time, Lazy Lempel-Ziv Factorization Algorithms, Faster Compressed Suffix Trees for Repetitive Collections, String Indexing with Compressed Patterns, Near-optimal search time in \(\delta \)-optimal space, and vice versa, Computational graph pangenomics: a tutorial on data structures and their applications, Near-optimal search time in \(\delta \)-optimal space, FM-index of alignment: a compressed index for similar strings, Compact binary relation representations with rich functionality, LZ77 computation based on the run-length encoded BWT, A compressed dynamic self-index for highly repetitive text collections, Comparison of LZ77-type parsings, A separation between RLSLPs and LZ77, Time-space trade-offs for Lempel-Ziv compressed indexing, FM-index of alignment with gaps, Universal compressed text indexing, Flexible indexing of repetitive collections, An LMS-based grammar self-index with local consistency properties, On the approximation ratio of LZ-end to LZ77, Block trees, Lempel-Ziv compressed structures for document retrieval, Block graphs in practice, Grammar compressed sequences with rank/select support, Document listing on repetitive collections with guaranteed performance, Grammar-compressed indexes with logarithmic search time, Faster repetition-aware compressed suffix trees based on block trees, Sensitivity of string compressors and repetitiveness measures, Orthogonal Range Searching for Text Indexing, Composite Repetition-Aware Data Structures, Hybrid indexes for repetitive datasets, Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- Representing trees of higher degree
- Large alphabets and incompressibility
- Indexing text using the Ziv--Lempel trie
- Lempel-Ziv factorization using less time \& space
- Faster entropy-bounded compressed suffix trees
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Stronger Lempel-Ziv based compressed text indexing
- Rank and select revisited and extended
- Compressed representations of sequences and full-text indexes
- Self-indexing Based on LZ77
- Suffix Arrays: A New Method for On-Line String Searches
- Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval
- Self-indexed Text Compression Using Straight-Line Programs
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- An analysis of the Burrows—Wheeler transform
- Self-Indexed Grammar-Based Compression
- An Online Algorithm for Finding the Longest Previous Factors
- Indexing compressed text
- Optimal Succinctness for Range Minimum Queries
- Squeezing succinct data structures into entropy bounds
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
- Upper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the Lempel-Ziv algorithm
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- New text indexing functionalities of the compressed suffix arrays
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- Reducing the Space Requirement of LZ-Index
- Implementing the LZ-index
- Fully-Compressed Suffix Trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
