2 citations · 3 across the 9 of their papers we have counts for
11 papers
Solving Square-Submatrix Equation Systems
Lorenzo Carfagna, Giovanni Manzini
We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et a…
Prefix-free parsing for merging big BWTs
Diego Diaz-Dominguez, Travis Gagie, Veronica Guerrini +5
When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset c…
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…
Depth first representations of -trees
Gabriel Carmona, Giovanni Manzini
The -tree is a compact data structure designed to efficiently store sparse binary matrices by leveraging both sparsity and clustering of nonzero elements. This representation…
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…
Faster run-length compressed suffix arrays
Nathaniel K. Brown, Travis Gagie, Giovanni Manzini +2
We first review how we can store a run-length compressed suffix array (RLCSA) for a text of length over an alphabet of size whose Burrows-Wheeler Transform (BWT) consis…
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…
Algorithms for Galois Words: Detection, Factorization, and Rotation
Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka +1
Lyndon words are extensively studied in combinatorics on words -- they play a crucial role on upper bounding the number of runs a word can have [Bannai+, SIAM J. Comput.'17]. We ca…
Computing the LCP Array of a Labeled Graph
Jarno Alanko, Davide Cenzato, Nicola Cotumaccio +3
The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al.…
Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests
Dominika Draesslerová, Omar Ahmed, Travis Gagie +4
For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read, we can quickly choose a small subtree likely to contain th…
Suffixient Sets
Lore Depuydt, Travis Gagie, Ben Langmead +2
We define a suffixient set for a text to be a set of positions between 1 and such that, for any edge descending from a node to a node in the suffix tree…