Metodos eficientes para reconhecimento de padrões em texto

AUTOR(ES)
DATA DE PUBLICAÇÃO

1993

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.

ASSUNTO(S)

reconhecimento de padrões algoritmos

Documentos Relacionados