MAC 324 Estruturas de Dados para Engenharia (projeto)

Este projeto foi elaborado pelo professor Yoshiharu Kohayakawa.

Observações importantes!

Veja nesta página observações importantes sobre o 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. Palavras Mais Freqüentes

Neste primeiro exercício-programa, você se familiarizará com a noção de tabela de símbolos. Nesta etapa, você não precisará usar implementações sofisticadas de tais tabelas; a idéia principal é você entender como podemos usar tais estruturas. A referência básica para este parte do projeto é o início do Capítulo~12 de Sedgewick (inclusive Seção 12.1).

Problema a ser resolvido

O programa que você escreverá neste exercício deve resolver o seguinte problema: a entrada de seu programa é formada por um inteiro n e um texto e a saída de seu programa deve ser a lista das n palavras mais freqüentes no texto, com suas respectivas freqüências (número de ocorrências na entrada).

Palavras

Uma palavra é uma seqüência maximal de letras. Você deve distinguir letras maiúsculas de minúsculas, de forma que Vitória e vitória devem ser consideradas palavras diferentes. As palavras que ocorrem um mesmo número de vezes devem ser listadas em ordem `alfabética'. Use a ordem alfabética induzida pela tabela ASCII, por exemplo, Zoroastro deve vir antes de alabastro. O seu programa deve parar após n palavras terem sido devolvidas, caso a entrada tenha pelo menos n palavras.

Execução

A entrada de seu programa deve vir do \texttt{stdin} e o seu programa deve receber o inteiro n na linha de comando. A saída deve ser enviada para o \texttt{stdout}. Por exemplo, executando o seu programa no texto do King James' Bible do Projeto Gutenberg, removendo o cabeçalho contendo informações sobre o Projeto Gutenberg, termos de distribuição, etc, obtemos algo como

meu_prompt > ep1 -n5 < entrada.txt
     62064 the
     38847 and
     34428 of
     13378 to
     12846 And

Esta saída diz que, por exemplo, a palavra mais freqüente é the, com 62064 ocorrências.

Estrutura geral do programa

Você deve estruturar o seu programa da seguinte forma.

Objetos das tabelas de símbolos

Os objetos a serem armazenados em sua tabela de símbolos devem ser do tipo Item, implementados em Item.c e manipulados através da interface Item.h.

Tabela de símbolos

Uma tabela de símbolos é uma estrutura de dados de Items com Chaves que permitem dois tipos de operações básicas: inserir um novo item e devolver um item que tem uma dada Chave.

Tabelas de símbolos são também chamadas de dicionários devido a anologia com o sistema que fornece o significado de palavras listando-as em ordem alfabética. Neste exemplo temo que a Chave é uma palavra e um Item, além da palavra, também contém o significado da palavra. Em computês, para este exemplo, um Item seria um objeto com a seguinte cara:

typedef char *Chave;
typedef char *Texto;
struct registro {
    Chave palavra; /* uma palavra da entrada, assumindo uma palavra por linha */
    Texto significado; /* numero de ocorrencias desta palavra */
};
typedef struct registro *Item;

A sua tabela de símbolos deve ser implementada em ST.c e o acesso a ela deve ser estritamente através da interface ST.h. Projete a interface ST.h de forma que ao alterar a implementação da tabela de símbolos, você não precisará alterar outras partes do programa. Possivelmente, você disponibilizará uma função de protótipo

  void ST_first_n(void (*visit)(Item), int n);

em ST.h, para enviar as n palavras mais freqüentes à saída, por exemplo, com a chamada

  ST_first_n(ITEMshow, n);

em seu programa principal. Procure implementar sua tabela de símbolos de forma que o seu programa possa manipular arquivos de tamanho `razoavelmente grandes'. Com o que vimos em sala até o momento, provavelmente não sabemos como escrever um programa que possa realmente processar um arquivo como o King James' Bible, que contém algo como 800.000 palavras.

Arquivos de teste

Uma boa fonte de arquivos para testar o seu programa é o Projeto Gutenberg.

Parte 2. Palavras Mais Freqüentes

Neste segundo exercício-programa, você deverá implementar uma tabela de símbolos por meio de árvores binárias de busca. A referência básica para este parte do projeto é o início do Capítulo~12 de Sedgewick (inclusive Seção 12.1).

Problema a ser resolvido

O programa que você escreverá neste exercício deve resolver o mesmo problema do exercício passado, ou seja: a entrada de seu programa é formada por um inteiro n e um texto e a saída de seu programa deve ser a lista das n palavras mais freqüentes no texto, com suas respectivas freqüências (número de ocorrências na entrada).

Árvores binárias de busca

O professor Yoshiharu Kohayakawa colocou várias implementações de tabelas de símbolos, no endereço

http://www.ime.usp.br/~yoshi/2001i/mac323/exx/STs/

Para implementar a sua tabela de símbolos você deverá empregar uma árvore binária de busca (ABB). Você pode usar no seu programa uma adaptação de alguma das seguintes implementações, contidas na página acima:

  BST - ABBs padrões
  BST_noN - ABBs padrões, sem campos N nos nós
  rBST - ABBs aleatórias
  rBSTb - ABBs aleatórias, com um gerador de números aleatórios bem simples

Faça uma pequena análise empirica de desempenho comparando o programa feito na Parte 1 e o programa feito agora. Entregue um pequeno relatório (no máximo uma página) com os resultados e conclusões.

Execução

Procure executar os seus programas com arquivos grandes, por exemplo, execute os seus programas tendo como entrada o texto do King James' Bible do Projeto Gutenberg.

Parte 3. Palavras Mais Freqüentes (Epílogo)

Neste terceira parte do projeto, você deverá implementar uma tabela de símbolos por meio de uma árvores AVL. A referência básica para esta parte do projeto são as notas de aula.

Problema a ser resolvido

O programa que você escreverá desta vez deve resolver o mesmo problema que as partes anterior, ou seja: a entrada de seu programa é formada por um inteiro n e um texto e a saída de seu programa deve ser a lista das n palavras mais freqüentes no texto, com suas respectivas freqüências (número de ocorrências na entrada).

Árvores AVL

Para implementar a sua tabela de símbolos você deverá empregar uma árvore AVL. Faça uma pequena análise empirica de desempenho comparando o programa feito nas Partes 1 e 2 e o programa feito agora. Entregue um pequeno relatório (no máximo uma página) com os resultados e conclusões.

Execução

Procure executar os seus programas com arquivos grandes, por exemplo, execute os seus programas tendo como entrada o texto do King James' Bible do Projeto Gutenberg.

Prazos de entrega

Primeira parte: 14/5/2001 (segunda-feira).
Primeira parte: 30/5/2001 (quarta-feira).
Terceira parte: 18/6/2001 (segunda-feira).

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.
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.)
Endente o seu programa sistematicamente.
Coloque comentários apropriados em seu programa.
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. Novamente, não esqueça de indicar que compilador que você usou (djgpp, gcc, Turbo C, Borland C, etc).

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

MAC 324's Home Page.

Last modified: Wed Jun 6 14:41:15 BRST 2001