CASAMENTO EXATO DE CADEIAS DE CARACTERES

UNIVERSIDADE FEDERAL DO PARÁ
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS
FACULDADE DE COMPUTAÇÃO

CASAMENTO EXATO DE CADEIAS DE CARACTERES

Belém/PA
2013

CASAMENTO EXATO DE CADEIAS DE CARACTERES

Belém/PA
2013
SUMÁRIO

1 INTRODUÇÃO

Casamento de padrões é o ato de verificação da presença de um padrão em um conjunto de dados. Em contraste ao reconhecimento de padrões, o padrão é rigidamente especificado, seja por uma cadeia de caracteres ou uma árvore. As cadeias aparecem no processamento de textos em linguagem natural, códigos, dicionários, sequenciamento de DNA em biologia computacional, representação de imagens por meio de bitmaps, dentre outros.
O casamento de padrões é usado para testar se o objeto de estudo possui a estrutura desejada, para então encontrar a estrutura relevante, encontrar os pontos de alinhamento e substituir a parte do casamento por outra estrutura. Padrões de sequência (como cadeias de texto) são geralmente escritos usando expressões regulares.
Uma cadeia corresponde a uma sequência de elementos denominados caracteres. Os caracteres são escolhidos de um conjunto denominado alfabeto. Por exemplo, em uma cadeia de bits o alfabeto é {0, 1}.
A pesquisa em cadeias de caracteres é um componente importante em diversos problemas computacionais, tais como edição de texto, recuperação de informação e estudo de sequências de DNA em biologia computacional. No caso de programas editores de texto, o usuário pode estar interessado em buscar todas as ocorrências de um padrão (uma palavra particular) no texto que está sendo editado. Este problema é conhecido como casamento de cadeias de caracteres ou casamento de padrão (do inglês pattern matching).

2 CATEGORIAS DE ALGORITMOS

O uso mais comum de casamento de padrões envolve cadeias de