Fast compressed self-indexes with deterministic linear-time construction
type: Item
instance of: scholarly article
title: Fast compressed self-indexes with deterministic linear-time construction
zbMATH Open document ID: 1433.68105
author: J. Ian Munro
author: Gonzalo Navarro
author: Yakov Nekrich
published in: Algorithmica
publication date: 2020-04-09T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8232/
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7188813
zbMATH Keywords: succinct data structures
zbMATH Keywords: self-indexes
zbMATH Keywords: suffix arrays
zbMATH Keywords: deterministic construction
MaRDI profile type: Publication
OpenAlex ID: W2981639848
cites work: Efficient fully-compressed sequence representations
cites work: Fast Prefix Search in Little Space, with Applications
cites work: Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform
cites work: Linear-time String Indexing and Analysis in Small Space
cites work: Alphabet-Independent Compressed Text Indexing
cites work: Optimal Lower and Upper Bounds for Representing Sequences
cites work: Deterministic Indexing for Packed Strings
cites work: Suffix trays and suffix trists: structures for faster text indexing
cites work: Indexing compressed text
cites work: Compressed representations of sequences and full-text indexes
cites work: A simple storage scheme for strings achieving entropy bounds
cites work: Alphabet-Dependent String Searching with Wexponential Search Trees
cites work: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
cites work: Large alphabets and incompressibility
cites work: Rank/select operations on large alphabets
cites work: More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
cites work: Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
cites work: Deterministic dictionaries
cites work: Linear work suffix array construction
cites work: Constructing suffix arrays in linear time
cites work: Space efficient linear time construction of suffix arrays
cites work: Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
cites work: Suffix Arrays: A New Method for On-Line String Searches
cites work: An analysis of the Burrows—Wheeler transform
cites work: A Space-Economical Suffix Tree Construction Algorithm
cites work: Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
cites work: Succinct representations of permutations and functions
cites work: Time-Optimal Top-$k$ Document Retrieval
cites work: Fully functional static and dynamic succinct trees
cites work: New text indexing functionalities of the compressed suffix arrays
cites work: Compressed suffix trees with full functionality
cites work: A data structure for dynamic trees
cites work: On-line construction of suffix trees
Wikidata QID: Q127025879
DOI: 10.1007/S00453-019-00637-X
description: scientific article; zbMATH DE number 7188813