50 citations · 156 across the 20 of their papers we have counts for
14 papers · 1 filter
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…
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…
Computing the optimal BWT of very large string collections
Davide Cenzato, Veronica Guerrini, Zsuzsanna Lipták +1
It is known that the exact form of the Burrows-Wheeler-Transform (BWT) of a string collection depends, in most implementations, on the input order of the strings in the collection.…
Suffix sorting via matching statistics
Zsuzsanna Lipták, Francesco Masillo, Simon J. Puglisi
We introduce a new algorithm for constructing the generalized suffix array of a collection of highly similar strings. As a first step, we construct a compressed representation of t…
A survey of BWT variants for string collections
Davide Cenzato, Zsuzsanna Lipták
In recent years, the focus of bioinformatics research has moved from individual sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform (…
Computing the original eBWT faster, simpler, and with less memory
Christina Boucher, Davide Cenzato, Zsuzsanna Lipták +2
Mantaci et al. [TCS 2007] defined the eBWT to extend the definition of the BWT to a collection of strings, however, since this introduction, it has been used more generally to desc…
Pattern Discovery in Colored Strings
Zsuzsanna Lipták, Simon J. Puglisi, Massimiliano Rossi
In this paper, we consider the problem of identifying patterns of interest in colored strings. A colored string is a string where each position is assigned one of a finite set of c…
Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták +2
A prefix normal word is a binary word with the property that no substring has more s than the prefix of the same length. By proving that the set of prefix normal words is a bubb…
When a Dollar Makes a BWT
Sara Giuliani, Zsuzsanna Lipták, Francesco Masillo +1
The Burrows-Wheeler-Transform (BWT) is a reversible string transformation which plays a central role in text compression and is fundamental in many modern bioinformatics applicatio…
Bubble-Flip -- A New Generation Algorithm for Prefix Normal Words
Ferdinando Cicalese, Zsuzsanna Lipták, Massimiliano Rossi
We present a new recursive generation algorithm for prefix normal words. These are binary strings with the property that no substring has more 1s than the prefix of the same length…
On Combinatorial Generation of Prefix Normal Words
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták +2
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary…
Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
Ferdinando Cicalese, Travis Gagie, Emanuele Giaquinta +4
We consider how to index strings, trees and graphs for jumbled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing…
Binary Jumbled String Matching for Highly Run-Length Compressible Texts
Golnaz Badkobeh, Gabriele Fici, Steve Kroon +1
The Binary Jumbled String Matching problem is defined as: Given a string over of length and a query , with non-negative integers, decide whether …
Algorithms for Jumbled Pattern Matching in Strings
Péter Burcsi, Ferdinando Cicalese, Gabriele Fici +1
The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two no…