Explicação_Codigos-de-busca_em_string

Prévia do material em texto

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
Shift para [c] = 3
h b a d e c a e d c a d e
c a d e
4
Shift para [match] = 4
3 2 1
Algoritmo de Boyer-Moore
 = {A C G T}
P = { G C A G A G A G }
T = { G C A T C G C A G A G A G C A G A G A G}
-1234567
07654321
GAGAGACG
8261
8463
8765
8888
TGCA
G C A T C G C A G A G A G
1
C A G A G A G
G C A G A G A G Shift para [A] = 1
Algoritmo de Boyer-Moore
G C A T C G C A G A G A G
2
C A G A G A G
G C A G A G A G Shift para [C] = 6
3 1
G C A T C G C A G A G A G
6
C A G A G A G
G C A G A G A G Shift para [G] = 2
7 5 4 38 2 1
G C A T C G C A G A G A G C A G A G A G
G C A G A G A G Shift para [A] = 1
1
Shift para [C] = 6
G C A G A G A G
algo_BM(char *T, char *P) {
n = strlen(T);
m = strlen(P);
int k, j;
int d[ALFA];
for(k=0;k<ALFA;k++) d[k]=m;
for(k=0;k<m-1;k++) d[P[k]]= m-k-1);
k = m;
while(k <= m){
j = m;
while(j < 0 && T[k] == P[j]) {
j--; k--;
}
if (j==0) printf(“>>match”); 
k +=d[T[k]]; 
}
}
Algoritmo de Boyer-Moore
4
Aplicação: Busca em Texto
O estudo em que consideramos o “problema” de 
definir se uma seqüência de bits existe ou não, é na 
realidade um excelente modelo para diversos 
problemas reais que também aparecem em aplicações, 
como busca na Web e extração de informações em 
texto.
Localização de strings no texto
Um problema comum na era da Web e outros 
repositórios de textos no-line: Dado um conjunto de 
palavras, encontre todos os documentos que 
contenham a maior quantidade “destas palavras”
Máquina de Busca (Cade, Google, Yahoo, etc )