Fast compressed self-indexes with deterministic linear-time construction
From MaRDI portal
Publication:1986963
DOI10.1007/s00453-019-00637-xzbMath1433.68105OpenAlexW2981639848WikidataQ127025879 ScholiaQ127025879MaRDI QIDQ1986963
Yakov Nekrich, Gonzalo Navarro, J. Ian Munro
Publication date: 9 April 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8232/
Related Items
Cites Work
- Succinct representations of permutations and functions
- Efficient fully-compressed sequence representations
- Large alphabets and incompressibility
- A simple storage scheme for strings achieving entropy bounds
- A data structure for dynamic trees
- On-line construction of suffix trees
- Suffix trays and suffix trists: structures for faster text indexing
- Compressed suffix trees with full functionality
- Constructing suffix arrays in linear time
- Space efficient linear time construction of suffix arrays
- Deterministic Dictionaries
- Fully Functional Static and Dynamic Succinct Trees
- Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform
- Alphabet-Dependent String Searching with Wexponential Search Trees
- Compressed representations of sequences and full-text indexes
- Time-Optimal Top-$k$ Document Retrieval
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Suffix Arrays: A New Method for On-Line String Searches
- An analysis of the Burrows—Wheeler transform
- Linear work suffix array construction
- Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
- Indexing compressed text
- Rank/select operations on large alphabets
- Fast Prefix Search in Little Space, with Applications
- A Space-Economical Suffix Tree Construction Algorithm
- New text indexing functionalities of the compressed suffix arrays
- Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
- Alphabet-Independent Compressed Text Indexing
- Optimal Lower and Upper Bounds for Representing Sequences
- Linear-time String Indexing and Analysis in Small Space
- Deterministic Indexing for Packed Strings
- More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching