Universal compressed text indexing
From MaRDI portal
Publication:1729689
DOI10.1016/j.tcs.2018.09.007zbMath1418.68086arXiv1803.09520OpenAlexW2794898040MaRDI QIDQ1729689
Nicola Prezza, Gonzalo Navarro
Publication date: 28 February 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.09520
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items
Document listing on repetitive collections with guaranteed performance, Grammar-compressed indexes with logarithmic search time, Substring complexities on run-length compressed strings, Sensitivity of string compressors and repetitiveness measures, Block trees, Optimal rank and select queries on dictionary-compressed text, Top tree compression of tries, A compressed dynamic self-index for highly repetitive text collections
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On compressing and indexing repetitive sequences
- Approximation of grammar-based compression via recompression
- Construction of Aho Corasick automaton in linear time for integer alphabets
- Large alphabets and incompressibility
- A \textit{really} simple approximation of smallest grammar
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Collage system: A unifying framework for compressed pattern matching.
- On the approximation ratio of Lempel-Ziv parsing
- A fully linear-time approximation algorithm for grammar-based compression
- A Faster Grammar-Based Self-index
- Time-space trade-offs for predecessor search
- Composite Repetition-Aware Data Structures
- Longest Common Extensions in Sublinear Space
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Suffix Arrays: A New Method for On-Line String Searches
- Self-Indexed Grammar-Based Compression
- Access, Rank, and Select in Grammar-compressed Strings
- Linear work suffix array construction
- Constructing Efficient Dictionaries in Close to Sorting Time
- Indexing compressed text
- The Smallest Grammar Problem
- Fast Prefix Search in Little Space, with Applications
- Efficient randomized pattern-matching algorithms
- Data compression via textual substitution
- Efficient string matching
- On the Complexity of Finite Sequences
- Grammar-based codes: a new class of universal lossless source codes
- Range Predecessor and Lempel-Ziv Parsing
- Sparse Suffix Tree Construction in Optimal Time and Space
- Fully Dynamic Data Structure for LCE Queries in Compressed Space
- Deterministic sorting in O(nloglogn) time and linear space
- Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
- Fast Label Extraction in the CDAWG
- A Self-index on Block Trees
- Complete inverted files for efficient text retrieval and analysis
- At the roots of dictionary compression: string attractors
- Orthogonal range searching on the RAM, revisited
- LZ77-Based Self-indexing with Faster Pattern Matching
