\subsection*{Casamento de Padr\~ao com Busca Aproximada}

O objetivo deste trabalho \'{e} projetar e implementar um sistema de 
programas para recuperar ocorr\^encias de padr\~oes em 
arquivos constitu\'{\i}dos de documentos, 
utilizando algoritmos lineares de busca sequencial.

%\vspace{-0.2cm}
\subsubsection*{Busca}
\label{Busca}
%\vspace{-0.2cm}

O sistema de programas recebe do usu\'ario uma cadeia de caracteres,
se a busca \'e exata ($k=0$) ou aproximada ($0 < k < m$),
e imprime todas as ocorr\^encias do padr\~ao no texto.
Nesta parte do trabalho voc\^e dever\'a utilizar os seguintes algoritmos:
\begin{itemize}
\item Algoritmo de Boyer-Moore-Horspool (BMH) para casamento exato de padr\~oes
\item Algoritmo Shift-And para casamento exato de padr\~oes
\item Algoritmo Shift-And para casamento aproximado de padr\~oes
% e que pode ser obtido em
%{\tt http://www.dcc.ufmg.br/$\sim$nivio/pa00/tp3}.
\end{itemize}

\subsubsection*{2 Pontos extras}
\begin{itemize}
\item
Apresente a implementa\c{c}\~ao em Pascal dos algoritmos Shift-And
para (i) casamento exato e (ii) casamento aproximado.
Procure realizar as opera\~oes  {\em or}, {\em and} e deslocamento
($>>$) da maneira mais eficiente poss\'{\i}vel, mas sem perder a
eleg\^ancia e a clareza.
\item Compare o desempenho das implementa\c{c}\~oes em Pascal e C. 
\end{itemize}

\subsubsection*{Como fazer}

Utilize os arquivos de documentos da cole\c{c}\~ao TREC dispon\'{\i}vel
em {\tt /export/texto2/wsj}, com as seguintes caracter\'{\i}sticas:\\

\begin{tabular}{|l|c|} \hline
Cole\c{c}\~ao & Tamanho (Mb) \\
wsj88    & 109 \\
wsj88\_10 & 10 \\
wsj88\_20 & 20 \\
wsj89    & 2.8 \\
\hline
\end{tabular}

\vspace{0.4cm}
\noindent
Um exemplo de registro deste arquivo \'e:

%\vspace{-0.5cm}

{\small
\begin{verbatim}

<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>
\end{verbatim}
}

\noindent
{\bf Observa\c{c}\~oes:}

\begin {enumerate}

\item
Crie uma interface de uso do seu sistema parecida com a do sistema
{\em agrep} dispon\'{\i}vel na rede do DCC.

\item   A sa\'{\i}da do programa deve mostrar 
a linha do documento que cont\^em o padr\~ao.

\item 
Para testar seu programa voc\^e deve realizar as consultas 
listadas no arquivo {\tt /export/texto2/wsj\_consultas}
e mostrar o resultado obtido.

\item O sistema {\em agrep} dispon\'{\i}vel na rede do DCC pode
ser um bom par\^ametro para comparar o desempenho da sua implementa\c{c}\~ao
em rela\c{c}\~ao a uma implementa\c{c}\~ao considerada r\'apida.

\item A principal refer\^encia \'e o Cap\'{\i}tulo 7 indicado acima.
As refer\^encias ao final do texto s\~ao apenas complementares, e o
TP3 poder\'a ser feito independente delas.

\end {enumerate}

\noindent
{\bf O que deve ser entregue:}

\begin {itemize}

\item Explica\c{c}\~ao suscinta dos algoritmos e estruturas de dados
utilizados para resolver o problema. (2 pontos) 

%\item An\'alise de complexidade dos principais algoritmos implementados. 
%(1 ponto) 

\item Listagem dos programas implementados. O c\'odigo deve ser bem comentado e organizado. (4 pontos)

\item Resultados de experimentos para avaliar empiricamente
 o desempenho dos algoritmos, usando tempo de rel\'ogio.
(4 pontos)

\end{itemize}

\noindent
{\bf Refer\^encias:}

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

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

\noindent
Baeza-Yates, R. e R\'egnier, M. (1992) ``Average Running Time of the Boyer-Moore-Horspool Algorithm'',
{\em Theoretical Computer Science 92}(1), 19--31.

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

%\vspace{0.3cm}
%\noindent
%{\bf C\'odigo:} 
%
%A seguir \'e apresentado um c\'odigo exemplo. Ele faz busca sequencial
%em textos.
%
%{\small
%\begin{verbatim}
%
%==============================================================================
%/*
%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);
%}  
%
%\end{verbatim} 
%}

\end {document}