Terceiro Exercício-Programa - VIP

MAC122 - Princípios de Desenvolvimento de Algoritmos

BCC - 2o. Semestre de 1998

Introdução

Este terceiro exercício-programa é um exercício sobre manipulação de volumes consideráveis de dados. Ele consiste de duas partes: (a) um verificador ortográfico simples e (b) um indexador das palavras de um texto. Daí o nome do EP: Verificador e Indexador de Palavras! Voce deve escrever dois programas, digamos ep3a e ep3b.

O verificador de palavras

Basicamente falando, o seu ep3a 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 ep3a 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 (2856k): uma lista de palavras do português brasileiro.
pt (4360k): uma lista de palavras do português português.
uniao (5052k): uma uniao de br e pt, sem as repetições, naturalmente!
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]. Acredito que um entendimento completo das várias nuances deste programa está além do escopo desta disciplina, mas um estudo dele deve ser proveitoso. Por exemplo, 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.

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, "MAC122" como entrada e você obterá, rapidamente (se a rede não estiver sobrecarregada), o endereço (URL) de todas as páginas do mundo inteiro que tem a ver com "MAC122". A página da nossa disciplina é a segunda página que ele fornece na lista dele (pelo menos agora, quando escrevendo este texto). Experimente! Qual página você acha que ele apresenta no topo da lista dele? Se você ainda não conhece, vale a pena conferir!

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 "MAC122", 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 EP3

Faremos nesta segunda parte do EP um pequeno experimento. O programa ep3a 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 ter uma linha por palavra encontrada em texto.txt, (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 âncora ocorre nas linhas 6, 14, 47 e 198 de texto.txt, o seu arquivo texto.idx deve conter a linha

âncora 4 6 14 47 198

É claro que o "4" 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 ep3b deve ler este arquivo texto.idx e deve também receber como entrada linhas do tipo

+âncora +navio +terra +caminha -Guanabara

O seu ep3b deve então imprimir as linhas de texto.txt em que se encontram, obrigatoriamente, as palavras "âncora", "navio", "terra" e "caminha", mas não se encontra a palavra "Guanabara". (Experimente fornecer a linha acima ao AltaVista! Este link faz isto para você.)

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

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.

Prazo de entrega

Segunda-feira, 16 de novembro de 1998, até as 18:00. Entregue seu EP na secretaria do MAC, sala 256, bloco A, antes do término do expediente naquele dia!

Observações

O EP é estritamente individual. Exercícios semelhantes receberão nota 0.
Exercícios atrasados não serão aceitos.
Exercícios 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 MAC110), com nome, número USP, curso, data, nome do professor e identificação do EP (EP3). Não esqueça de indicar que compilador que você usou (Turbo C, Quick C, gcc, 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.
- As saídas correspondentes aos exemplos no enunciado (ainda a serem postos nesta página) e quaisquer outras 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.
Importante: entregue o seu material também por correio eletrônico para o nosso monitor Ricardo Bueno Cordeiro <rbc@linux.ime.usp.br>, com cópias para <yoshi@ime.usp.br> e <armando@ime.usp.br>. O ideal é que futuramente a entrega de disquetes não fosse mais necessária.

Página principal de MAC122 (BCC - 2o. semestre de 1998).

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

Last modified: Tue Oct 19 03:51:51 EDT 1999