Artículo de revista
Parallel computation of the Burrows Wheeler Transform in compact space
Fecha
2020Registro en:
Theoretical Computer Science 812(2020)123–136
10.1016/j.tcs.2019.09.030
Autor
Fuentes Sepúlveda, José
Navarro, Gonzalo
Nekrich, Yakov
Institución
Resumen
The Burrows-Wheeler Transform (BWT) has become since its introduction a key tool for representing large text collections in compressed space while supporting indexed searching: on a text of length n over an alphabet of size sigma, it requires O (n lg sigma) bits of space, instead of the O (n lg n) bits required by classical indexes. A challenge for its adoption is to build it within O (n lg sigma) bits as well. There are some sequential algorithms building it within this space, but no such a parallel algorithm. In this paper we present a PRAM CREW algorithm to build the BWT using O (n root lgn) work, O(lg(3)n/lg sigma) depth, and O (n lg sigma) bits.