9 papers
Practical evaluation of Lyndon factors via alphabet reordering
Marcelo K. Albertini, Felipe A. Louza
We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with Pizza & Chili datasets show that for most alphabet reorderings,…
Grammar Compression By Induced Suffix Sorting
Daniel S. N. Nunes, Felipe A. Louza, Simon Gog +2
A grammar compression algorithm, called GCIS, is introduced in this work. GCIS is based on the induced suffix sorting algorithm SAIS, presented by Nong et al. in 2009. The proposed…
Space efficient merging of de Bruijn graphs and Wheeler graphs
Lavinia Egidi, Felipe A. Louza, Giovanni Manzini
The merging of succinct data structures is a well established technique for the space efficient construction of large succinct indexes. In the first part of the paper we propose a…
Algorithms to compute the Burrows-Wheeler Similarity Distribution
Felipe A. Louza, Guilherme P. Telles, Simon Gog +1
The Burrows-Wheeler transform (BWT) is a well studied text transformation widely used in data compression and text indexing. The BWT of two strings can also provide similarity meas…
Space-efficient merging of succinct de Bruijn graphs
Lavinia Egidi, Felipe A. Louza, Giovanni Manzini
We propose a new algorithm for merging succinct representations of de Bruijn graphs introduced in [Bowe et al. WABI 2012]. Our algorithm is based on the lightweight BWT merging app…
A Simple Algorithm for Computing the Document Array
Felipe A. Louza
We present a simple algorithm for computing the document array given a string collection and its suffix array as input. Our algorithm runs in linear time using constant additional…