Um índice baseado em árvores de sufixos comprimidas com baixo consumo de memória

Abstract

Árvores de sufixos e arranjos de sufixos são índices bem conhecidos na literatura que organizam a informação combinatória de palavras e que possuem uma vasta gama de aplicações nas mais diversas áreas como processamento de palavras e análise de sequências biológicas. A principal desvantagem destes índices é a demanda excessiva de espaço na prática para entradas grandes. Recentemente, vários trabalhos vem explorando uma estrutura denominada árvore de sufixos comprimida, que oferece a mesma funcionalidade de uma árvore sufixos convencional e é baseada em arranjos de sufixos comprimidos, informação de maior prefixo comum e operações de navegação na árvore. Neste trabalho uma implementação de uma árvore de sufixos comprimida baseada em consultas de range-minimum-query e next/previous smaller queries é apresentada. A implementação possui uma baixa memória de pico, requerendo pouco mais de espaço durante a sua construção em relação ao espaço de representação final da estrutura. Experimentos mostram que este índice é útil para diversas aplicações visto que é possível efetuar operações complexas como travessia de links de sufixos e consultas de ancestral comum mais baixo até quando a quantidade disponível de memória é baixa, já que a estrutura comprimida cabe em memória principal mesmo em computadores mais modestos. ______________________________________________________________________________ ABSTRACT

Suffix trees and suffix arrays are well known indices which organize the combinatorial information of strings and which have a large amount of applications in areas such as string processing and molecular sequence analysis. The main drawback of these indices is that they demand a lot amount of space for large inputs. Recently, several works have been exploring a data structure called compressed suffix tree, which offers the same functionality of the suffix tree and is based on compressed suffix array, compressed longest common pre x information and navigational operations. In this work, the implementation of a compressed suffix tree based on range-minimum-queries and next/previous smaller values queries is presented. The implementation has a low peak memory usage, requiring roughly more than the space needed to represent the index during the construction. Experiments show that this index is useful for many applications since one can execute complex operations like suffix link traversals and longest common ancestor queries being of great interest when the amount of available memory is low, because the structure ts in main memory of ordinary computers.