Casamento aproximado de padrões

AUTOR(ES)
DATA DE PUBLICAÇÃO

1994

RESUMO

Neste trabalho estudaremos alguns algoritmos que fornecem soluções para três variações do problema de casamento aproximado de padrões: k diferenças, k colisões, e padrões com símbolos neutros. Neste último problema não estudaremos um algoritmo específico para solucioná-lo, mas um algoritmo genérico que soluciona os três problemas citados. Nosso objetivo principal é descrever e analisar de forma clara e precisa alguns algoritmos para os três problemas. No Capítulo 2 estudaremos o algoritmo de Ukkonen que servirá de base para alguns algoritmos do Capítulo 3. No Capítulo 3 apresentaremos soluções para o problema das k diferenças. Serão apresentados os algoritmos de Ukkonen, o algoritmo de Galil e Park e o algoritmo de Tarhio e Ukkonen. O algoritmo de Ukkonen é uma modificação do algoritmo original apresentado no Capítulo 2, o algoritmo de Galil e Park é uma melhoria do algoritmo de Ukkonen. Já o algoritmo de Tarhio e Ukkonen utiliza as idéias da programação dinâmica e do pré-processamento do padrão. No Capítulo 4 descreveremos três algoritmos que fornecem soluções para o problema das k colisões: algoritmo de Landau e Vishkin, algoritmo de Baeza-Yates e o algoritmo de Tarhio e Ukkonen. O primeiro utiliza idéias semelhantes às idéias do algoritmo de Knuth, Morris e Pratt, os dois últimos algoritmos usam as idéias de deslocamento do padrão encontradas no algoritmo de Boyer e Moore. Por fim, no Capítulo 5, apresentamos os algoritmos de Baeza- Yates e Gonnet e o algoritmo de Wu e Manber que apresentam algoritmos flexíveis para resolver os três problemas do casamento aproximado de padrões

ASSUNTO(S)

reconhecimento de padrões algoritmos

ACESSO AO ARTIGO

Documentos Relacionados