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

Algoritmos e Estruturas de Dados III

2$^o$ semestre de 2008

Trabalho prático 6

Data de entrega: 10 de dezembro de 2008

Este trabalho tem por objetivo projetar e avaliar uma extensão do algoritmo Boyer-Moore como base para uma máquina de busca. Dada uma consulta a ser respondida, o seu algoritmo deve retornar os conjuntos de ocorrências das palavras que não estejam mais que X caracteres distantes entre si. Uma solução ingênua é executar o algoritmo várias vezes, registrar as ocorrências para cada palavra da consulta e verificar essas ocorrências de forma a verificar se elas estão próximas o suficiente. A sua estratégia deve ser independente do tamanho da consulta, ou seja, será realizado apenas uma passada para cada consulta.

Pede-se:

1. Descreva como você vai estender o algoritmo.

2. Discuta a correção e complexidade obtidos.

3. Avalie experimentalmente o seu algoritmo, verificando o número de comparações realizadas para cada consulta. Utilize o seguinte arquivo como base para busca. Varie o número de termos na consulta e o limiar de distância a ser utilizado. Derive experimentalmente a complexidade do seu algoritmo como função do tamanho do texto, do tamanho dos padrões e do número de padrões.

4. Apresente a documentação da proposta e dos resultados (veja aqui maiores detalhes sobre a entrega de trabalhos práticos). O seu trabalho deve ser submetido ao Minha.ufmg.