Please use this identifier to cite or link to this item:
Type: Artigo
Title: Algorithms to compute the Burrows-Wheeler similarity distribution
Author: Louza, Felipe A.
Telles, Guilherme P.
Gog, Simon
Zhao, Liang
Abstract: 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 measures between them, based on the observation that the more their symbols are intermixed in the transformation, the more the strings are similar. In this article we present two new algorithms to compute similarity measures based on the BWT for string collections. In particular, we present practical and theoretical improvements to the computation of the Burrows-Wheeler Similarity Distribution for all pairs of strings in a collection. Our algorithms take advantage of the BWT computed for the concatenation of all strings, and use compressed data structures that allow reducing the running time with a small memory footprint, as shown by a set of experiments with real and artificial datasets
Subject: Algoritmos paralelos
Country: Países Baixos
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.tcs.2019.03.012
Date Issue: 2019
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000473373000010.pdf618.58 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.