Orientador : Claudio Leonardo Lucchesi

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

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...

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

Abstract: In this work, we study some algorithms that give solutions to the three variations of the problem of approximate string matching: k-differences, k-mismatches, patterns with don't care symbols. In this last problem we will not study a specific algorithm that solves it but we study a generic...

Abstract: In this work, we study some algorithms that give solutions to the three variations of the problem of approximate string matching: k-differences, k-mismatches, patterns with don't care symbols. In this last problem we will not study a specific algorithm that solves it but we study a generic algorithm that solves the three problems. Our main objective is to describe and analize clearly and precisely some algorithms for the three problems. In Chapter 2 we study the algorithm of Ukkonen that gives a basis for some algorithms in Chapter 3. In Chapter 3 we present solutions to the k-differences problem. It will be presented the algorithm of Ukkonen, the algorithm of Galil and Park and the algorithm of Tarhio and Ukkonen. The algorithm of Ukkonen is a modification of the original one presented in Chapter 2, the algorithm of Galil and Park is an improvement of the algorithm of Ukkonen. The algorithm of Tarhio and Ukkonen uses the ideas from dynamic programming and preprocessing of the pattern.In Chapter 4, we describe three algorithms that solve the k-mismatches problem: algorithm of Landau and Vishkin, algorithm of Baeza and Gonnet and the algorithm of Tarhio and Ukkonen. The first uses the ideas similar to the ideas of the algorithm of Knuth, Morris and Pratt, the last two algorithms use the pattern shift technique introduced in the algorithm of Boyer and Moore. Finally, in Chapter 5, we describe the algorithm of Baeza and Gonnet and the algorithm of Wu and Manber, these algorithms are flexible enough to solve the three problems of approximate string matching