Projeto para MAC324 - VIP

MAC324 - Estruturas de Dados para Engenharia

Poli/Elétrica - 1o. Semestre de 1999

Observações importantes!

Veja nesta página observações importantes sobre o projeto. A observação mais importante é a seguinte:

Você pode entregar uma versão preliminar de vip1, que usa árvores de busca binária sem balanceamento para implementar a tabela de símbolos. O prazo de entrega é o estabelecido incialmente para a primeira fase do projeto.
Se você optar por fazer isto, você pode entregar a versão definitiva de seu vip1 até as 15:00 do dia 24 de maio de 1999 [Novo prazo: 15:00 de 7/6/99]. Esta versão definitiva deve usar árvores com balanceamento. Nada além da implementação da tabela de símbolos deve mudar de uma versão para outra. Isto será verificado pelo monitor!!!
Aqueles que optarem por entregar duas versões do vip1 (que eu recomendo), terão a oportunidade de entregar um relatório comparando o desempenho de suas duas versões até as 15:00 do dia 14/6/99. Um relatório bem feito valerá um ponto extra na nota final do projeto.

Introdução

Este projeto é um exercício sobre manipulação de volumes consideráveis de dados, e cobre dois dos tópicos mais importantes desta disciplina: árvores balanceadas e tabelas de espalhamento (hashing). Ele consiste de duas partes: (a) um verificador ortográfico simples e (b) um indexador das palavras de um texto. Daí o nome do projeto: VIP - Verificador e Indexador de Palavras!

Voce deve escrever dois programas, digamos vip1 e vip2.

Parte 1. O verificador de palavras

Basicamente, o seu vip1 deve receber como entrada um arquivo texto texto.txt e um dicionário de palavras dicio.txt. Assumimos que o dicionário contém uma lista de palavras em ordem alfabética, uma por linha. O seu vip1 deve então descobrir que palavras de texto.txt não ocorrem no dicionário fornecido e deve devolvê-las, digamos no stdout. Além disto, ele deve criar um arquivo, digamos texto.idx, que indexa as palavras de texto.txt. O formato e função deste índice é discutido abaixo. Concentremo-nos aqui na parte de verificação das palavras.

Dicionários

Estão aqui alguns dicionários para testes.

br (2444k): uma lista de palavras do português brasileiro (atualizado em 14/4/99).
pt (4360k): uma lista de palavras do português português.
uniao (4827k): uma uniao de br e pt, sem as repetições, naturalmente (atualizado em 14/4/99).
pt_so_compostos (4300k): uma lista de palavras compostas do português português (inclui coisas como "mordê-lo-ei").
pt_compostos (8650k): uma lista de palavras do português português, inclusive as compostas.

Gerei o arquivo acima para o português brasileiro a partir do trabalho de Ricardo Ueda. Veja, em particular, a sua página sobre br.ispell. Note que uma condição que devemos respeitar é que qualquer coisa que produzirmos com a ajuda deste arquivo deve ficar livremente redistribuível (veja a licença GNU GPL).

Para gerar os arquivos para o português português, usei o trabalho de José João Almeida. Este trabalho também é distribuído de acordo com a licença GNU GPL.

Uma página muito interessante sobre recursos computacionacionais para o português é http://www.portugues.mct.pt/recursos.html.

Para entender a motivação e filosofia dos termos da licença GNU GPL, veja a página do Projeto GNU.

Alguns detalhes

Você terá de decidir sobre vários detalhes sobre o seu verificador. Aqui estão alguns deles:

O seu programa imporá limites no comprimento das linhas? (Ele não deve, se você quiser dez ponto zero!)
O seu programa imporá limites no número de linhas do texto de entrada? (Idem!)
O seu programa fará distinção entre letras maiusculas e minúsculas?
Qual vai ser a definição precisa de "palavra" para o seu programa?
O que o seu programa fará com palavras compostas como "quebra-cabeça"?

Um exemplo

