Um algoritmo para pesquisa aproximada de padrões baseado no método de Landau e Vishkin e uso de arranjos de sufixos para reduzir o uso de espaço / algorithmos; pattern matching; approximate pattern matching; dynamic programming; Landau; Vishkin; suffix trees;suffix arrays; LCA; LCE; RMQ

AUTOR(ES)

Rodrigo Cesar de Castro Miranda

DATA DE PUBLICAÇÃO

2006

RESUMO

A pesquisa aproximada de padrões em um texto é um problema importante para a ciência da computação. A pesquisa de algoritmos eficientes para solucionar esse problema influencia o desenvolvimento de aplicações em áreas como biologia computacional e pesquisa textual em grandes massas de dados (como a web, por exemplo). Mas para o tratamento de volumes de informação da magnitude envolvida nessas aplicações, o uso eficiente de tempo e espaço é uma condição essencial. A solução mais conhecida para esse problema é um algoritmo de programação dinâmica com complexidade O(mn) para duas palavras P e T de comprimento m e n. Landau e Vishkin desenvolveram um algoritmo que usa árvores de sufixos para acelerar a computação de caminhos da tabela de programação dinâmica que correspondem às ocorrências de um padrão em um texto com no máximo k diferenças, cuja complexidade de tempo e espaço está em O(kn). Nesse algoritmo as árvores de sufixos são utilizadas para permitir o cálculo em tempo constante do comprimento do maior prefixo comum entre quaisquer dois sufixos de P e T. Propusemos e implementamos uma variação do algoritmo de Landau e Vishkin que usa arranjos de sufixos para esse cálculo, melhorando o uso de espaço e mantendo um desempenho similar, e apresentamos a relação de custo e benefício de cada alternativa examinada. Com isso, desenvolvemos um mecanismo que torna possível substituir o uso de árvores de sufixos por arranjos de sufixos em determinadas aplicações, com ganho no uso de espaço, o que permite processar um volume maior de informações. A modificação realizada não é trivial, pois os algoritmos e estruturas de dados utilizadas são complexos, e os parâmetros de desempenho e uso de espaço rigorosos.

ASSUNTO(S)

landau pesquisa de padrões ciencia da computacao árvores de sufixos arranjos de sufixos pesquisa de padrões aproximados vishkin lce lca algoritmos rmq programação dinâmica

Documentos Relacionados

• Modelos de processos difusivos e solução aproximada usando volumes finitos
• The approximate quantum Fourier transform and its simulation
• Graphical models and point pattern matching
• Aplicação de autômatos finitos nebulosos no reconhecimento aproximado de cadeias.
• Caracterização da conectividade entre regiões cerebrais via entropia aproximada e causalidade de Granger.