| 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 |