3 papers
cs.DS2019
Inducing the Lyndon Array
Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini +2
In this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in $O(n…
cs.DS2019
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…
cs.DS2018
External memory BWT and LCP computation for sequence collections with applications
Lavinia Egidi, Felipe A. Louza, Giovanni Manzini +1
We propose an external memory algorithm for the computation of the BWT and LCP array for a collection of sequences. Our algorithm takes the amount of available memory as an input p…