Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Ayala-Rincón, Mauricio | - |
Autor(es): dc.creator | Nunes, Daniel Saad Nogueira | - |
Data de aceite: dc.date.accessioned | 2024-10-23T15:11:47Z | - |
Data de disponibilização: dc.date.available | 2024-10-23T15:11:47Z | - |
Data de envio: dc.date.issued | 2013-10-30 | - |
Data de envio: dc.date.issued | 2013-10-30 | - |
Data de envio: dc.date.issued | 2013-10-30 | - |
Data de envio: dc.date.issued | 2013-05-17 | - |
Fonte completa do material: dc.identifier | http://repositorio.unb.br/handle/10482/14442 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/876911 | - |
Descrição: dc.description | Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2013. | - |
Descrição: dc.description | Á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 | - |
Descrição: dc.description | 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. | - |
Descrição: dc.description | Instituto de Ciências Exatas (IE) | - |
Descrição: dc.description | Departamento de Ciência da Computação (IE CIC) | - |
Descrição: dc.description | Programa de Pós-Graduação em Informática | - |
Formato: dc.format | application/pdf | - |
Direitos: dc.rights | Acesso Aberto | - |
Direitos: dc.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. | - |
Palavras-chave: dc.subject | Informática | - |
Palavras-chave: dc.subject | Algoritmos | - |
Título: dc.title | Um índice baseado em árvores de sufixos comprimidas com baixo consumo de memória | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional – UNB |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: