Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS

Última alteração: 25 de Setembro de 2002

Professor: Nivio Ziviani
Monitora: Claudine Santos Badue
2$^{\underline{o}}$ Trabalho Prático - 30/07/02 - 10 pontos
Data de Entrega: 16/08/02
Penalização por Atraso: 1 ponto até 20/08/02 mais 1 ponto por dia a seguir

Casamento de Padrão com Busca Aproximada

O objetivo deste trabalho é projetar e implementar um sistema de programas para recuperar ocorrências de padrões em arquivos constituídos de documentos, utilizando algoritmos lineares de busca sequencial.

Busca

  O sistema de programas recebe do usuário uma cadeia de caracteres, se a busca é exata (k=0) ou aproximada (0 < k < m), e imprime todas as ocorrências do padrão no texto. Nesta parte do trabalho você deverá utilizar os seguintes algoritmos:

• Algoritmo de Boyer-Moore-Horspool (BMH) para casamento exato de padrões
• Algoritmo proposto por Wu e Manber (WM) de 1992 para casamento aproximado de padrões, utilizando o código implementado por Márcio Drumond Araújo, apresentado abaixo.

Como fazer

Utilize os arquivos de documentos da coleção TREC disponível em /export/texto2/wsj, com as seguintes características:

Coleção Tamanho (Mb)

wsj88 109

wsj88_10 10

wsj88_20 20

wsj89 2.8

Um exemplo de registro deste arquivo é:

<DOC>
<DOCNO> WSJ890802-0125 </DOCNO>
<DD> = 890802 </DD>
<AN> 890802-0125. </AN>
<HL> Inside Track:
@  NCNB Director Sold Big Holding in July
@  Worth $7.4 Million More 4 Weeks Later
@  ----
@  By Alexandra Peers and John R. Dorfman
@  Staff Reporters of The Wall Street Journal </HL>
<DD> 08/02/89 </DD>
<SO> WALL STREET JOURNAL (J) </SO>
<CO> NCB BPCO TRN EGGS LABOR </CO>
<IN> STOCK MARKET, OFFERINGS (STK)
SECURITIES INDUSTRY (SCR) </IN>
<TEXT>
   Even insiders make mistakes. 
Sometimes, big, fat, $7 million-dollar mistakes. ...

</TEXT>
</DOC>

Observações:

1.

São consideradas palavras as sequências compostas por caracteres pertencentes ao conjunto a, ..., z, A, ..., Z.

2.

Utilize o algoritmo WM para realizar buscas exatas ou aproximadas sobre o vocabulário e sobre os documentos.

3.

Crie uma interface de uso do seu sistema parecida com a do sistema agrep disponível na rede do DCC.

4.

A saída do programa deve mostrar a linha do documento que contêm o padrão.

5.

Para testar seu programa você deve realizar as consultas listadas no arquivo /export/texto2/wsj_consultas e mostrar o resultado obtido.

O que deve ser entregue:

• Explicação detalhada dos algoritmos e estruturas de dados utilizados para resolver o problema. As explicações devem ser dadas através de descricões em alto nível. (1 ponto)
• Análise de complexidade dos principais algoritmos implementados. (1 ponto)
• Listagem dos programas implementados. O código deve ser bem comentado e organizado. (2 pontos)
• Resultados de experimentos para avaliar empiricamente o desempenho dos algoritmos. (6 pontos)
  • Apresente o que falta nesta especificação para seu sistema se tornar útil e competitivo na vida real. Apresente estimativas para o desempenho dos algoritmos quando os mesmos estiverem lidando com arquivos maiores (algumas centenas de megabytes). (1 ponto)
  • Fazer um estudo comparativo de desempenho entre os algoritmos BMH, WM e o sistema grep disponível na rede do DCC, todos realizando busca exata. (1 ponto)
  • Fazer um estudo comparativo de desempenho entre os algoritmos BMH, WM e o sistema agrep disponível na rede do DCC, agora realizando busca exata e aproximada. (2 pontos)

Referências:

Wu, S. and Manber, U. (1992) Fast Text Searching Allowing Errors, Communications of the ACM, pp. 83-91, v. 35(10).

Andrew Hume, Daniel Sunday: Fast String Searching. Software - Practice and Experience 21(11): 1221-1248 (1991).

Daniel Sunday: A Very Fast Substring Search Algorithm. CACM 33(8): 132-142 (1990).

Código:

A seguir é apresentado um código exemplo. Ele faz busca sequencial em textos.

==============================================================================
/*
Autor    : Marcio Drumond Araujo - 1997
Descricao: Implementacao do algoritmo de Wu e Manber desenvolvido em 1992
           considerando a busca somente de palavras inteiras
*/

/* /// I N C L U D E S ///////////////////////////////////////////////////// */

#include <stdio.h>

/* /// D E F I N E S /////////////////////////////////////////////////////// */

#define TRUE                     1
#define FALSE                    0
#define ALPHABET_SIZE          256
#define MAX_LINE_SIZE          512
#define MAX_MODIFIED_LINE_SIZE 512
#define MAX_PATTERN_SIZE        29 /* considerando uma palavra de 32 bits */
#define MAX_NUMBER_OF_ERRORS    28 /* considerando uma palavra de 32 bits */
#define MAX_FILE_NAME_SIZE     256

/* /// G L O B A L   V A R I A B L E S ///////////////////////////////////// */

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 */

/* /// F U N C T I O N S /////////////////////////////////////////////////// */

/* Funcao    : preproc
   Objetivos : preprocessar o padrao, montando as mascaras de inicializacao, 
               dos caracteres do alfabeto e a de busca exata obrigatoria
   Parametros: o padrao e o numero de erros
   Saida     : nenhuma */
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
   Objetivos : verifica se um padrao ocorre ou nao numa sequencia, com um
               numero de erros menor ou igual a k
   Parametros: o padrao, a sequencia e o numero de erros
   Saida     : verdadeiro se o padrao ocorre na sequencia ou falso, 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;
}

/* /// M A I N   F U N C T I O N /////////////////////////////////////////// */

int main(int argc, char *argv[]) {
  FILE     *t; /* text file id */
  char     line[MAX_LINE_SIZE],          /* linha do arquivo texto */
           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 */

  if (argc != 4) { /* testa se o numero de argumentos esta correto */
    fprintf(stderr, "Numero incorreto de parametros\n");
    exit(1);
  }
  k = atoi(argv[1]);
  if (k > MAX_NUMBER_OF_ERRORS) { /* valida o numero de erros da busca */
    fprintf(stderr, "Numero de erros maior que o maximo permitido\n");
    exit(1);
  }
  strcpy(p, " "); /* p recebe um espaco como primeiro caractere */
  strcat(p, argv[2]); /* p recebe o padrao propriamente dito */
  strcat(p, " "); /* p recebe um espaco como ultimo caractere */
  strcpy(filename, argv[3]);
  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");
    exit(1);
  }
  if (k >= m) {
    fprintf(stderr, "Numero de erros nao e menor que o tamanho do padrao\n");
    exit(1);
  }
  
  preproc(p, k);

  t = fopen(filename, "r");
  while(fgets(line, MAX_LINE_SIZE, t)) { /* enquanto houver linhas no arquivo */
    line[strlen(line) - 1] = '\0';
    if (Wu_Manber(p, line, k)) {
      printf("%s: %s\n", filename, line);
    }
  }
  close(t);
}