Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||
| DOI | 10.4230/LIPICS.CPM.2018.7 | ||
| Año | 2018 | ||
| Tipo |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
Lempel-Ziv 1977 (LZ77) parsing, matching statistics and the Burrows-Wheeler Transform (BWT) are all fundamental elements of stringology. In a series of recent papers, Policriti and Prezza (DCC 2016 and Algorithmica, CPM 2017) showed how we can use an augmented run-length compressed BWT (RLBWT) of the reverse TR of a text T, to compute offline the LZ77 parse of T in O(n log r) time and O(r) space, where n is the length of T and r is the number of runs in the BWT of TR. In this paper we first extend a well-known technique for updating an unaugmented RLBWT when a character is prepended to a text, to work with Policriti and Prezza's augmented RLBWT. This immediately implies that we can build online the LZ77 parse of T while still using O(n log r) time and O(r) space; it also seems likely to be of independent interest. Our experiments, using an extension of Ohno, Takabatake, I and Sakamoto's (IWOCA 2017) implementation of updating, show our approach is both time- and space-efficient for repetitive strings. We then show how to augment the RLBWT further -albeit making it static again and increasing its space by a factor proportional to the size of the alphabet -such that later, given another string S and O(log log n)-time random access to T, we can compute the matching statistics of S with respect to T in O(|S| log log n) time.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Bannai, Hideo | Hombre |
Kyushu University - Japón
RIKEN - Japón RIKEN Center for Advanced Intelligence Project - Japón |
| 2 | Gagie, Travis | Hombre |
Universidad Diego Portales - Chile
|
| 3 | I, Tomohiro | Hombre |
Kyushu Institute of Technology - Japón
|
| Fuente |
|---|
| Fondo Nacional de Desarrollo Científico y Tecnológico |
| Japan Society for the Promotion of Science |
| Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica |
| Fondo Nacional de Desarrollo CientÃfico, Tecnológico y de Innovación Tecnológica |