Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

DOI10.4230/LIPICS.ISAAC.2017.57MaRDI QIDQ5136278zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Yakov Nekrich, Gonzalo Navarro

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1707.01743

zbMATH Keywords

deterministic constructionself-indexessuccinct data structuressuffix arrays

Mathematics Subject Classification ID

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

Abstract: We introduce a compressed suffix array representation that, on a text $T$ of length $n$ over an alphabet of size $sigma$, can be built in $O(n)$ deterministic time, within $O(nlogsigma)$ bits of working space, and counts the number of occurrences of any pattern $P$ in $T$ in time $O(|P|+loglo{g}_{w}sigma)$ on a RAM machine of $w=Omega(logn)$-bit words. This new index outperforms all the other compressed indexes that can be built in linear deterministic time, and some others. The only faster indexes can be built in linear time only in expectation, or require $Theta(nlogn)$ bits. We also show that, by using $O(nlogsigma)$ bits, we can build in linear time an index that counts in time $O(|P|/lo{g}_{s}igman+logn(loglogn{)}^2)$, which is RAM-optimal for $w=Theta(logn)$ and sufficiently long patterns.

Recommendations

• Fast compressed self-indexes with deterministic linear-time construction
• Space-efficient construction of compressed indexes in deterministic linear time
• Optimal-Time Dictionary-Compressed Indexes
• Linear time construction of compressed text indices in compact space
• Dynamic index and LZ factorization in compressed space
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Algorithms and Computation

Cites work

• Alphabet-dependent string searching with wexponential search trees
• Alphabet-independent compressed text indexing
• An analysis of the Burrows-Wheeler transform
• Compressed representations of sequences and full-text indexes
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed suffix trees with full functionality
• Deterministic dictionaries
• Deterministic indexing for packed strings
• Efficient fully-compressed sequence representations
• Fast prefix search in little space, with applications
• Fully functional static and dynamic succinct trees
• Indexing compressed text
• Large alphabets and incompressibility
• Linear work suffix array construction
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• New lower and upper bounds for representing sequences
• Rank/select operations on large alphabets
• Space-efficient construction of compressed indexes in deterministic linear time
• Suffix Arrays: A New Method for On-Line String Searches
• Time-optimal top-k document retrieval
• Versatile succinct representations of the bidirectional Burrows-Wheeler transform

Cited in

(4)

• Fast compressed self-indexes with deterministic linear-time construction
• Space-efficient construction of compressed indexes in deterministic linear time
• Optimal-Time Dictionary-Compressed Indexes
• Linear time construction of compressed text indices in compact space

This page was built for publication: Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136278)