10 papers
On Computing Minimum Wheeler DFA From Their Language
Ruben Becker, Davide Cenzato, Nicola Prezza +1
Wheeler automata have recently emerged as a powerful generalization of the Burrows-Wheeler Transform, enabling optimal linear-time pattern matching on compressed labeled graphs --…
Faster Cache-Efficient Pattern Matching for Deterministic Wheeler Pangenome Graphs
Riccardo Maso, Nicola Prezza, Carlo Tosoni
Pattern matching on strings is regarded as one of the core operations in computer science. Although researchers proposed several solutions to this problem, some of the most elegant…
Testing Suffixient Sets
Davide Cenzato, Francisco Olivares, Nicola Prezza
Suffixient sets are a novel prefix array (PA) compression technique based on subsampling PA (rather than compressing the entire array like previous techniques used to do): by stori…
Compressing Suffix Trees by Path Decompositions
Ruben Becker, Davide Cenzato, Travis Gagie +4
The suffix tree is arguably the most fundamental data structure on strings: introduced by Weiner (SWAT 1973) and McCreight (JACM 1976), it allows solving a myriad of computational…
Algorithms for Massive Data -- Lecture Notes
Nicola Prezza
These are the lecture notes for the course CM0622 - Algorithms for Massive Data, Ca' Foscari University of Venice. The goal of this course is to introduce algorithmic techniques fo…
Incongruity-sensitive access to highly compressed strings
Ferdinando Cicalese, Zsuzsanna Lipták, Travis Gagie +3
Random access to highly compressed strings -- represented by straight-line programs or Lempel-Ziv parses, for example -- is a well-studied topic. Random access to such strings in s…