Show simple item record

Professor Guidedc.contributor.advisorNavarro Badino, Gonzaloes_CL
Authordc.contributor.authorGonzález del Barrio, Rodrigo es_CL
Staff editordc.contributor.editorFacultad de Ciencias Físicas y Matemáticases_CL
Staff editordc.contributor.editorDepartamento de Ciencias de la Computaciónes_CL
Associate professordc.contributor.otherBarbay, Jeremy
Associate professordc.contributor.otherBustos Cárdenas, Benjamín
Associate professordc.contributor.otherPoblete Olivares, Patricio 
Associate professordc.contributor.otherSadakane, Kunihiko
Admission datedc.date.accessioned2012-09-12T18:11:18Z
Available datedc.date.available2012-09-12T18:11:18Z
Publication datedc.date.issued2008es_CL
Identifierdc.identifier.urihttp://repositorio.uchile.cl/handle/2250/101933
General notedc.descriptionDoctor en Ciencias, Mención Computación
Abstractdc.description.abstractLos autoíndices comprimidos para texto ofrecen una funcionalidad similar a la de los índices clásicos, ocupan espacio proporcional al tamaño del texto comprimido, y además lo reemplazan, pues son capaces de reproducir cualquier subcadena del texto. Aunque un índice comprimido es más lento que su versión clásica, puede funcionar en memoria principal en casos en que un índice tradicional tendría que recurrir a la memoria secundaria, que es órdenes de magnitud más lenta. Por otra parte, los autoíndices comprimidos para texto actuales sufren de varias deficiencias, como la falta de practicidad, la lentitud para localizar un patrón y para extraer un texto, y la falta de mecanismos de construcción eficientes en espacio, de versiones en memoria secundaria o de capacidades para actualizar el índice. Esta tesis aporta soluciones para todos estos problemas. Nuestra primera contribución es una estructura de datos para arreglos de bits, sencilla y eficiente, que permite consultas de rank y select, y que se ha hecho muy popular por su practicidad. También se creó el sitio Pizza&Chili, que contiene una colección de textos y de índices comprimidos, y se realizó un estudio práctico que compara los índices más prometedores. Cabe destacar que este sitio se ha convertido en una referencia habitual en la comunidad. Se desarrolló un nuevo índice comprimido para texto, basado en regularidades del arreglo de sufijos, el cual permite localizar ocurrencias rápidamente, y aún es más pequeño que los índices clásicos. Esta estructura se basa en Re-Pair, un compresor que posee propiedades de localidad que no tienen los índices comprimidos clásicos. Se desarrolló un codificador estadístico de secuencias, que permite el acceso directo a cualquier parte de la secuencia y logra una compresión de alto orden. Esta es una herramienta clave para lograr velocidad y localidad en la extracción de texto en un índice comprimido. Aprovechando esta localidad en la localización y en la extracción, se presentó un nuevo índice para memoria secundaria cuyo tiempo de acceso mejora gracias a la compresión, en lugar de empeorar como es lo normal en otros autoíndices. Este índice ofrece un compromiso muy competitivo entre espacio y tiempo.
Patrocinadordc.description.sponsorshipEsta tesis ha recibido el apoyo de Mecesup, Proyecto UCH 0109, Chile; del Núcleo Milenio Centro de Investigación de la Web, Proyecto P04-067F, Mideplan, Chile; de Yahoo! Research Latin America, y del Instituto Milenio de Dinámica Celular y Biotecnología, Proyecto P05-001-F, Mideplan, Chile
Lenguagedc.language.isoIngles
Publisherdc.publisherUniversidad de Chilees_CL
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
Keywordsdc.subjectComputaciónes_CL
Keywordsdc.subjectEstructuras de datoses_CL
Keywordsdc.subjectAutoíndices comprimidoses_CL
Títulodc.titleAutoíndices Comprimidos para Textoes_CL
Document typedc.typeTesises_CL


Files in this item

Icon
Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile