No autorizado por el autor para ser publicada a texto completo / La cantidad de datos disponibles crece de forma dramática cada día. Esto trae consigo la necesidad de poder manejar éstos datos de forma adecuada, de manera de poder acceder a estos de forma eficiente y al mismo tiempo ahorrar espacio de almacenamiento. En particular, para manejar grandes cantidades de texto una herramienta clave son los índices de texto, y en el contexto de este trabajo los índices comprimidos, los cuales no sólo responden consultas de forma rápida sino que también almacenan sus datos y el texto en forma eficiente. El objetivo general del presente trabajo fue desarrollar un índice comprimido basado en listas de ocurrencias de los q-gramas del texto y comprimir este último. Se desea comparar la eficacia de este índice con los auto-índices ya desarrollados en el sitio Pizza&Chili (http://pizzachili.dcc.uchile.cl). Un índice invertido de q-gramas permite encontrar patrones en un texto. Para tal efecto las consultas se dividen en dos etapas. En la primera etapa se seleccionan las regiones del texto (llamadas bloques) donde ocurren todos los q-gramas del patrón y por lo tanto éste podría encontrarse. En la segunda etapa se verifica si efectivamente el patrón se encuentra en los bloques que fueron seleccionados. Además es necesario almacenar el texto de forma independiente. En la implementación realizada se mantiene el texto dividido en bloques comprimidos, los cuales se almacenan en memoria secundaria. Esto permite utilizar menos espacio y acceder a los bloques individualmente. Se implementaron diversos algoritmos para comprimir el índice y realizar consultas. Además se diseñaron y ejecutaron experimentos para medir el rendimiento de las distintas variantes obtenidas al combinar los diferentes algoritmos. En base a los resultados obtenidos se seleccionaron los algoritmos que presentaron mejor rendimiento tanto en velocidad como en niveles de compresión alcanzados. De la misma forma se implementaron y midieron experimentalmente alternativas para comprimir y buscar en el texto. Finalmente se comparó el rendimiento de las variantes seleccionadas del índice frente a los índices competitivos presentes en el sitio Pizza&Chili. Los resultados indican que el índice tiene un rendimiento competitivo para búsquedas de patrones pequeños.

El almacenamiento digital de la información debe abordar tanto el problema de la incorporación de datos al sistema como su recuperación, y debe hacer un catálogo acorde con las consultas que sobre ellos quiera hacerse. El espacio ocupado para el almacenamiento y el tiempo necesario para ingresar la información, y para recuperala, depende directamente de la estructura utilizada en el repositorio. De este modo, cuando nos referimos a información que ya cuenta cion un grado de estructuración, la indexación debe ser coherente con la estructuta formal de la misma, para favorecer así la consulta. En el presente estudio se aborda el problema de la compresión estática de información semi-estructurada combinada con una indezación tendiente a soportar uin conjunto de consultas sobre los datos, con un fuerte énfasis en el almacenamiento en memoria secundaria. El ámbito de desarrollo de la aplicación propuesta se enmarca dentro de la documentación XML y su lenguaje de consulta XQuery. El modelo utilizado en la implementación está basado en la propuestas desarrolladas por Baeza-Yates y Navarro en Proximal Nodes. La implementación corresponde a un desarrollo posterior de un procesador destinado a soportar consultas en el lenguaje XPath desarrollado por Manuel Ortega como memoria de Ingeniería. El desarrollo de la capa de almacenamiento del prototipo actual se enfoca en la resolución de problemas en tres áreas: recuperación del archivo fuente, consulta eficiente sobre la estructura del documento, y búsqueda de texto en lenguaje natural. Las estructuras diseñadas adhieren a técnicas recientes en el área de la compresión y de recuperación de la información en XML. El resultado de esta memoria es un autoíndice XML con gran desempeño en colecciones de tamaño pequeño y mediano, con capacidad de abordar colecciones de gran tamaño con resucesos limitados de memoria principal, y con un gran potencial de adaptación para colecciones en un nuevo contexto dinámico. El prototipo presenta un desempeño altamente competitivo con las alternativas existentes en el estado del arte.