Advanced search
Start date
Betweenand


Computing Burrows-Wheeler Similarity Distributions for String Collections

Full text
Author(s):
Louza, Felipe A. ; Telles, Guilherme P. ; Gog, Simon ; Zhao, Liang ; Gagie, T ; Moffat, A ; Navarro, G ; CuadrosVargas, E
Total Authors: 8
Document type: Journal article
Source: STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2018; v. 11147, p. 12-pg., 2018-01-01.
Abstract

In this article 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 Burrows-Wheeler transform (BWT) computed for the concatenation of all strings, instead of the pairwise construction of BWTs performed by the straightforward approach, and use compressed data structures that allow reductions of running time while still keeping a small memory footprint, as shown by a set of experiments with real datasets. (AU)

FAPESP's process: 17/09105-0 - Suffix sorting and string similarity measures
Grantee:Felipe Alves da Louza
Support Opportunities: Scholarships in Brazil - Post-Doctoral