Magíster en Ciencias, Mención Computación / La recuperación de documentos consiste en, dada una colección de documentos y un patrón de consulta, obtener los documentos más relevantes para la consulta. Cuando los documentos están disponibles con anterioridad a las consultas, es posible construir un índice que permita, al momento de realizar las consultas, obtener documentos relevantes en tiempo razonable. Contar con índices que resuelvan un problema como éste es fundamental en áreas como recuperación de la información, minería de datos y bioinformática, entre otros. Cuando el texto que se indexa es lenguaje natural, la solución paradigmática corresponde al índice invertido. Sin embargo, los problemas de recuperación de documentos emergen también en escenarios en que el texto y los patrones de consulta pueden ser secuencias generales de caracteres, como lenguajes orientales, bases de datos multimedia, secuencias genómicas, etc. En estos escenarios los índices invertidos clásicos no se aplican con el mismo éxito. Si bien existen soluciones que requieren espacio lineal en este escenario de texto general, el espacio que utilizan es un problema importante: estas soluciones pueden utilizar más de 20 veces el espacio de la colección. Esta tesis presenta nuevos algoritmos y estructuras de datos para resolver algunos pro- blemas fundamentales para recuperación de documentos en colecciones de texto general, en espacio reducido. Más específicamente, se ofrecen nuevas soluciones al problema de document listing con frecuencias, y recuperación de los top-k documentos. Como subproducto, se de- sarrolló un nuevo esquema de compresión para bitmaps repetitivos que puede ser de interés por sí mismo. También se presentan implementaciones de las nuevas propuestas, y de trabajos relaciona- dos. Estudiamos nuestros algoritmos desde un punto de vista práctico y los comparamos con el estado del arte. Nuestros experimentos muestran que nuestras soluciones para document listing reducen el espacio de la mejor solución existente en un 40%, con un impacto mínimo en los tiempos de consulta. Para recuperación de los top-k documentos, también se redujo el espacio de la mejor solución existente en un 40% en la práctica, manteniendo los tiempos de consulta. Así mismo, mejoramos el tiempo de esta solución hasta en un factor de 100, a expensas de usar un bit extra por carácter. Nuestras soluciones son capaces de retornar los top-10 a top-100 documentos en el orden de milisegundos. Nuestras nuevas soluciones dominan la mayor parte del mapa espacio-tiempo, apuntando a ser el estándar contra el cual comparar la investigación futura.

Gracias a la World Wide Web la idea de información compartida alrededor del mundo es común para todos, la información es ingresada desde diferentes fuentes para que todos puedan verla y usarla. Una Smart Web o Semantic Web tiene como objetivo estructurar los contenidos de forma tal que todo esté relacionado y por lo tanto, presente información consistente. Para ello, se requieren de estructuras que puedan ser accesadas por computadoras y contengan reglas de inferencia para un razonamiento automático. Una de estas estructuras es la ontología. Una ontología busca conceptualizar el conocimiento de un dominio específico valiéndose de representaciones. Como primer paso para construir una ontología, se debe obtener una taxonomía. Una taxonomía es una clasificación de entidades de información a manera de jerarquías. Las taxonomías ofrecen diversas ventajas como clasificar de la información, realizar búsquedas de manera más eficaz y navegar entre muchos conceptos, sin embargo, requieren mucho esfuerzo para ser construidas a mano. Para poder construir una taxonomía en base a un grupo de documentos, primero se debe extraer los conceptos más relevantes presentes en dichos textos. Luego, se debe deducir la jerarquía se convertirá en la taxonomía. Para extraer los conceptos más relevantes de un grupo de documentos, el método CFinder ha probado ser muy útil y dar buenos resultados. El objetivo del CFinder es que sea usado para la construcción de ontologías u otro tipo de estructura que requiera una fase de extracción de conceptos clave. No obstante, no se ha integrado con un método que permita estructurar la jerarquía entre los conceptos extraídos. En este proyecto se busca complementar el método CFinder con una fase para la deducción de jerarquías entre los conceptos extraídos y la construcción de una taxonomía, de esta manera, se está brindando una nueva opción para la construcción automática de taxonomías. Para ello, se realiza la implementación de una herramienta para la construcción automática de una taxonomía de un dominio que haga uso del método CFinder. El proyecto inicia con la implementación de un módulo que permite la extracción de conceptos clave de un conjunto de documentos usando el método CFinder. Luego, se procede a implementar un módulo que permita extraer una taxonomía usando los conceptos clave extraídos. Finalmente, se realizan las pruebas necesarias para medir la eficacia del método implementado y, con los resultados obtenidos, se concluye que se alcanzó el objetivo principal del proyecto.