Representación en memoria secundaria del trie de sufijos

Abstract

Mientras que en bases de datos tradicionales los índices ocupan menos espacio que el conjunto de datos indexados, en bases de datos de texto el índice ocupa más espacio que el texto en sí mismo, pudiendo necesitar de 4 a 20 veces el tamaño del mismo. Esto implica que un índice construido sobre una base de datos de texto residirá en memoria secundaria y en consecuencia la cantidad de accesos a disco realizados durante el proceso de búsqueda será un factor crítico en la performance del mismo. Un trie de sufijos es un índice para este tipo de bases de datos que necesita en espacio 10 veces el tamaño del texto indexado. Si bien existen algoritmos de construcción de un trie de sufijos en memoria secundaria, no se conocen algoritmos para paginar dicho índice. En este artículo presentamos una propuesta de representación de un trie de sufijos y una técnica de paginado del mismo.