Orientador : Claudio Leonardo Lucchesi

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

Resumo: O problema de reconhecimento de padrões surge muito freqüentem ente em diversas áreas e consiste basicamente em determinar se um dado objeto (padrão) ocorre em alguma parte de um outro objeto (geralmente bem maior). Existem diversas variações sobre o tema, por exemplo, objetos com uma ou...

Resumo: O problema de reconhecimento de padrões surge muito freqüentem ente em diversas áreas e consiste basicamente em determinar se um dado objeto (padrão) ocorre em alguma parte de um outro objeto (geralmente bem maior). Existem diversas variações sobre o tema, por exemplo, objetos com uma ou mais dimensões, reconhecimento aproximado de padrões etc.
Neste trabalho abordaremos a questão do reconhecimento de padrões unidimensionais que na literatura normalmente é citado como reconhecimento de padrões em texto. Além disso, nos concentramos no problema de reconhecimento exato de padrões. Nosso objetivo principal é apresentar (descrever e analisar) de forma clara e precisa os principais algoritmos que solucionam o problema em questão.
No capítulo 2 descrevemos o algoritmo de Knuth, Morris e Pratt através de autômatos, sendo que vale destacar que, embora a associação entre este algoritmo e autômatos seja citada na literatura com bastante freqüência, normalmente ela não é efetivamente utilizada na descrição do algoritmo. Esta abordagem tornou a descrição do algoritmo bastante simples. Além disso, na análise do algoritmo, a demonstração de alguns resultados foram realizadas de forma bem mais clara do que a originalmente proposta.
No capítulo 3 apresentamos o algoritmo de Boyer e Moore que é um algoritmo extremamente eficiente na prática e no qual se baseiam a maioria dos outros algoritmos existentes. Inclusive, nós apresentamos uma variação deste algoritmo que pode ser descrita de forma mais simples do que o algoritmo original e, em alguns casos, é mais eficiente do que ele. Além disso, neste capítulo tratamos da questão da análise de complexidade do algoritmo de Boyer e Moore que é um problema razoavelmente complexo e apresentamos ainda as principais variações deste algoritmo.
No apêndice A descrevemos outros algoritmos propostos recentemente que solucionam o problema de reconhecimento de padrões em textos e finalmente, no apêndice B, analisamos teoricamente o comportamento médio de alguns algoritmos e também descrevemos os resultados de algumas análises empíricas realizadas por outros autores.

Abstract: The pattern matching problem arises very frequently in several areas of knowledge and basically consists in determining if a given object (pattern) occurs in any place of another object (usually bigger). There are many variations of this problem, for exam pie, objects with one or more...

Abstract: The pattern matching problem arises very frequently in several areas of knowledge and basically consists in determining if a given object (pattern) occurs in any place of another object (usually bigger). There are many variations of this problem, for exam pie, objects with one or more dimensions, approximate pattern matching etc.
In this work we approach the pattern matching problem on one dimension that in the literature is normally named the string matching problem. More precisely, we confined ourselves to the exact pattern matching problem. Our main objective is to present (describe and analyse) dearly and precisely the most important algorithms to solve this problem.
In chapter 2 we describe the Knuth, Morris and Pratt algorithm through automata. It is worth mentioning that, although the association between this algorithm and automata is cited in the literature quite often, in general, automata are not effectively used in the description of the algorithm. This approach made the description of the algorithm very sim pie. Moreover, in the analysis of the algorithm, the proofs of some of the results were accomplished in a clearer way.
In chapter 3 we present the Boyer and Moore algorithm, which is extremelly efficient in practice and the majority of the algorithms found in the literature are based on the ideas of this algorithm. Actually, we present a little variation of this algorithm that is simpler and, in some cases, more efficient than the original algorithm. Moreover, in this chapter, we deal with the complexity analysis of the Boyer and Moore algorithm. We also present several variations of this algorithm.
In appendix A we describe other pattern matching algorithms that were recently developed and finally, in the appendix B, we analise theoretically the average behaviourof some algorithms and also describe the results of some empirical analyses made by other authors.