1 citations · 2 across the 6 of their papers we have counts for
8 papers · 1 filter
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 --…
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…
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…
The Trie Measure, Revisited
Jarno N. Alanko, Ruben Becker, Davide Cenzato +4
In this paper, we study the following problem: given subsets of an integer universe , having total cardinality ,…
Suffixient Arrays: a New Efficient Suffix Array Compression Technique
Davide Cenzato, Lore Depuydt, Travis Gagie +4
The Suffix Array is a classic text index enabling on-line pattern matching queries via simple binary search. The main drawback of the Suffix Array is that it takes linear space in…
Sketching and Streaming for Dictionary Compression
Ruben Becker, Matteo Canton, Davide Cenzato +3
We initiate the study of sub-linear sketching and streaming techniques for estimating the output size of common dictionary compressors such as Lempel-Ziv '77, the run-length Burrow…
Random Wheeler Automata
Ruben Becker, Davide Cenzato, Sung-Hwan Kim +3
Wheeler automata were introduced in 2017 as a tool to generalize existing indexing and compression techniques based on the Burrows-Wheeler transform. Intuitively, an automaton is s…
Sorting Finite Automata via Partition Refinement
Ruben Becker, Manuel Cáceres, Davide Cenzato +4
Wheeler nondeterministic finite automata (WNFAs) were introduced as a generalization of prefix sorting from strings to labeled graphs. WNFAs admit optimal solutions to classic hard…