Um programa que executa verificação de palavras no esquema descrito acima é o wordtest.w de Knuth [wordtest.dvi | wordtest.ps | wordtest.pdf | wordtest.w | wordtest.exe | wordtest.c (para que você possa criar seu próprio executável)]. Acredito que um entendimento completo das várias nuances deste programa está além do escopo desta disciplina (talvez não...), mas um estudo dele deve ser proveitoso. Este programa usa a estrutura de treaps para armazenar as palavra do texto de entrada. Treaps são árvores binárias que são uma mescla de árvores binárias de busca e heaps. O programa acima procura garantir que as árvores binárias que são construídas durante a sua execução sejam "balanceadas", através do uso de treaps, que são um pouco mais sofisticadas que árvores de busca binária.

Parte 2. A indexação de palavras

Uma tarefa muito comum, quando temos um volume grande de dados ou texto, é tentar encontrar todas as ocorrências de algum padrão ou palavra naquele conjunto de dados. Por exemplo, vocês devem conhecer os instrumentos de busca muito populares que existem hoje na rede, como o AltaVista. No AltaVista, você pode fornecer, por exemplo, "Josephus" e descobrir as páginas da teia que fazem referência a ele. Aliás, "Josephus Problem" descobre páginas interessantes sobre o nosso desafio do Josephus. Experimente!

A rapidez, precisão e a efetividade geral dos instrumentos de busca de informação na teia como o AltaVista são, simplesmente, fascinantes. Com eles, temos em nossas mãos como encontrar uma agulha em um palheiro.

Naturalmente, um esquema básico que está por trás é um esquema de "indexação" (além de muitos outros). Isto é, dado um padrão como "Josephus", estes esquemas facilitam a procura, em seu banco de dados, de tudo que é relevante. Naturalmente, quão efetivo é esta busca (se ela devolve informação interessante) depende da "qualidade" das informações que estão arquivadas neste banco de dados. O ponto para nós é que esquemas de busca em massas bem grandes de dados assim como a forma de armazenamento destes dados devem ser projetados com muito cuidado, para permitir busca eficiente.

A 2a. parte de seu projeto

Faremos nesta segunda parte do projeto um pequeno experimento. O programa vip1 que você vai escrever deve gerar um arquivo, digamos texto.idx que contém informação sobre onde ocorrem as palavras no arquivo de entrada texto.txt. Mais especificamente, (i) este arquivo deve conter uma linha para cada palavra distinta de texto.txt (incluindo aquelas palavras que não foram encontradas no dicionário), (ii) cada linha deve começar com a palavra à qual ela corresponde, (iii) esta palavra deve ser seguida de um inteiro que diz quantas vezes esta palavra ocorre no arquivo examinado e, finalmente, (iv) a linha deve conter uma lista de inteiros que dizem em que linhas da entrada ocorreu a palavra em questão. Por exemplo, se a palavra programming ocorre nas linhas 6, 14 (duas vezes), 47 e 198 de texto.txt, o seu arquivo texto.idx deve conter a linha

programming 5 6 14 14 47 198

É claro que o "5" acima é informação redundante, mas ela pode facilitar a depuração do seu programa e também permite responder rapidamente perguntas do tipo "Quais são as 20 palavras mais freqüentes em texto.txt?"

O seu vip2 deve ler este arquivo texto.idx e deve também receber como entrada linhas do tipo

+programming +pearls -course -order -buy -book

(Chamemos uma linha como acima de "query".) O seu vip2 deve então imprimir as linhas de texto.txt em que se encontram, obrigatoriamente, as palavras "programming" e "pearls", mas não se encontram as palavras "course", "order", "buy" e "book". Experimente fornecer a linha acima ao AltaVista! Este link faz isto para você. Veja a página de help do AltaVista para maiores detalhes de como funciona a sintaxe dos queries do AltaVista.

O seu programa vip2 deve receber um número arbitrário de queries, no stdin, e deve imprimir, no stdout, a saída correspondente a cada query, encabeçadas pelo query correspondente. Para conveniência do usuário, imprima uma linha em branco após o resultado de cada query (desta forma, a saída vem em blocos, um bloco por query). O usuário deve fornecer como parâmetro, na linha de comando, o nome do arquivo a ser examinado, digamos, sem extensão (seria "texto", no exemplo acima).

