Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas,
Departamento de Ciência da Computação, 2013. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-10-24T14:11:34Z
No. of bitstreams: 1
2013_DanielSaadNogueiraNunes.pdf: 1772473 bytes, checksum: 3318dc18d61505b474774b9d9243c2c6 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-10-30T10:50:28Z (GMT) No. of bitstreams: 1
2013_DanielSaadNogueiraNunes.pdf: 1772473 bytes, checksum: 3318dc18d61505b474774b9d9243c2c6 (MD5) / Made available in DSpace on 2013-10-30T10:50:28Z (GMT). No. of bitstreams: 1
2013_DanielSaadNogueiraNunes.pdf: 1772473 bytes, checksum: 3318dc18d61505b474774b9d9243c2c6 (MD5) / Á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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unb.br:10482/14442 |
| Date | 17 May 2013 |
| Creators | Nunes, Daniel Saad Nogueira |
| Contributors | Ayala-Rincón, Mauricio |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UnB, instname:Universidade de Brasília, instacron:UNB |
| Rights | 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., info:eu-repo/semantics/openAccess |
Page generated in 0.0124 seconds