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: 26. Junho 2003

Capítulo 7: Processamento de Cadeias de caracteres
Enunciado TP3 em Latex

Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani
Monitor: Bruno Pôssas
3 $^{\underline{o}}$ Trabalho Prático - 26/06/03 - 10 pontos
Data de Entrega: 11/07/03
Penalização por Atrazo: 1 ponto até 16/07/03 mais 1 ponto por dia útil a seguir
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).

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 Shift-And para casamento exato de padrões
• Algoritmo Shift-And para casamento aproximado de padrões

2 Pontos extras

• Apresente a implementação em Pascal dos algoritmos Shift-And para (i) casamento exato e (ii) casamento aproximado. Procure realizar as operaões or, and e deslocamento ($»$) da maneira mais eficiente possível, mas sem perder a elegância e a clareza.
• Compare o desempenho das implementações em Pascal e C.

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. Crie uma interface de uso do seu sistema parecida com a do sistema agrep disponível na rede do DCC.

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

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

4. O sistema agrep disponível na rede do DCC pode ser um bom parâmetro para comparar o desempenho da sua implementação em relação a uma implementação considerada rápida.

5. A principal referência é o Capítulo 7 indicado acima. As referências ao final do texto são apenas complementares, e o TP3 poderá ser feito independente delas.

O que deve ser entregue:

• Explicação suscinta dos algoritmos e estruturas de dados utilizados para resolver o problema. (2 pontos)

• Listagem dos programas implementados. O código deve ser bem comentado e organizado. (4 pontos)

• Resultados de experimentos para avaliar empiricamente o desempenho dos algoritmos, usando tempo de relógio. (4 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).

Baeza-Yates, R. e Régnier, M.: Average Running Time of the Boyer-Moore-Horspool Algorithm, Theoretical Computer Science 92(1), 1992, 19-31.

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