3 citations · 4 across the 9 of their papers we have counts for
11 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…
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…
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…
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…
Morphisms and BWT-run Sensitivity
Gabriele Fici, Giuseppe Romana, Marinella Sciortino +1
We study how the application of injective morphisms affects the number of equal-letter runs in the Burrows-Wheeler Transform (BWT). This parameter has emerged as a key repetiti…
Generalized Straight-Line Programs
Gonzalo Navarro, Francisco Olivares, Cristian Urbina
It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size.…
Exploring Repetitiveness Measures for Two-Dimensional Strings
Giuseppe Romana, Marinella Sciortino, Cristian Urbina
Detecting and measuring repetitiveness of strings is a problem that has been extensively studied in data compression and text indexing. However, when the data are structured in a n…
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…
Iterated Straight-Line Programs
Gonzalo Navarro, Cristian Urbina
We explore an extension to straight-line programs (SLPs) that outperforms, for some text families, the measure based on substring complexity, a lower bound for most measures an…
Balancing Run-Length Straight-Line Programs*
Gonzalo Navarro, Francisco Olivares, Cristian Urbina
It was recently proved that any SLP generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We show that this r…
L-systems for Measuring Repetitiveness*
Gonzalo Navarro, Cristian Urbina
An L-system (for lossless compression) is a CPD0L-system extended with two parameters and , which determines unambiguously a string , where is the mo…