Alvaro Martín - Árboles de sufijos y árboles de sufijos truncados.

El árbol de sufijos de una cadena x de largo n es una estructura de datos (de tipo trie) que representa de forma concisa toda la información relativa a qué subcadenas ocurren en x.
Equipados con esta estructura, es posible determinar si una cadena arbitraria z es subcadena de x en tiempo proporcional al largo de z, independientemente de n. Más aún, es posible encontrar todas las posiciones de las ocurrencias de z como subcadena de x usando un tiempo adicional proporcional a la cantidad de ocurrencias, nuevamente con independencia de n.
Esta estructura de datos tiene diversas aplicaciones y, sorprendentemente, existen algoritmos que permiten construirla en tiempo O(n) (asumiendo que operaciones elementales en registros de O(log n) bits pueden realizarse en tiempo O(1)). La estructura de datos requiere O(n log n) bits de memoria.

Los árboles de sufijos truncados son una estructura de datos similar, que puede usarse cuando existe una cota superior, k, para el largo de las cadenas que necesitamos buscar dentro de x. Dependiendo del valor de k (que podría depender de n), la versión truncada es potencialmente más económica en consumo de memoria que el árbol de sufijos completo. Sin embargo, la cantidad de memoria requerida por una representación clásica de un árbol de sufijos truncados crece al menos linealmente con n, sin importar qué tan pequeño sea k.

En esta charla presentaremos estas estructuras de datos en general y un resultado reciente, en el cual mostramos cómo representar eficientemente un árbol de sufijos truncado. Esta nueva representación supera la barrera intrínseca de la representación clásica para alcanzar un consumo de memoria sublineal en n. La nueva representación en ningún caso requiere más memoria que la clásica y su construcción no necesita prácticamente ningún esfuerzo de cómputo adicional. Veremos además un ejemplo de aplicación y resultados experimentales que demuestran un enorme ahorro de memoria en dicha aplicación.