Isto é o básico do vip2. Ah! Naturalmente, para que o esquema acima funcione, o seu programa vip2 deve ter acesso ao arquivo texto.txt também.

Em tempo (adicionado em 19/5/99)

Uma operação útil (além de `+' e `-') é a operação `ou'. É útil para o usuário poder executar queries do tipo `linhas que contêm a palavra x ou a palavra y'. Para permitir consultas deste tipo, escreva seu vip2 de forma que ele aceite entradas do tipo

+programming |pearls -gems

Este querie deve selecionar as linhas que contêm a palavra "programming" e/ou "pearls" e, destas, eliminar aquelas que contêm a palavra "gems". (O operador `|' deve, por assim dizer, "adicionar" linhas àquelas já selecionadas.)

O ideal é que consultas booleanas fossem aceitas por seu vip2. Veja como isto funciona no Altavista. Note que já vimos em sala como processar expressões aritméticas (em notação in-fixa, pós-fixa, e pré-fixa), e portanto você já conhece a teoria para fazer análise sintática de expressões booleanas.

Conclusão. Você deve implementar o operador `|'. Você pode implementar consultas booleanas como no AltaVista; esta extensão da funcionalidade do vip2 valerá 1.0 ponto extra na nota de vip2.

Dados para testes

O seguinte diretório contém alguns arquivos nos quais testar os seus programas. Fontes interessantes são as páginas dos projetos Projecto Natura (de onde tirei a maioria dos arquivos do diretório dado acima) e do Projecto Vercial.

Estruturas de dados a serem usadas

As estruturas de dados fundamentais que estes programas deverão usar serão árvores balanceadas (vip1) e tabelas de hashing (vip2). Que sabor de árvores balanceadas e tabelas de hashing fica a seu critério! Naturalmente, a sua escolha dependerá do desenrolar desta disciplina no semestre. Note que muitas coisas podem já ser feitas e se você planejar um desenvolvimento modular de seu projeto, você já pode ter versões beta de seu vip1 e vip2 funcionando em breve.

Prazos de entrega

Veja observação importante sobre prazos de entrega acima!

Primeira parte: 15:00 do dia 10/5/99 (segunda-feira).
Segunda parte: 15:00 do dia 7/6/99 (segunda-feira).

Entregue o material mim, antes da aula, ou entregue na secretaria do Departamento de Ciência da Computação (MAC) do IME-USP, sala 256, bloco A do IME.

Observações

O projeto deve ser feito individualmente ou em duplas. A troca de informações entre grupos (por exemplo, através da lista de discussão) é fortemente encorajada, mas os programas entregues devem ser desenvolvidos separadamente; programas semelhantes receberão nota 0.
Faça um programa robusto, independente de ambiente. De qualquer forma, escreva claramente em que ambiente o seu programa foi desenvolvido e qual compilador foi usado. O compilador padrão para correção será o gcc.
Projetos atrasados podem ser aceitos, mas com redução de valor de 3 pontos por dia (ou parte de dia) de atraso. (Isto é, se atrasou por 28 horas, perde 6 pontos.)
Programas com erros de sintaxe receberão nota 0.
Endente o seu programa sistematicamente. Uma má apresentação do código resultará em nota menor.
Coloque comentários apropriados em seu programa. Programas sem documentação receberão nota baixa.
Coloque o cabeçalho usual em seu programa (como em MAC115), com nome, número USP, curso, data, nome do professor e identificação da parte (vip1 ou vip2). Novamente, não esqueça de indicar que compilador que você usou (djgpp, gcc, Turbo C, Borland C, etc).
Entregue em um envelope (preferencialmente de plástico transparente):
- Um disquete com o código do seu programa. Identifique o disquete com uma etiqueta.
- Uma listagem do programa.
- Saídas que você achar importantes (com as respectivas entradas, em forma eletrônica). A abrangência dos seus testes também será considerada na nota. Saber testar bem um programa é também muito importante.
- Guarde uma cópia de seu material até o fim do semestre.

Página principal de MAC324 (Poli - 1o. semestre de 1999).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Wed Jun 2 11:48:14 EST 1999