4 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…
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…