13 citations · 26 across the 10 of their papers we have counts for
9 papers · 1 filter
Optimal Rank and Select Queries on Dictionary-Compressed Text
Nicola Prezza
We study the problem of supporting queries on a string of length within a space bounded by the size of a string attractor for . Recent works showed that random acces…
Optimal-Time Dictionary-Compressed Indexes
Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka +2
We describe the first self-indexes able to count and locate pattern occurrences in optimal time within a space bounded by the size of the most popular dictionary compressors. To ac…
Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space
Travis Gagie, Gonzalo Navarro, Nicola Prezza
Indexing highly repetitive texts - such as genomic databases, software repositories and versioned text collections - has become an important problem since the turn of the millenniu…
Detecting Mutations by eBWT
Nicola Prezza, Nadia Pisanti, Marinella Sciortino +1
In this paper we develop a theory describing how the extended Burrows-Wheeler Transform (eBWT) of a collection of DNA fragments tends to cluster together the copies of nucleotides…
String Attractors: Verification and Optimization
Dominik Kempa, Alberto Policriti, Nicola Prezza +1
String attractors [STOC 2018] are combinatorial objects recently introduced to unify all known dictionary compression techniques in a single theory. A set is a…
Universal Compressed Text Indexing
Gonzalo Navarro, Nicola Prezza
The rise of repetitive datasets has lately generated a lot of interest in compressed self-indexes based on dictionary compression, a rich and heterogeneous family that exploits tex…