Busca de Padrões

A busca de padrões (amplamente utilizada na informática) consiste em dado um conjunto de caracteres de tamanho n (que alguns chamam de “texto”) e outro conjunto menor ou igual chamado de padrão (com tamanho m). Assim, é realizada a procura no texto da posição (se ocorrer) referente ao padrão dado. Mais precisamente, queremos achar o índice o qual inicia o padrão no texto. Se for o caso, podemos verificar o texto todo para busca de múltiplas ocorrências. O funcionamento da busca de padrão é simples, se o primeiro caractere é idêntico à um referente no texto, todos os sucessores devem ser idênticos também, até finalizar o padrão. Caso ocorra que um caractere não seja igual, desloca-se o padrão em um caractere até chegar ao fim do texto ou encontrar o padrão.

Algoritmos

#include
#include
#include //fflush(stdin) e
#include //pra pegar o tempo! clock();
#define TAM 1000
//variaveis globais para manipulacao das funcoes abaixo
int comparacoes = 0 ;
int pula[53];
int proximo[11]; //vetor pro KMP proximos valores

//---------------------------------------------------------------------//
//PUC MINAS - SÃO GABRIEL
//Alunos - André Gouvêa Horst
//Data - 4/06/2005
//Programa - varios metodos de reconhecimento de padrão
//---------------------------------------------------------------------//

void pulaKMP(char *p){
int i = 0, j, m = strlen(p);
j = proximo[0] =-1;
while(i while (j>= 0 && p[i] != p[j])
j = proximo[j];
i++;
j++;
if(p[i]==p[j])
proximo[i] = proximo[j];
else
proximo[i] = j;
}
for (i = 0; i < m; i++)
cout<<"proximo ["<}

int kmp(char *p, char *a){
int i, j, m = strlen(p), n = strlen(a);
comparacoes = 0;
pulaKMP(p);
int final;
int inicio = clock();
for(i = 0, j = 0; j < m && i < n; i++, j++){
cout<<"Comprarando "< cout<<"Numero de comparacoes "< cout<<"Tempo "< return i-m;
}
else{
cout<<"Falha! "<<(i)< cout<<"Numero de comparacoes "< cout<<"Tempo "< return i;
}
}

int forcaBruta(char *p, char *a){
int i = 0, j = 0, n = 0, m = 0;
comparacoes = 0;
n = strlen(a);
m = strlen(p);
int final;
int inicio = clock();
for(i = 0, j = 0; j < m && i < n; i=i, j=j){
cout< if (a[i]!= p[j]) {
comparacoes++;
i = i-(j-1);
j = 0;
}
else{
comparacoes++;
i++;
j++;
}
}
final = clock();
if(j == m){
cout<<"Comparacao comeca com "<<(i-m)< cout<<"Numero de comparacoes "< cout<<"Tempo "< return i-m;
}
else{
cout<<"Falha!"<<(i)< cout<<"Numero de comparacoes "< cout<<"Tempo "< return i;
}
}

void initpula(char *p) {
int i, l = strlen(p);
cout<<"pula vetor..."< for(i = 0; i <= 52; i++)
pula[i] = l;
for(i = 0; i <= l - 1; i++){
cout<<"pula["< pula[p[i]-65]= l - 1 - i;
}
cout<}

int boyerMoore(char *p, char *a){
int i, j, t, M = strlen(p), N = strlen(a);
initpula(p);
int final;
int inicio = clock();
for(i = M-1, j = M-1; j >= 0; i--, j--){
while(a[i] != p[j]){
comparacoes++;
cout< i += (M-j > t) ? M-j : t;
if(i >= N){
cout<<"Combinacao nao encontrada! "< return N;
}
j = M-1;
}
comparacoes++;
}
final = clock();
cout<<"Combinacao comeca com "< cout<<"Numero de comparacoes "< cout<<"Tempo "< return i;
}

