8 papers
Computing Smallest Suffixient Arrays in Sublinear Time
Hiroto Fujimaru, Gonzalo Navarro, Francisco Olivares +3
A suffixient array is a novel data structure that, when combined with an index providing direct access on a text , allows us to answer a variety of pattern matching queries. In…
Smallest Suffixient Sets: Effectiveness, Resilience, and Calculation
Hiroto Fujimaru, Gonzalo Navarro, Giuseppe Romana +1
A suffixient set is a novel combinatorial object that captures the essential information of repetitive strings in a way that, provided with a random access mechanism, supports vari…
Checking and producing word attractors
Marie-Pierre Béal, Maxime Crochemore, Giuseppe Romana
The article focuses on word (or string) attractors, which are sets of positions related to the text compression efficiency of the underlying word. The article presents two combinat…
Unclustered BWTs of any Length over Non-Binary Alphabets
Gabriele Fici, Estéban Gabory, Giuseppe Romana +1
We prove that for every integer and for every alphabet of size , there exists a necklace of length whose Burrows-Wheeler Transform (BWT) is completely…
Bit catastrophes for the Burrows-Wheeler Transform
Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták +3
A bit catastrophe, loosely defined, is when a change in just one character of a string causes a significant change in the size of the compressed string. We study this phenomenon fo…
Generalization of Repetitiveness Measures for Two-Dimensional Strings
Lorenzo Carfagna, Giovanni Manzini, Giuseppe Romana +2
The problem of detecting and measuring the repetitiveness of one-dimensional strings has been extensively studied in data compression and text indexing. Our understanding of these…