Davide Cenzato

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 storing very few entries of PA (in fact, a compressed number of entries), one can prove that pattern matching via binary search is still possible provided that random access is available on the text. In this paper, we tackle the problems of determining whether a given subset of text positions is (1) a suffixient set or (2) a suffixient set of minimum cardinality. We provide linear-time algorithms solving these problems.

Ruben Becker, Davide Cenzato, Travis Gagie et al.

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 problems on strings in linear time. Motivated by its large space usage, subsequent research focused first on reducing its size by a constant factor via Suffix Arrays, and later on reaching space proportional to the size of the compressed string. Modern compressed indexes, such as the $r$-index (Gagie et al., SODA 2018), fit in space proportional to $r$, the number of runs in the Burrows-Wheeler transform (a strong and universal repetitiveness measure). These advances, however, came with a price: while modern compressed indexes boast optimal bounds in the RAM model, they are often orders of magnitude slower than uncompressed counterparts in practice due to catastrophic cache locality. This reality gap highlights that Big-O complexity in the RAM model has become a misleading predictor of real-world performance, leaving a critical question unanswered: can we design compressed indexes that are efficient in the I/O model of computation? We answer this in the affirmative by introducing a new Suffix Array sampling technique based on particular path decompositions of the suffix tree. We prove that sorting the suffix tree leaves by specific priority functions induces a decomposition where the number of distinct paths (each corresponding to a string suffix) is bounded by $r$. This allows us to solve indexed pattern matching efficiently in the I/O model using a Suffix Array sample of size at most $r$, strictly improving upon the (tight) $2r$ bound of Suffixient Arrays, another recent compressed Suffix Array sampling technique.

Ruben Becker, Davide Cenzato, Nicola Prezza et al.

Wheeler automata have recently emerged as a powerful generalization of the Burrows-Wheeler Transform, enabling optimal linear-time pattern matching on compressed labeled graphs -- a task that is otherwise computationally hard. Consequently, when an automaton recognizes a Wheeler language (i.e., it is equivalent to some Wheeler automaton), computing its minimum equivalent Wheeler DFA is a powerful indexing strategy. This problem is particularly relevant in computational pangenomics, where pangenome graphs frequently recognize Wheeler languages. However, constructing the minimum Wheeler DFA for a Wheeler language has remained a computational bottleneck. The problem is known to be PSPACE-hard for nondeterministic inputs. When the input is a DFA, state-of-the-art solutions forced a compromise: they were either fast but limited to acyclic DFAs (Alanko et al., SODA 2020) or capable of handling general topologies but prohibitively slow (D'Agostino et al., TCS 2023). In this work, we bridge this gap with the first algorithm solving the problem for general DFAs in near-optimal, linearithmic output-sensitive time. By matching the efficiency of acyclic-only solutions while retaining full generality, our approach improves upon the previous general solution by at least a quadratic factor. We demonstrate the practical impact of our algorithm on real-world pangenome graphs; our tool achieves a processing throughput of over 10^5 transitions per second on a standard workstation, enabling the construction of a provably optimal pattern matching data structure in such applications.