Representación secuencial de un trie de sufijos

Abstract

Un <i>trie de sufijos</i> es un índice para bases de datos de texto que permite resolver eficientemente las operaciones de búsqueda pero que necesita en espacio 10 veces el tamaño del texto indexado. Por esta razón, es importante contar con una técnica de paginación que permita mantener el índice en memoria secundaria pero resolviendo eficientemente las búsquedas sobre el texto indexado. Para lograr esto, como primer paso debemos contar con una representación que sea adecuada para memoria secundaria, es decir que secuencialice la estructura del árbol. En este trabajo implementamos y evaluamos experimentalmente una representación del trie de sufijos que tiene estas características.