Aluno: Mateus Conrad B. da Costa
A busca por padrões assume papel relevante em diversas áreas de aplicação,
tanto a busca exata como a busca aproximada. Na busca exata deseja-se encontrar
todas a ocorrências de um dado padrão P em T. Especificamente busca-se pelo
conjunto de posições iniciais f, tal que 
tal que
.
Em algumas áreas de aplicação algoritmos de busca aproximada desempenham papel
fundamental. Nestes, a busca se dá por um casamento aproximado do padrão,
(não necessariamente exato). Este problema, denominado casamento aproximado de
padrões, implica em encontrar todas as substrings em T que são próximas
de P sob um determinado critério de proximidade.
O critério de proximidade pode variar de acordo com a necessidade do problema.
Neste trabalho foi construído um sistema de busca sequencial por padrões
utilizando dois algoritmos: Wu-Mamber que implementa o casamento aproximado e o
algortimo Boyer-Moore-Horspool para buscas exatas. O sistema permite
a busca aproximada e exata utilizando o algoritmo Wu-Mamber e também a busca
exata utilizando Boyer-Moore-Horspool. A seguir são discutidos os dois
algoritmos principais utilizados na implementação do sistema.
Seja a busca de um padrão P de tamanho m sobre um texto T de tamanho n.
Busca exata
Seja R um arranjo de bits de tamanho m. Rj é um valor do vetor R depois do
caracter j (de T) já ter sido processado. O vetor Rj contém informação sobre
todos os casamentos de prefixos de P que acabam em j. Mais precisamente ,
Rj[i]=1 se os primeiros i caracteres do padrão casam exatamente com os
últimos i caracteres antes de J no texto. Ou seja:
![$ R_j[i]=1 \quad se \quad (p_1p_2 \dots p_i = t_{j-i+1} t_{j-i+2} \dots t_j$](img3.gif){kind=small}
Para cada i tal que Rj[i]=1 necessitamos checar se tj+1 = pi+1.
A transição entre Rj e Rj+1 pode ser sumarizada como:
Inicialmente R0[i]=0 para todo i tal que 
e
R0[0]=1
![$R_{j+1}[i]= 1 \quad se \quad R_j[i-1]=1 \quad e \quad p_i = t_{j+1}.$](img5.gif){kind=small}
e
Rj+1[i]= 0 caso contrário.
Se Rj+1[m]= 1 então, um casamento foi encontrado em j-m+2
Ou seja, na transição entre os Rj é determinado se existe um prefixo casado
ou não.
A velocidade do Algoritmo Wu-Manber está na rapidez com que as transições são
computadas. As transições são feitas utilizando um conjunto de máscaras para o
alfabeto do padrão procurado. As mascaras são construídas da seguinte forma:
Para cada caracter si no alfabeto constroi-se um vetor de bits Si de
tamanho m tal que Si[r]=1 se pr=Si. Em outras palavras, Si denota os
índices no padrão que contém Si. Por exemplo Se o padrão for ica os
vetores são:
A transição de Rj para Rj+1 é implementada por uma operação de
deslocamento a direita de Rj e um and do resultado do
deslocamento com o vetor Si, onde Si=tj+1
Busca com erros
A implementação do esquema de busca com erros leva em conta erros de inserção,
remoção e substituição.
Para a busa permitindo apenas 1 erros necessitamos de um registrador a mais.
Vejamos como exemplo o caso da Inserção: Neste caso, busca-se encontrar todas os
intervalos de tamanho máximo m+1 que contenha o padrão. Agora teremos duas
possibilidades para o casamento do prefixo: o casamento exato ou o casamento
com um inserção.
Assim, o novo registrado R¹j indicará os possíveis
casamentos com no máximo uma inserção. R¹j[i]=1 se os primeiros i
caracteres do padrão casam com i dos últimos i+1 caracteres até j no texto.
A transição ocorrerá nos seguintes casos:
I1 - Existe um casamento extao para os primeiros i caracteres até tj. Neste
caso, inserindo tj+1 no final do casamento exato cria um casamento com uma
inserção.
I2 - Existe um casamento do primeiros i-1 caracteres até tj com uma
inserção e tj+1=pi. Neste caso a inserção está em alguma posição do padrão
diferente do fim.
O caso I1 pode ser resolvido apenas copiando o valor de R para R¹ e I2 é
feito com um deselocamento a direita de R¹ e uma operação de AND com
Si onde Si=tj.
Da mesma forma são definidas as operações de remoção e de substituição.
Considerando os Registradores R0 e R1 e as situações anterior e atual
dos mesmos temos a seguinte equação de transição:
![$ R_1^{AT} = (R_0{ANT} \gt\gt 1) \vert (R_0^{AT}\gt\gt 1) \vert R_1{ANT} \gt\gt 1) \& S[t[i]] $](img9.gif){kind=small}
Quando consideramos a busca com um erro a mais, um novo registrador deve ser
inserido. Para a busca com dua remoções por exemplo, teremos a seguinte equação:
![$ R_2^{AT} = (R_0{AT} \gt\gt 2) \vert (R_1^{AT}\gt\gt 1) \vert R_2{ANT} \gt\gt 1) \& S[t[i]] $](img10.gif){kind=small}
A explicação detalhada das transições pode ser encontrada em [1].
A implementação do algoritmo se dá em duas etapas principais: O preprocessamento
e a busca. No preprocessamento o principal objetivo é a construção das máscaras.
Na busca são realizadas as transições. Sempre que um registrador recebe 1 na
posição m, temos a indicação de que um padrão foi encontrado. Dependendo do
registrador saberemos se o casamento foi com 
erros.
Estes registradores e as transições são implementações do autômato finito que
modela as transições. da busca.
O padrão é inicialmente casado com o inicio do texto. O programa procede
comparando os caracteres do padrão da direita para a esquerda. Enquanto se dá o
casamento os mesmo continua realizando as comparações. Se o padrão é percorrido
completamente, o casamento exato foi encontrado.
Quando ocorre não ocorre o casamento de um dos caracteres do padrão, a
comparação é interrompida e o padrão é deslocado sobre o texto de acordo com a
máscara do próximo caracter do texto. As máscaras são iguais ao tamanho do
padrão m para todos os caracteres que não estão no padrão, 0 para o
caracter da última posição do padrão e m subtraído da maior distância do
caracter no padrão até a posição 0.
Este deslocamento dependerá do caracter queda posição de cada caracter do alfabeto usado no padrão. Quando uma comparação verifica uma diferença entre os padrões, o deslocamento sobre o texto se dará de um número de caracteres equivalente a distância calculada no preprocessamento para o texto em questão,
Conforme visto em sala[4], a complexidade do algoritmo B-M-H é, para o pior caso,
f(BMH)= O(n.m)
No melhor caso o B-M-H é O(n/m), onde n é o tamanho do texto e m o tamanho do padrão procurado.
Para realizar o pré processamento o algoritmo tem um custo de O(c)
onde c é o tamanho do alfabeto.
A complexidade do Wu-Manber segundo Nívio Ziviani em [3] é
O(k.n), onde 
é o número de erros e n é o tamanho do texto.
Uso: campeia -[m[er]] -[w][c][n][v][B] p arq -m : Faz a busca exata do padrão <p> sobre o arquivo <arq> usando o algoritmo Wu-Mamber -m[er] : Faz a busca aproximada do padrão <p> sobre o arquivo <arq> usando o algoritmo Wu-Mamber com <er> erros Opções: -w - Busca da palavra completa sem sufixos nem prefixos -n - Apresenta o número da linha onde o padrão é encontrado -c - Omite as linhas onde o padrão é encontrado -v - Imprime as linhas onde o padrão não é encontrado -B - Busca pelo melhor casamento possívelA seguir são apresentados o módulo campeia.c e seu header file.
/* - Universidade Federal de Minas Gerais
- Departamento de Ciência da omputação
- Disciplina: Projeto e Análise de Algoritmos
- Professor: Nívio Ziviani
- Aluno: Mateus Conrad Barcellos da Costa -
- Doutorado em Ciência da Computação
- Trabalho Prático III: Construção de um sistema
de busca sequencial em textos
- Descrição: Utilização dos algoritmos de Busca sequencial em texto:
Wu-Mamber e Boyer-Moore-Horspool para a construção do sistema de busca
sequencial por padrões em arquivos de texto. Para o algoritmo Wu-Mamber
será utilizada a implementação construída por Marcio Drumond Araujo (1992),
disponibilizada em:
http://www.dcc.ufmg.br/nivio/cursos/pa02/tp3/pa02tp3.html (julho/2002).
Para o algoritmo Boyer-Moore-Horspool foi utilizada a
função disponível em:
ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/7/713b.srch.c
- Data da ultima alteração: 16/08/2002
*/
/*
Inclusão de Arquivos de cabeçalho
*/
#include <stdio.h>
#include <stddef.h>
#include "campeia.h"
long S[ALPHABET_SIZE], /* mascaras dos caracteres do alfabeto */
valid[ALPHABET_SIZE], /* diz se o caractere faz parte de palavras */
Start[MAX_NUMBER_OF_ERRORS], /* mascaras de inicializacao */
M; /* mascara que diz onde a busca
obrigatoriamente e' exata no padrao */
/* Funcão bmhprep: Implementação do preprocessamento do algoritmo BMH.
Objetivo: Construi o vetor de Desolocamento para ser utilizando no algoritmo
BMH.
Parâmetros:
char *pat: Padrão procurado
char *text: texto a ser pesquisado
int *skip: Vetor de deslocamento que será construído
*/
int bmhprep( char *pat, char *text, int *skip)
{
int register i, j, k;
int m;
m = strlen(pat); /* atribui o valor do tamanho do padrão a todas
as mascaras*/
for( k=0; k<MAXCHAR; k++)
skip[k] = m;
/* para os caracateres que estão no padrao (fora o último) redefine o valor
da mascara*/
for( k=0; k<m-1; k++ )
skip[pat[k]] = m-k-1;
}
/*
Função bmhs : Implementação do algoritmo: Boyer-Moore-Horspool
Objetivo: Realizar a busca sequencial exata por um padrão em um texto
Parametros de Entrada:
char *pat - padrão a ser procurado
char *text - texto alvo
valor de retorno:
1 se encontrou o padrão no texto e 0 caso contrario
*/
int bmhs( char *pat, char *text, int *skip, int n, int m )
{
int register i, j, k;
/*Percorre o texto iniciando a m posições frente
O indice e incrementado de acordo
com a mascara do caracter em questão*/
for( k=m-1; k < n; k += skip[text[k] & (MAXCHAR-1)] ) {
/*Enquanto houver casamento a comapração continua
até o inicio do padrão*/
for( j=m-1, i=k; j>=0 && text[i] == pat[j]; j-- )
i--;
/*Se houver um casamento retorna om 1 */
if( j == (-1) )
return(1);
}
return(0);
}
/*
Função: ConfiguraBusca
Autor: Mateus Conrad Barcellos da Costa
Objetivos: Ler os parâmetros de entrada, determinar o padrão a ser procurado,
o arquivo onde se dará a busca e configurar o vetor de opções que irá guiar
a execução do programa de acordo com a definição da interface
Parâmetros:
int c - número de argumentos passados
char *v[] - vetor de argumentos
short *op - vetor representativo das opcoes do usuário
char *pat - padrao procurado
char *file - Arquivo
Valor de retorno:
- 0 se ocorreu um erro de número de parametros
- 1 se nao ocorreu nenhum erro
*/
int ConfiguraBusca(int c, char *v[], short *op, char *pat, char *file){
int register i,j;
char *paux;
for(i=0;i<10;i++)
op[i]=0;
if (c==1){
/* imprimir as opçoes e o modo de uso */
printf("campeia 1.0 - Busca de padroes em arquivos \n");
printf("Uso: campeia -[m[er]] -[w][c][n][v][B] p arq\n");
printf("-m : Faz a busca exata do padrão <p> sobre o arquivo <arq> usando
o algoritmo Wu-Mamber\n");
printf("-m[er] : Faz a busca aproximada do padrão <p> sobre o arquivo
<arq> usando o algoritmo Wu-Mamber com <er> erros\n");
printf("Opções: \n");
printf(" -w - Busca da palavra completa sem sufixo nem prefixos\n");
printf(" -n - Apresenta o número da linha onde o padrão é encontrado \n");
printf(" -c - Omite as linhas onde o padrão é encontrado\n");
printf(" -v - Imprime as linhas onde o padrão não é encontrado\n");
printf(" -B - Busca pelo melhor casamento possível\n");
return(0);
}
if (c < MINARG){
fprintf(stderr, "%s\n", E_ARG_INS);
return 0;
}
if (c > ARG){
fprintf(stderr, "%s\n", E_ARG_EXT);
return 0;
}
if(c == 3) {
/* Se o numero de parametros for igual a 3 atribuo os dois ultimos
parametros ao padrao e ao arquivo */
strcpy(pat,v[1]);
strcpy(file,v[2]);
return 1; /* retorno com os valores do padrao e do arquivo */
}
/* Se o numero de parametros for maior que 3 monto as opcoes*/
if (v[1][0]=='-') {
/* podera ser o parametro da busca com erros ou o das opcoes*/
if (v[1][1]=='m') {
/*é a opção de busca aproximada*/
paux=&v[1][2];
if (*paux)
/*guardo o número de erros na posicao 0 do vetor op*/
op[0]=atoi(paux);
else
op[0]=-1;
}
else {
paux=&v[1][1];
while(*paux){
switch(*paux) {
case 'w': op[1]=1;
break;
case 'c': op[2]=1;
break;
case 'n': op[3]=1;
break;
case 'v': op[4]=1;
break;
case 'B': op[5]=1;
break;
}
paux++;
}
}
}
if (v[2][0]=='-') {
paux=&v[2][1];
while(*paux){
switch(*paux) {
case 'w': op[1]=1;
break;
case 'c': op[2]=1;
break;
case 'n': op[3]=1;
break;
case 'v': op[4]=1;
break;
case 'B': op[5]=1;
break;
}
paux++;
}
strcpy(pat,v[3]);
strcpy(file,v[4]);
return 1;
}
else {
/*O parametro 2 é o padrao e o 3 o file */
strcpy(pat,v[2]);
strcpy(file,v[3]);
return 1;
}
}
/* Funcao : preproc
Autor: Marcio Droumond Araujo
Objetivos : preprocessar o padrao, montando as mascaras de inicializacao,
dos caracteres do alfabeto e a de busca exata obrigatoria
Parametros:
char * p: padrao
long k: numero de erros
*/
void preproc(char *p, long k) {
int i,
j,
m; /* pattern size */
m = strlen(p);
for (i = 0; i < (k + 1); i++) { /* inicializa mascaras de inicializacao */
Start[i] = 0;
for (j = 0; j <= i; j++) {
Start[i] |= 1 << (m - j);
}
}
for (i = 0; i < ALPHABET_SIZE; i++) {
S[i] = 0;
valid[i] = ((i >= 'a') && (i <= 'z')) || ((i >= 'A') && (i <= 'Z'));
}
M = 0;
for (i = 0; i < m; i++) { /* inicializa mascaras de caracteres do alfabeto */
if (((p[i] >= 'a') && (p[i] <= 'z')) || ((p[i] >= 'A') && (p[i] <= 'Z'))) {
S[p[i]] |= 1 << (m - 1 - i);
M |= 1 << (m - 1 - i);
}
else {
S[' '] |= 1 << (m - 1 - i);
}
}
for (i = 0; i < ALPHABET_SIZE; i++) {
if (!valid[i]) {
S[i] = S[' '];
}
}
}
/* Funcao : Wu_Manber
Autor: Marcio Droumond Araujo - 1992
Objetivos : verifica se um padrao ocorre ou nao numa sequencia, com um
numero de erros menor ou igual a k
Parametros:
- char *p: padrao
- char *t: a sequencia
- long k: numero de erros
-Valor de retorno: 1 se o padrao ocorre na sequencia ou 0, caso
contrario.
*/
long Wu_Manber(char *p, char *t, long k) {
long i,
j,
m, /* tamanho do padrao */
n, /* tamanho da sequencia */
matchfound, /* diz se um casamento foi encontrado */
R0[MAX_NUMBER_OF_ERRORS], /* mascaras de estado anterior */
R1[MAX_NUMBER_OF_ERRORS]; /* mascaras de estado atual */
char newt[MAX_MODIFIED_LINE_SIZE]; /* sequencia entre espacos */
strcpy(newt, " ");
strcat(newt, t);
strcat(newt, " ");
n = strlen(newt);
m = strlen(p);
matchfound = FALSE;
for (i = 0; i <= k; i++) { /* inicializa mascaras de estado */
R1[i] = Start[i];
R0[i] = Start[i];
}
for (i = 0; i < n; i++) { /* executa o algoritmo */
R1[0] = ((R0[0] >> 1) & S[newt[i]]) | (Start[0] & R0[0]);
for (j = 1; j <= k; j++) {
R1[j] = ((R0[j] >> 1) & S[newt[i]]) |
((R0[j-1] | ((R1[j-1] | R0[j-1]) >> 1)) & M) | (Start[0] & R0[j]);
}
for (j = 0; j <= k; j++) { /* atribui estado atual no anterior */
R0[j] = R1[j];
if (R1[j] & 1) { /* se bit menos significativo estiver ativo, entao
tem-se um casamento na linha atual do texto */
matchfound = TRUE;
}
}
}
return matchfound;
}
/****************
Função Main()
Objetivo: Chamar as funções de busca sequencial para realizar a
busca do padrão desejado de acordo com os parâmetros de entrada
Parâmetros de entrada:
- opções
- padrão
- arquivo
Default: campeia <padrao> <arquivo>
Busca no arquivo o padrão usando o bmh e
aprasenta a linha em que foi encontrado o padrão e o número de ocorrências
total.
Número de parâmetros 3,
argv[1]: padrao
argv[2]: arquivo
campeia <-m[erros]> <-wcn> <padrao> <arquivo>
-m[erros] - busca permitindo erros: O resto do parâmetro é o número de erros
permitidos
-w - Busca por palavras sem sufixos nem prefixos
-c - imprime apenas o número de ocorrência do padrão
-n - imprime o número da linha onde ocorreu o padrão
-v - imprime as linhas que não comtem
-B - Busca pelo melhor casamento possível
****************/
int main(int argc, char *argv[]) {
FILE *fp; /* text file id */
char line[MAX_LINE_SIZE], /* linha do arquivo texto */
pat[MAX_PATTERN_SIZE],
p[MAX_PATTERN_SIZE], /* padrao a ser pesquisado */
filename[MAX_FILE_NAME_SIZE]; /* nome do arquivo texto */
long i,
j,
m, /* tamanho do padrao */
k, /* numero de erros */
wx, /*Conta número de busca*/
nl;
int n,skip[MAXCHAR]; /* Vetor de máscara de deslocamento do BMH*/
short opcoes[10], /*vetor de opções montado em ConfiguraBusca*/
bestmatch; /* usada para controlar a busca com a opao -B*/
if(ConfiguraBusca(argc,argv,opcoes,pat,filename)) /* obtem os parâmetros da
busca a ser feita */
{
printf("Nome do arquivo: %s\n", filename);
printf("Padrao: %s\n", pat);
if(opcoes[0]){
if (opcoes[0]==-1){
if(!opcoes[5])
printf("Busca exata com o esquema Wu-Mamber\n", opcoes[0]);
k=0;
}
else{
printf("Busca aproximada com %d erros\n", opcoes[0]);
k=opcoes[0];
}
}
else
printf("Busca exata com o esquema B-M-H\n", opcoes[0]);
if (opcoes[1]){
strcpy(p, " "); /* p recebe um espaco como primeiro caractere */
strcat(p, pat); /* p recebe o padrao propriamente dito */
strcat(p, " "); /* p recebe um espaco como ultimo caractere */
printf("-w - Busca por palavras sem sufixos nem prefixos\n");
}
else {
strcpy(p, pat);
}
if (opcoes[2])
printf("-c - imprime apenas o número de ocorrências do padrão\n");
if(opcoes[3])
printf("-n - imprime o número da linha onde ocorreu o padrão\n");
}
else {
return 0;
}
if(opcoes[0]) { /* a busca será feita com o esquema Wu-Mamber e será feito o
preprocessamento e verificacao do número de erros*/
if (opcoes[0] > MAX_NUMBER_OF_ERRORS) {
/* valida o numero de erros da
busca */
fprintf(stderr, "Numero de erros maior que o maximo
permitido\n");
exit(1);
}
m = strlen(p); /* m armazena o tamanho do padrao */
if (m > MAX_PATTERN_SIZE - 2) { /* valida o tamanho do padrao considerando
a insercao de 2 espacos, antes e depois
do padrao */
fprintf(stderr, "Tamanho do padrao maior que o maximo permitido\n");
return(0);
}
if (k >= m) {
fprintf(stderr, "Numero de erros nao e menor que o tamanho do padrao\n");
return(0);
}
preproc(p, k);
}
if((fp= fopen(filename, "r"))==NULL){
fprintf(stderr,"%s", E_ARQ_INV);
return (0);
}
wx=0;
if(opcoes[0]){
/* Faz a busca usando o esquema Wu-Mamber */
if(opcoes[5]) {/* Busca procurando o melhor casamento possível*/
printf("-B - Busca pelo melhor casamento possível\n");
bestmatch=0;
k=0;
while(!bestmatch && ((k<strlen(p)-2)) &&(k<MAX_NUMBER_OF_ERRORS) ){
nl=0;
rewind(fp);
while(fgets(line, MAX_LINE_SIZE, fp)) {
/* enquanto houver linhas no arquivo*/
line[strlen(line) - 1] ='\0';
nl++;
if (Wu_Manber(p, line, k)) {
wx++;
if(!opcoes[2]){
if(!opcoes[4]){ /* imprimira as linhas que não possuem o
padrao*/
if(opcoes[3]) /*imprime o número da linha */
printf("line: %d==> ",nl);
printf("File %s:=> %s\n", filename, line);
}
}
}
else{
if(opcoes[4]){ /* imprimira as linhas que não possuem o padro*/
if(opcoes[3]) /*imprime o número da linha */
printf("line: %d==> ",nl);
printf("File %s:=> %s\n", filename, line);
}
}
}
if(wx>0)
bestmatch=1;
k++;
}
}
else{
/* executo o wu-mamber normal*/
while(fgets(line, MAX_LINE_SIZE, fp)) {
/* enquanto houver linhas no arquivo*/
line[strlen(line) - 1] ='\0';
nl++;
if (Wu_Manber(p, line, k)) {
wx++;
if(!opcoes[2]){
if(!opcoes[4]){ /* imprimira as linhas que não possuem o
padrao*/
if(opcoes[3]) /*imprime o número da linha */
printf("line: %d==> ",nl);
printf("File %s:=> %s\n", filename, line);
}
}
}
else{
if(opcoes[4]){ /* imprimira as linhas que não possuem o padrao*/
if(opcoes[3]) /*imprime o número da linha */
printf("line: %d==> ",nl);
printf("File %s:=> %s\n", filename, line);
}
}
}
}
}
else{
/* Faz a busca com o esquema B-M-H*/
bmhprep(p,line,skip);
m=strlen(p);
while(fgets(line, MAX_LINE_SIZE,fp)) { /* enquanto houver linhas no arquivo*/
n=strlen(line);
line[n - 1] = '\0';
// printf("%s\n", line);
if (bmhs( p, line, skip, n,m))
{
wx++;
if(!opcoes[2]){
if(!opcoes[4]){ /* imprimira as linhas que não possuem o padro*/
if(opcoes[3]) /*imprime o número da linha */
printf("line: %d==> ",nl);
printf("File %s:=> %s\n", filename, line);
}
}
}
else{
if(opcoes[4]){ /* imprimira as linhas que não possuem o padro*/
if(opcoes[3]) /*imprime o número da linha */
printf("line: %d==> ",nl);
printf("File %s:=> %s\n", filename, line);
}
}
}
}
printf("Numero de ocorrencias %d\n", wx);
close(fp);
return 0;
}
Arquivo de Cabeçalho: campeia.h/** UFMG- DCC - Campeia.h - Arquivo de cabeçalho de campeia.c: Sistema de programas para busca de padroes em texto Autoria:Mateus Conrad B. da Costa Doutorado em Ciência da Computação Data da ultima alteração: 16/08/2002 Definição de constantes **/ #define TRUE 1 #define FALSE 0 #define ALPHABET_SIZE 256 #define MAX_LINE_SIZE 4096 #define MAX_MODIFIED_LINE_SIZE 4096 #define MAX_PATTERN_SIZE 29 /* considerando uma palavra de 32 bits */ #define MAXCHAR 256 /* considerando uma palavra de 32 bits */ #define MAX_NUMBER_OF_ERRORS 28 /* considerando uma palavra de 32 bits */ #define MAX_FILE_NAME_SIZE 256 #define ARG 5 #define MINARG 3 #define E_ARG_INS "Erro: Numero de argumetos insuficientes" #define E_ARG_EXT "Erro: Numero de argumetos em excesso" #define E_ARQ_INV "Erro: Nome do arquivo inválido" /* Protótipos das funçeoes */ int bmhprep( char *pat, char *text, int *skip); int bmhs( char *pat, char *text, int *skip, int n, int m ); int ConfiguraBusca(int c, char *v[], short *op, char *pat, char *file); void preproc(char *p, long k); long Wu_Manber(char *p, char *t, long k);
Para apresentar a funcionalidade, será usado o arquivo bandeira contendo o poema abaixo:
Teu corpo claro e perfeito,Testes
(Manuel Bandeira)
1 Teu corpo de maravilha,
2 Quero possuí-lo no leito
3 Estreito da redondilha...
4 Teu corpo é tudo o que cheira...
5 Rosa... flor de laranjeira...
6 Teu corpo macio,
7 É como um véu de noivado...
8 Teu corpo é pomo doirado...
9 Rosal queimado do estio,
10 Desfalecido em perfume...
11 Teu corpo é a brasa do lume...
12 Teu corpo é chama e flameja
13 Como à tarde os horizontes...
14 É puro como nas fontes
15 A água clara que serpeja,
16 Quem em antigas se derrama...
17 Volúpia da água e da chama...
18 A todo o momento o vejo...
19 Teu corpo... a única ilha
20 No oceano do meu desejo...
21 Teu corpo é tudo o que brilha,
22 Teu corpo é tudo o que cheira...
23 Rosa, flor de laranjeira...
[mcosta@abrolhos zip]$ ./campeia Uso: campeia -[m[er]] -[w][c][n][v][B] p arq -m : Faz a busca exata do padrão <p> sobre o arquivo <arq> usando o algoritmo Wu-Mamber -m[er] : Faz a busca aproximada do padrão <p> sobre o arquivo <arq> usando o algoritmo Wu-Mamber com <er> erros Opções: -w - Busca da palavra completa sem sufixo nem prefixos -n - Apresenta o número da linha onde o padrão é encontrado -c - Omite as linhas onde o padrão é encontrado -v - Imprime as linhas onde o padrão não é encontrado -B - Busca pelo melhor casamento possível
[mcosta@abrolhos zip]$ ./campeia ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema B-M-H File bandeira:=> Teu corpo de maravilha, File bandeira:=> Estreito da redondilha... File bandeira:=> Teu corpo... a única ilha File bandeira:=> Teu corpo é tudo o que brilha, Numero de ocorrencias 4 [mcosta@abrolhos zip]$ ./campeia -m ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema Wu-Mamber File bandeira:=> Teu corpo de maravilha, File bandeira:=> Estreito da redondilha... File bandeira:=> Teu corpo... a única ilha File bandeira:=> Teu corpo é tudo o que brilha, Numero de ocorrencias 4
[mcosta@abrolhos zip]$ ./campeia -w ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema B-M-H -w - Busca por palavras sem sufixos nem prefixos File bandeira:=> Teu corpo... a única ilha Numero de ocorrencias 1 [mcosta@abrolhos zip]$ ./campeia -m -w ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema Wu-Mamber -w - Busca por palavras sem sufixos nem prefixos File bandeira:=> Teu corpo... a única ilha Numero de ocorrencias 1
[mcosta@abrolhos zip]$ ./campeia -wc ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema B-M-H -w - Busca por palavras sem sufixos nem prefixos -c - imprime apenas o número de ocorrências do padrão Numero de ocorrencias 1 [mcosta@abrolhos zip]$ ./campeia -m -wc ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema Wu-Mamber -w - Busca por palavras sem sufixos nem prefixos -c - imprime apenas o número de ocorrências do padrão Numero de ocorrencias 1
[mcosta@abrolhos zip]$ ./campeia -m -wn ilha bandeira Nome do arquivo: bandeira Padrao: ilha Busca exata com o esquema Wu-Mamber -w - Busca por palavras sem sufixos nem prefixos -n - imprime o número da linha onde ocorreu o padrão line: 23==> File bandeira:=> Teu corpo... a única ilha Numero de ocorrencias 1
[mcosta@abrolhos zip]$ ./campeia -m -vn corpo bandeira Nome do arquivo: bandeira Padrao: corpo Busca exata com o esquema Wu-Mamber -n - imprime o número da linha onde ocorreu o padrão line: 1==> File bandeira:=> line: 3==> File bandeira:=> (Manuel Bandeira) line: 4==> File bandeira:=> line: 6==> File bandeira:=> Quero possuí-lo no leito line: 7==> File bandeira:=> Estreito da redondilha... line: 9==> File bandeira:=> Rosa... flor de laranjeira... line: 11==> File bandeira:=> É como um véu de noivado... line: 13==> File bandeira:=> Rosal queimado do estio, line: 14==> File bandeira:=> Desfalecido em perfume... line: 17==> File bandeira:=> Como à tarde os horizontes... line: 18==> File bandeira:=> É puro como nas fontes line: 19==> File bandeira:=> A água clara que serpeja, line: 20==> File bandeira:=> Quem em antigas se derrama... line: 21==> File bandeira:=> Volúpia da água e da chama... line: 22==> File bandeira:=> A todo o momento o vejo... line: 24==> File bandeira:=> No oceano do meu desejo... line: 27==> File bandeira:=> Rosa, flor de laranjeira... line: 28==> File bandeira:=> Numero de ocorrencias 10
[mcosta@abrolhos zip]$ ./campeia -m -nB brama bandeira Nome do arquivo: bandeira Padrao: brama -n - imprime o número da linha onde ocorreu o padrão -B - Busca pelo melhor casamento possível line: 15==> File bandeira:=> Teu corpo é a brasa do lume... line: 20==> File bandeira:=> Quem em antigas se derrama... Numero de ocorrencias 2
[mcosta@abrolhos zip]$ ./campeia -m1 -n brama bandeira Nome do arquivo: bandeira Padrao: brama Busca aproximada com 1 erros -n - imprime o número da linha onde ocorreu o padrão line: 15==> File bandeira:=> Teu corpo é a brasa do lume... line: 20==> File bandeira:=> Quem em antigas se derrama... Numero de ocorrencias 2 [mcosta@abrolhos zip]$ ./campeia -m2 -n naranjera bandeira Nome do arquivo: bandeira Padrao: naranjera Busca aproximada com 2 erros -n - imprime o número da linha onde ocorreu o padrão line: 9==> File bandeira:=> Rosa... flor de laranjeira... line: 27==> File bandeira:=> Rosa, flor de laranjeira... Numero de ocorrencias 2 [mcosta@abrolhos zip]$ ./campeia -m4 -n "No mariano" bandeira Nome do arquivo: bandeira Padrao: No mariano Busca aproximada com 4 erros -n - imprime o número da linha onde ocorreu o padrão line: 24==> File bandeira:=> No oceano do meu desejo... Numero de ocorrencias 1 [mcosta@abrolhos zip]$ ./campeia -m1 -nw ilja bandeira Nome do arquivo: bandeira Padrao: ilja Busca aproximada com 1 erros -w - Busca por palavras sem sufixos nem prefixos -n - imprime o número da linha onde ocorreu o padrão line: 23==> File bandeira:=> Teu corpo... a única ilha Numero de ocorrencias 1 [mcosta@abrolhos zip]$ ./campeia -m1 -n ilja bandeira Nome do arquivo: bandeira Padrao: ilja Busca aproximada com 1 erros -n - imprime o número da linha onde ocorreu o padrão line: 5==> File bandeira:=> Teu corpo de maravilha, line: 7==> File bandeira:=> Estreito da redondilha... line: 23==> File bandeira:=> Teu corpo... a única ilha line: 25==> File bandeira:=> Teu corpo é tudo o que brilha, Numero de ocorrencias 4
I. Tempos obtidos para a busca dos padrões especificados sobre o
arquivo wsj98: 2821600 bytes - (em segundos)
II. Tempos obtidos para a busca dos padrões especificados sobre o
arquivo wsj88_10 10138622 bytes (em segundos)
Padrão
4c| Busca Exata
2c| Busca Aproximada - 1 erro
2c| Busca Aproximada - 2 erros
Wu-Mamber
B-M-H
grep
agrep
Wu-Mamber
agrep
Wu-Mamber
agrep
DCC
3.72
0.5
0.5
0.1
7.01
0.3
10.36
0.55
dollar
3.79
0.36
0.5
0.1
6.97
0.1
10.30
0.82
branco
3.75
0.33
0.5
0.1
7.04
0.23
10.28
0.89
administration
3.79
0.32
0.5
0.1
7.01
0.1
10.14
0.54
coffee
3.77
0.36
0.5
0.1
7.0
0.16
10.28
0.61
sotck
3.78
0.42
0.5
0.1
7.19
0.3
10.34
1.97
Exchange
3.75
0.35
0.5
0.1
6.98
0.17
10.29
0.89
Price Index
3.75
0.30
0.5
0.1
7.0
0.11
10.32
0.54
Média
3.76
0.36
0.5
0.1
7.02
0.18
10.28
0.85
Padrão
4c| Busca Exata
2c| Busca Aproximada - 1 erro
2c| Busca Aproximada - 2 erros
Wu-Mamber
B-M-H
grep
agrep
Wu-Mamber
agrep
Wu-Mamber
agrep
DCC
9.64
1.73
0.88
0.16
17.33
0.65
24.68
1.63
dollar
9.34
1.25
1.17
0.12
17.12
0.33
24.66
1.63
branco
9.32
1.30
1.06
0.16
17.36
0.32
24.58
1.86
administration
9.44
1.05
1.33
0.11
17.47
0.51
24.67
1.09
coffee
9.52
1.30
1.20
0.22
17.08
0.34
24.72
1.21
sotck
9.32
1.34
1.27
0.14
17.48
0.71
24.64
4.16
Exchange
9.57
1.19
0.92
0.17
17.24
0.31
24.54
1.93
Price Index
9.32
1.09
0.86
0.08
17.32
0.42
24.65
0.72
Média
9.43
1.28
1.08
0.14
17.3
0.44
24.64
1.77
III. Tempos obtidos para a busca dos padrões especificados sobre o
arquivo wsj88_20 20279274 bytes (em segundos)
IV. Tempos obtidos para a busca dos padrões especificados sobre o
arquivo wsj88 109450208 bytes (em segundos)
Padrão
4c| Busca Exata
2c| Busca Aproximada - 1 erro
2c| Busca Aproximada - 2 erros
Wu-Mamber
B-M-H
grep
agrep
Wu-Mamber
agrep
Wu-Mamber
agrep
DCC
18.51
2.48
1.98
0.34
34.38
1.23
49.74
1.66
dollar
18.78
2.53
2.2
0.32
34.61
0.67
49.86
3.28
branco
18.57
2.57
2.11
0.31
34.6
0.59
49.79
3.64
administration
18.66
2.17
2.53
0.20
34.39
0.89
49.78
2.20
coffee
19.0
2.66
2.33
0.29
34.51
0.70
49.60
2.36
sotck
18.57
2.69
2.52
0.30
34.35
1.37
50.18
8.51
Exchange
18.70
2.32
2.02
0.32
34.58
0.53
49.91
3.91
Price Index
18.63
2.27
2.01
0.21
34.57
0.70
49.86
1.46
Média
18.67
2.46
2.21
0.28
34.49
0.83
49.84
3.37
V. Tempos obtidos para a busca exata de um padrão sobre um
arquivo de teste
Padrão
4c| Busca Exata
2c| Busca Aproximada - 1 erro
2c| Busca Aproximada - 2 erros
Wu-Mamber
B-M-H
grep
agrep
Wu-Mamber
agrep
Wu-Mamber
agrep
DCC
99.86
17.8
10.27
1.94
185.02
6.4
268.28
9.21
dollar
100.07
13.68
11.87
1.45
184.81
3.5
270.43
17.23
branco
99.58
14.34
10.89
2.51
183.6
3.48
271.43
19.85
administration
99.64
11.64
13.59
1.02
184.43
5.13
268.87
11.67
coffee
99.47
14.31
11.7
1.65
184.72
3.64
270.91
12.26
sotck
99.66
14.65
10.57
1.37
183.52
7.45
271.5
45.21
Exchange
99.12
12.61
10.36
1.41
184.31
3.07
272.19
20.45
Price Index
99.81
11.48
10.6
0.87
184.69
3.94
267.3
7.48
Média
99.65
13.81
11.23
1.52
184.38
4.57
270.11
17.92
- Padrão: United States of America
- Arquivo: wsj88_10
- Busca Exata
Wu-Mamber
B-M-H
agrep
grep
0.07
0.92
0.09
1.0
VI. Tempos obtidos para a busca com erros de um padrão sobre os
arquivos especificados
Padrao: Administration
VII. Tempos obtidos para a busca com erros de um padrão longo sobre um
arquivo de teste
Arquivo
2c| 3 ERROS
2c| 5 ERROS
2c| 8 ERROS
Arquivo
Wu-Mamber
agrep
Wu-Mamber
agrep
Wu-Mamber
agrep
wsj89
8.89
0.42
13.04
1.68
18.99
2.62
wsj88_10
32.17
1.52
46.64
5.91
68.61
9.89
wsj88_20
63.86
3.07
93.25
11.93
137.23
20.08
wsj88
346.49
16.95
501.56
63.78
738.61
107.23
- Padrão: United States of America
- Arquivo: wsj88_10
- Busca Aproximada
Arquivo
2c| 3 ERROS
2c| 5 ERROS
2c| 8 ERROS
Arquivo
Wu-Mamber
agrep
Wu-Mamber
agrep
Wu-Mamber
agrep
wsj88_10
3.57
0.65
46.24
2.59
67.9
48.73
| Tam. aprox. do texto (Mbytes) | B-M-H | Wu-Manber | grep | agrep |
| 2 | 0.36 | 3.76 | 0.5 | 0.1 |
| 10 | 1.28 | 9.43 | 1.08 | 0.14 |
| 20 | 2.46 | 18.67 | 2.21 | 0.28 |
| 100 | 13.81 | 99.65 | 11.23 | 1.52 |
Comparações entre: Wu-Manber - B-M-H - grep
Podemos verificar que o sistema utilizando o B-M-H é competitivo com o sistema
grep, sendo que para arquivos menores os dois se equiparam. Observando
os experimentos no que se refere ao tamanho do padrão, vemos que o algoritmo
Wu-Manber tem comportamento constante (conforme esperado) e o B-M-H diminui com
o aumento do tamanho do padrão, de acordo com o caso médio esperado. Por
exemplo, no experimento IV temos uma busca pelo padrão ``DCC'' em 17.8s e uma
busca pelo padrão ``Price Index'' em 11.48 segundos. Já o sistema grep
possui comportamento constante com relação ao tamanho do padrão. Este
comportamento foi verificado também no experimento V, onde foi testada a busca
exata por um padrão longo (United States of America) e o tempo de busca do B-M-H
foi 0.09 segundos e do grep foi 0.1 segundos.
Em resumo, o sistema grep foi:
- 8.39 vezes mais rápido que o Wu-Manber
- 1.05 vezes mais rápido que o B-M-H
B-M-H X Wu-Manber
Na busca exata o B-M-H foi 7.99 vezes mais rápido que o Wu-Manber.
Considerando especificamente os algoritmos implementados notamos que o Algoritmo Wu-manber é mais lento que o B-M-H, embora no pior caso o Wu-Manber seja teoricamente melhor que o B-M-H. No entanto, para o experimento devemos considerar o caso médio, no qual o B-M-H apresenta um desempenho melhor que o Wu-Manber. A disparidade de tempo do Wu-Manber pode também estar ligada a aspectos de implementação, dado que o sistema agrep, (baseado no mesmo algoritmo) possui melhor desempenho que o B-M-H.
Comparações entre: Wu-Manber - B-M-H - agrep
Em todos os experimentos realizados o sistema agrep foi mais eficiente
que os demais. Observando os experimentos verificamos que o sistema agrep é em
média:
- 73.04 vezes mais rápido que o Wu-ManberConsiderando que o sistema agrep é baseado no algoritmo Wu-Manber, esta diferença grande de desempenho pode ser atribuida a implmentação eficiente do agrep. O comportamento da busca permitindo erros já é menos discrepante como veremos a seguir.
- 7.65 vezes mais rápido que o B-M-H
Verificamos então que a busca utilizando o agrep é mais eficiente em todos os
teste realizados. De acordo com os experimento, temos que o agrep é em média:
Tam. texto(Mbytes)
2c| 1 ERRO
2c| 2 ERROS
Wu-Manber
agrep
Wu-Manber
agrep
2
7.02
0.18
10.28
0.85
10
17.83
0.44
24.64
1.77
20
34.49
0.83
49.84
3.37
100
184.38
4.57
270.11
17.92
- 40.05 vezes mais rápido que o Wu-Manber para 1 erroNota-se uma diminuição da diferença entre os desmpenhos com o aumento do número de erros. Para verficar este aspecto, foram realizado os experimentos VI e VII com 3, 5 e 8 erros. Do experimento VI, verificamos as seguintes relações:
- 13.96 vezes mais rápido que o Wu-Manber para 2 erros.
- com 3 erros: o agrep é 20.89 vezes mais rápido que o Wu-ManberPor último, verifamos através do experimento VII que o agrep e o sistema implementado se equiparam na busca por um padrão de tamanho maior (United States of America) e com um número de erros grande (8):
- com 5 erros: o agrep é 7.83 vezes mais rápido que o Wu-Manber
- com 8 erros: o agrep é 6.88 vezes mais rápido que o Wu-Manber
- com 3 erros: o agrep é 5.49 vezes mais rápido que o Wu-ManberNota-se também que na busca por padrões com 5 ocorre um ponto invariante relação de desempenho entre o agrep e o Wu-Manber, seja aumentando o tamanho do padrão ou não. Deve-se observar também que embora o Sistema implementado ``melhore'' seu desempenho para um número maior de erros om relação ao sistema agrep, isso não é muito significativo pois buscas com número grande de erros não se aplicam em muitos casos.
- com 5 erros: o agrep é 17.85 vezes mais rápido que o Wu-Manber
- com 8 erros: o agrep é 1.39 vezes mais rápido que o Wu-Manber
Pa a busca exata temos o os seguintes padrões de comportamento para os
algoritimos B-M-H e Wu-Manber:
Plotando-se o gráfico da tabela acima e adicionando uma linha de
tendência para as relações entre o tamanho do texto e os algoritmos obtivemos
as seguintes equações:
Texto em Mbytes (T)
B-M-H (B)
Wu-Manber (W)
2
0.36
3.76
10
1.28
9.43
20
2.46
18.67
100
13.81
99.65
W = 0.9939T e B = 0.137T.Com base nessas equações, estimamos os valores de tempo de busca para textos com tamanhos de 1 Gbyte, e 100 gygabytes por exemplo, basta aplicar as equações. Para este valores teremos:
Texto em Gbytes (T)
B-M-H (B)
Wu-Manber (W)
1
137.0
993.9
100
13700
99390
A estimativa de busca do Wu-manber com 1 dois erros também foi obtida através
da curva de tendência dos gráficos com base na tabela tempos abaixo:
Foram obtidas as seguintes equações:
Texto em Mbytes (T)
1 erro (B1)
2 erros (B2)
2
7.02
10.28
10
17.3
24.64
20
34.49
49.84
100
184.38
270.11
B1 = 1.8388T e B2 = 2.6918TPara os arquivos acima apresentados teremos a seguinte estimativa de tempo em segundos:
Texto em Gbytes (T)
1 erro
2 erros
1
1838.8
2691.8
100
183880
269180
No que se refere ao desempenho a implementação do algoritmo Wu-Manber precisa
ser revista, procurando detectar o gargalo que está tornando muito fraco o
desempenho do mesmo com relação ao sistema agrep.
No que se refere a sua aplicabilidade, caso de deseja realizar buscas sobre
grandes volumes de dados, torna-se necessário rever o projeto do sistema e
buscar alternativas mais eficientes tais como o uso de arquivos invertidos.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 trab3.tex.
The translation was initiated by Mateus Conrad Barcellos da Costa on 9/26/2002