Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
1
AED´s III
String Matching
Casamento de Padrão
UNIPAC – Universidade Presidente Antonio Carlos
Departamento de Ciência da Computação
Professor: Ciro Meneses Santos
O problema de localizar
ocorrências de uma cadeia de
caracteres em um texto.
String Matching
Conteúdo
• String Matching
– Algoritmo de Força Bruta
– Algoritmo KMP
– Algoritmo Boyer-Moore
Introdução
• O problema de localizar ocorrência duma cadeia
de caracteres num texto é muito frequente.
Existem muitos algoritmos com qualidades
diferentes para satisfazer esta necessidades.
• O problema pode ser formulado como: dado um
conjunto de símbolos “” que definimos como
alfabeto do Texto. Desejamos saber as
ocorrências do Padrão “P” no Texto “T”.
• Aplicações:
– Busca na Internet
– Busca de palavra em texto
– Verificações em sequências de DNA
– Livros, dicionários, artigos técnicos, científicos e
jornalismo
• Notações:
• T Texto;
• P Padrão;
• Alfabeto;
• n Tamanho do Texto;
• m Tamanho do Padrão;
• c Tamanho do alfabeto;
Introdução
• Descrição:
O algoritmo força bruta consiste em verificar, em
todas as posições no texto entre 0 e n-m, se uma
ocorrência do padrão existe ou não. Isto e feito
deslocando o padrão sobre o texto por
exatamente uma posição à direita.
• Características Principais:
– Nenhuma fase de pre-procesamento
– E necessário espaço extra para constante
– desloca sempre o conteúdo 1 posição à direita
– As comparações podem ser feitas em qualquer ordem.
– A complexidade do Algoritmo e O(nm).
Algoritmo Força Bruta
2
• Alfabeto = {a, b, c}
• Texto = { a b a a b a c a b }
• Padrão = { a a b a }
• Passos:
Algoritmo Força Bruta
a b a a b a c a b
a a b a
a b a a b a c a b
a a b a
a b a a b a c a b
a a b a
Primeira tentativa
A B A B A C A BA
1
A A B A
2
Algoritmo Força Bruta
Primeira tentativa
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4
G C A G A G A G
Em segundo tentativa
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Terceira tentativa
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Algoritmo Força Bruta
Quarta tentativa
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Quinta tentativa
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Sexta tentativa
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4 5 6 7 8
G C A G A G A G
Algoritmo Força Bruta
forcaBruna(char *T, char *P) {
n = strlen(T);
m = strlen(P);
for (i=0; i < n-m; i++) {
k=i; cont=1
for(j=0; j < m; j++) {
if ((T[k]==P[j]) and (cont != m)){
cont++;
k++;
}
if (cont == m)
return (1)
}
return (0);
}
Algoritmo de Boyer-Moore
• O algoritmo de Boyer-Moore criado por Robert
Boyer e J. Moore. É considerado como o algoritmo
string-match mais eficiente em aplicações usuais,
principalmente para padrões relativamente longos
e alfabeto grande. Uma versão simplificada do
algoritmo é executada frequentemente em editores
de texto para os comandos de “localizar" e
"substituir".
• O algoritmo faz a varredura dos símbolos do
padrão da direito para à esquerda (rightmost). O
algoritmo utiliza duas funções pre-processadas
para deslocar o padrão à direita. Estas funções dos
deslocamentos são chamadas good-suffix shift e
bad-character shift.
Algoritmo de Boyer-Moore
• Ideia: Analisar o padrão para poder percorrer
o texto mais depressa (com menos
comparações utilizando o conhecimento
adquirido no pre-processamento)
• Consideram-se sufixos do padrão:
• Comparar símbolos atual do padrão (de trás para
frente) e o correspondente no texto.
• Se coincidir, recuar para o símbolo anterior (no
padrão e no texto)
• Se não,
• Usar o número de caracteres já identificados e
o código do caractere do texto que não
coincidiu com o padrão para obter o número de
posições a avançar o padrão no texto.
3
Algoritmo de Boyer-Moore
• Heurísticas:
A questão é, quando não se encontrar uma
ocorrência; é portanto, saber em quantas posições
é que se desloca o padrão para a direita.
• Ocorrência: A heurística da maior ocorrência, em
que se coloca o caractere (do texto) que deferiu
alinhamento com a sua ultima ocorrência no
padrão.
• Coincidências: A heurística das (boas)
coincidências resulta de observar que, quando se
desloca o padrão para a direita, na nova posição
este deve:
• Coincidir com todos os carateres já encontrados. Isto
significa encontrar um substring de P que coincida com
um sufixo do mesmo P.
Algoritmo de Boyer-Moore
= {a b c d e f g h}
P = { c a d e}
T = { h b a d e c a e d c a d e }
44441342
44444444
hgfedcba
4123
edac
h b a d e c a e d c a d e
c a d e
1
Shift para [d] = 1
Algoritmo de Boyer-Moore
h b a d e c a e d c a d e
c a d e
1234
Shift para [b] = 4
h b a d e c a e d c a d e
c a d e
1
Shift para [d] = 1
h b a d e c a e d c a d e
c a d e
1