Fast compressed self-indexes with deterministic linear-time construction

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/

zbMATH Keywords

succinct data structuressuffix arraysdeterministic constructionself-indexes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Range majorities and minorities in arrays

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