2019/03/13 by Felipe A. Louza, Guilherme P. Telles, Simon Gog +1 · 18 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Combinatorics #Computation #Computer science #Concatenation (mathematics) #Data compression #Genomics and Phylogenetic Studies #Image (mathematics) #Mathematics #Memory footprint #Natural Language Processing Techniques #Search engine indexing #Set (abstract data type) #Similarity (geometry) #String (physics) #Theoretical computer science #Transformation (genetics) #cs.DS
paper · pdf · doi:10.1016/j.tcs.2019.03.012
published in Theoretical Computer Science 782, 145-156 (Elsevier BV) · Accepted to TCS
openalex publication_date 2019/03/13 · arxiv created 2019/03/25 · arxiv updated 2020/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.