Skip navigation
Use este identificador para citar ou linkar para este item: http://repositorio.unb.br/handle/10482/14442
Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2013_DanielSaadNogueiraNunes.pdf1,73 MBAdobe PDFVisualizar/Abrir
Título: Um índice baseado em árvores de sufixos comprimidas com baixo consumo de memória
Autor(es): Nunes, Daniel Saad Nogueira
Orientador(es): Ayala-Rincón, Mauricio
Assunto: Informática
Algoritmos
Data de publicação: 30-Out-2013
Referência: NUNES, Daniel Saad Nogueira. Um índice baseado em árvores de sufixos comprimidas com baixo consumo de memória. 2013. viii, 82 f., il. Dissertação (Mestrado em Informática)—Universidade de Brasília, Brasília, 2013.
Resumo: Á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.
Unidade Acadêmica: Instituto de Ciências Exatas (IE)
Departamento de Ciência da Computação (IE CIC)
Informações adicionais: Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2013.
Programa de pós-graduação: Programa de Pós-Graduação em Informática
Licença: A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
Aparece nas coleções:Teses, dissertações e produtos pós-doutorado

Mostrar registro completo do item Visualizar estatísticas



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.