Resultados: visualización detallada

Registro 1 de 1 para la búsqueda Autor Rodríguez Brisaboa, Nieves 

Estructuras Comprimidas para Árboles de Sufijos

Cánovas Barroso, Rodrigo Antonio
Navarro Badino, Gonzalo
Felix Barbay, Jérémy
Rodríguez Brisaboa, Nieves
Paredes Moraleda, Rodrigo

2010

  • Datos de edición CyberDocs
  • Tipo de Documento Libro
  • Materia Estructuras de datos (ciencias de la computación); compresión de datos (ciencias de la computación); estructuras compactas; suffix tree
  • Descripción
    El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación, destacándose en la bioinformática. Una implementación clásica de esta estructura ocupa un espacio de memoria muy grande, lo cual hace difícil su uso para problemas de gran tamaño. En este trabajo se presentará una nueva representación com ...
    El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación, destacándose en la bioinformática. Una implementación clásica de esta estructura ocupa un espacio de memoria muy grande, lo cual hace difícil su uso para problemas de gran tamaño. En este trabajo se presentará una nueva representación comprimida para los árboles de sufijos, la cual ofrece muchas variantes, haciéndola una interesante alternativa con respecto a las implementaciones ya existentes.En la práctica, además de la presentada en este trabajo, existen dos implementaciones disponibles para un árbol de sufijos comprimido. Ambas implementaciones ofrecen espacios y tiempos completamente diferentes. La primera fue propuesta por Sadakane (2007) e implementada por Välimäki et al. (2007). Esta estructura soporta la mayoría de las operaciones de navegación en tiempo constante, tomando unas pocas decenas de microsegundos por operación, pero en la práctica requiere entre 25 a 35 bits por símbolo. La segunda implementación fue propuesta e implementada por Russo et al. (2005). Las operaciones de navegación se resuelven en el orden de los milisegundos por operación, ocupando muy poco espacio en memoria, alrededor de 4 a 6 bits por símbolo. Esto hace que sea atractiva cuando la secuencia es grande en comparación con la memoria principal disponible, pero la implementación es mucho más lenta que la de Välimäki et al. De hecho los tiempos de navegación de Russo et al. son cercanos al tiempo de acceso que toma almacenar datos en disco.En este trabajo inicialmente se implementa una propuesta teórica reciente de Fischer et al., demostrando que de su trabajo se obtienen muchas estructuras interesantes que ofrecen tiempos competitivos y requerimientos de memoria accesibles en la práctica. Luego se exploran diferentes variantes y nuevas ideas para todas las estructuras que componen al árbol de sufijos comprimido propuesto por ellos. Una de estas variantes resultó ser superior a la implementación de Sadakane tanto en espacio como en tiempo, utilizando alrededor de 13 a 16 bits por símbolo y tomando unos pocos microsegundos en resolver cada operación. Otra de estas variantes ocupa entre 8 y 12 bits por símbolo y toma unos pocos cientos de microsegundos por operación, siendo todavía varias veces más rápida que la implementación de Russo.En esta tesis también se implementan y comparan las técnicas actuales más importantes, que usan 2n + o(n) bits y toman tiempo constante por operación, para representar árboles generales en forma sucinta. Cabe notar que en la literatura no existe un estudio exhaustivo que compare la eficiencia práctica de estas técnicas. Éstas se pueden clasificar en tres grandes tendencias: las basadas en BP (balanced parentheses), las basadas en DFUDS (depth - first unary degree sequence) y las basadas en LOUDS (level - ordered unary degree sequence).Los experimentos realizados permiten concluir que una técnica reciente para representar árboles generales, basada en los llamados range min - max trees, se destaca como una excelente combinación de espacio, tiempo y funcionalidad, mientras que las otras (en particular LOUDS) siguen siendo interesantes cuando se necesita funcionalidad limitada. Este estudio aporta nuevas ideas que fueron aplicadas en la implementación del árbol de sufijos comprimido presentado en esta tesis, con lo cual se obtuvieron implementaciones competitivas e incluso mejores que las ya existentes.
  • Identificador 10725