Listado eficiente y en espacio reducido de documentos con sus frecuencias

Abstract

En este trabajo se propone un nuevo método para la recuperación de documentos eficiente en espacio reducido. En términos generales, en recuperación de documentos se busca responder eficientemente a consultas sobre una colección de documentos con aquellos documentos cuyo contenido satisface algún criterio especificado en las consultas. Para acelerar las consultas los documentos son indexados con alguna estructura de datos. Las soluciones tradicionales para estos problemas basadas en índices invertidos no son adecuadas para dominios en los cuales los patrones de consulta son arbitrarios. Por ello, para colecciones cuyo contenido son, por ejemplo, secuencias de ADN, secuencias de proteínas, datos multimedia o algunos lenguajes naturales estas soluciones no son aplicables. Los índices de texto completo ofrecen una alternativa. Estos permiten indexar patrones generales pero incurren en un excesivo costo en espacio. Muthukrishnan diseñó una solución que utiliza este tipo de índices junto con otras estructuras para resolver listado de documentos. Su algoritmo es óptimo en tiempo pero consume más de veinte veces el espacio que ocupa la colección de documentos de entrada. Sadakane desarrolló una variante del algoritmo de Muthukrishnan. Para reducir el espacio introduce algunas modificaciones y diseña estructuras compactas que reemplazan las utilizadas por Muthukrishnan. Además extiende el algoritmo para resolver consultas de listado de documentos jerarquizadas. El espacio ocupado por el algoritmo de Sadakane para consultas jerarquizadas resulta excesivo para muchas aplicaciones prácticas. Aquí se proponen nuevas estructuras compactas para abordar este problema. Los resultados experimentales muestran que la nueva estrategia resuelve el problema de listado de documentos con sus frecuencias en un espacio menor y con la misma eficiencia que la solución original de Sadakane.