void main(){
//variaveis com textos default para textes do programa
char t1[] = "CACACAU";
char p1[] = "CACAU";
char t2[] = "GCATCGCAGAGAGTATACAGTACG";
char p2[] = "GCAGAGAG";
char t3[] = "ABACAABADCABACABAABB";
char p3[] = "ABACAB";
//variavel para entrada de dados a partir do teclado
char t[TAM], p[TAM];
int opcao = 0; //para controlar o menu
while(1){
cout<<"\nDigite os valores para testar\n";
cout<<"\n(1) - Texto = CACACAU e Padrao = CACAU ";
cout<<"\n(2) - Texto = GCATCGCAGAGAGTATACAGTACG e Padrao = GCAGAGAG ";
cout<<"\n(3) - Texto = ABACAABADCABACABAABB e Padrao = ABACAB ";
cout<<"\n(4) - Valores digitados a partir do teclado ";
cout<<"\n(5) - Sair do programa ";
cout<<"\n\nEscolha uma opcao ?\b";
cin>>opcao;
if(opcao == 1){
cout<<"\n\n# BOYER-MOORE #\n\n";
boyerMoore(p1,t1);
cout<<"\n\n# KMP #\n\n";
kmp(p1,t1);
cout<<"\n\n# FORCA-BRUTA #\n\n";
forcaBruta(p1,t1);
}
if(opcao == 2){
cout<<"\n\n# BOYER-MOORE #\n\n";
boyerMoore(p2,t2);
cout<<"\n\n# KMP #\n\n";
kmp(p2,t2);
cout<<"\n\n# FORCA-BRUTA #\n\n";
forcaBruta(p2,t2);
}
if(opcao == 3){
cout<<"\n\n# BOYER-MOORE #\n\n";
boyerMoore(p3,t3);
cout<<"\n\n# KMP #\n\n";
kmp(p3,t3);
cout<<"\n\n# FORCA-BRUTA #\n\n";
forcaBruta(p3,t3);
}
if(opcao == 4){
cout<<"digite a sequencia de texto ";
fflush(stdin);
gets(t);
cout<<"digite a sequencia a ser procurada";
fflush(stdin);
gets(p);

if(strlen(t) <= strlen(t)){
int v1=strlen(t),v2=strlen(p);
cout<<"\nTexto nao pode ser maior que o padrao de busca! ";
while(v1 <= v2 ){
cout<<"digite a sequencia de texto ";
fflush(stdin);
gets(t);
cout<<"digite a sequencia a ser procurada";
fflush(stdin);
gets(p);
v1=strlen(t);
v2=strlen(p);
}
}
cout<<"\n\n# BOYER-MOORE #\n\n";
boyerMoore(p,t);
cout<<"\n\n# KMP #\n\n";
kmp(p,t);
cout<<"\n\n# FORCA-BRUTA #\n\n";
forcaBruta(p,t);
}
if(opcao == 5)
exit(1); //força a saida!
} //fim while do menu
} //fim do programa principal

Analise dos algoritmos

Força Bruta

O algoritmo apresentado não é eficiente, pois não usufruiu de nenhuma otimização no processamento dos caracteres. Sua complexidade de tempo é O((n-m+1)*m).

Boyer – Moore

A análise do algoritmo de Boyer- depende apenas do padrão e do alfabeto em questão. A complexidade de tempo e de espaço do BM para esta fase é O(m+c). O pior caso do algoritmo é O(n+M) onde r é igual ao número total de casamentos, o que torna o algoritmo ineficiente quando o número de casamentos é grande. O melhor caso e o caso médio para o algoritmo é O(n/m), ou seja, um resultado muito bom!

KMP

A complexidade do KMP é O(n) + O(m) . Quando se tem textos onde é difícil encontrar palavras que possuem caracteres repetidos, sufixo igual ao prefixo, a complexidade do KMP aproxima-se à do Força-Bruta O(mxn).