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

Última alteração: July 12, 2004

Professor: Nivio Ziviani
Monitor: Fabiano C. Botelho
3 $^{\underline{o}}$ Trabalho Prático - 11/05/04 - 10 pontos
Data de Entrega: 28/05/04
Penalização por Atrazo: 1 ponto até 04/06/04 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 é realizar experimentos em um conjunto 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 de Boyer-Moore-Horspool-Sunday (BMHS) 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 de um algoritmo para casamento aproximado usando programação dinâmica.
• Compare o desempenho da sua implementação com o Shift-And para casamento aproximado de padrões. A principal referência é Navarro,, G. e Raffinot, M. Flexible Pattern Matching in Strigs, Cambridge University Press, 2002 [NR02].

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. Utilize as consultas listadas no arquivo /export/texto2/wsj/wsj89_consultas para testar seu programa você deve realizar 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 dos programas em relação a uma implementação considerada rápida.

5. A principal referência é o Capítulo 7 do livro Ziviani, N. Projeto de Algoritmos, Thomson, 2004 [Z04]. As referências ao final do texto são apenas complementares, e o TP3 poderá ser feito independente delas.

O que deve ser entregue:

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

• Análise de complexidade dos principais algoritmos implementados. (2 ponto)

• Resultados de experimentos para avaliar empiricamente o desempenho dos algoritmos. Interprete os resultados (6 pontos):
  • Medindo o número de comparações entre caracteres, para os casos BMH e BMHS.
  • Usando tempo de relógio.

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).

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 pa04tp3

The translation was initiated by Nivio Ziviani on 2004-07-12