| Home page da disciplina MAC 324 | Mapa do sítio da disciplina |
Veja as recomendações dos monitores aqui: Especificações para a entrega do projeto (Última alteração em 09jun98).
O objetivo do projeto é montar um índice remissivo do Primeiro Livro do Velho Testamento, Genesis. A estrutura de dados a ser usada será uma B-árvore, que veremos na disciplina oportunamente. O projeto será elaborado em grupos de dois ou três alunos, em várias etapas.
Nesta segunda etapa o trabalho deve ser feito pelos mesmos grupos que foram formados por ocasião da entrega da primeira etapa.
A saída da primeira etapa servirá de entrada para esta segunda etapa.
O objetivo final é fazer um programa que recebe uma palavra e informa, em ordem crescente, todos os artigos de Genesis onde esta palavra ocorre. Em outras palavras, faremos um índice remissivo completo de Genesis.
Para obter este índice deve se montar uma B-árvore a partir das linhas produzidas na primeira etapa. As entradas na B-árvore devem ser guardadas em ordem alfabética crescente das palavras indexadas, para cada palavra indexada, os artigos em que ela comparece devem estar disponíveis em ordem crescente. Há muitas maneiras diferentes de conseguir este efeito. Em geral, quanto mais eficiente é um método, mais esforço de programação vai exigir a sua implementação. As exceções a esta regra são as pérolas da computação. A escolha do método a ser usado fica a critério de cada grupo. O método usado e os detalhes da sua implementação devem ser cuidadosamente explicados em documento próprio, à parte do programa.
A escolha dos parâmetros da B-árvore e do formato das suas páginas também deve ser justificada e explicada no documento aludido.
A implementação da B-árvore deve ser feita usando-se os métodos de entrada/saída do pacote java.io.* no subpacote RandomAccess. Vocês vão montar um arquivo de acesso aleatório contendo as páginas da B-árvore que devem ter tamanho pré-fixado. Notem que o esquema de endereçamento das páginas fica por conta da sua implementação, isto é não se podem usar as referências do Java, já que o acesso, dentro do arquivo de páginas, deve ser feito pelo próprio programa.
O diretório de programas de demonstração de manipulação de arquivos de acesso aleatório, gentilmente elaborado por Caetano Jimenez Carezzato, pode ser útil para um melhor entendimento de como um arquivo de acesso aletório é usado em Java. Maiores informações podem ser obtidas no Capítulo 12 do livro de Arnold e Gosling.
Em princípio a sua programação deve incluir um método de busca e inserção na B-árvore. Este método será usado tanto na montagem da estrutura principal, como na busca das informações sobre as ocorrências de uma palavra dada. Vocês podem se basear nas páginas do livro de Wirth que foram distribuídas e que contêm uma rotina completa de busca e inserção em B-árvores, escrita em Pascal. Note que não há necessidade de implementação de um método de remoção da B-árvore já que a nossa só vai crescer. Isto simplifica a programação.
Como já foi dito, o programa deve ser acompanhado de um documento, preferencialmente no formato html, para poder ser lido num browser, explicando os métodos usados na implementação e justificando as suas escolhas.
Esforços de enriquecer a funcionalidade básica deste projeto são fortemente encorajados e serão recompensados ou através da nota ou através da exposição dos melhores trabalhos recebidos. Estes esforços incluem a feitura de uma interface gráfica para a utilização do índice dentro de um browser, por exemplo. Outra sugestão é estender o projeto e implementar a remoção de B-árvore também, fazendo uma extensão do projeto para fazer a demonstração do método de remoção. Outra possibilidade ainda é fazer um programa que monta a B-árvore a partir de parâmetros especificados (como a ordem da árvore, por exemplo) e fazer um estudo de como varia a eficiência do programa quando se variam os parâmetros. Todos os enriquecimentos devem ser explicados no documento que acompanhará o projeto.
Boa sorte e mais uma vez, não deixe o trabalho para a última hora!
O trabalho será feito em grupos de dois ou três alunos. Os grupos devem ser registrados na entrega da primeira etapa e não poderão ser alterados após esta data.
O objetivo da primeira etapa é produzir uma lista das ocorrências de palavras no texto na forma:
artigo palavra-em-minúsculas-sem-sinais-de-pontuação
O texto de Genesis, em inglês, pode ser encontrado aqui: Genesis em ASCII. Este texto provêm do Projeto Gutenberg, um site que merece ser visitado. O texto em questão pode ser encontrado na página: The Project Gutenberg Etext of The King James Bible.
Assim, as primeiras linhas do arquivo a ser produzido serão:
1:1 in 1:1 the 1:1 beginning 1:1 god 1:1 created 1:1 the 1:1 heaven 1:1 and 1:1 the 1:1 earth 1:2 and 1:2 the 1:2 earth 1:2 was 1:2 without 1:2 form 1:2 and 1:2 void 1:2 and 1:2 darkness 1:2 was 1:2 upon 1:2 the 1:2 face 1:2 of 1:2 the 1:2 deep 1:2 and 1:2 the 1:2 spirit 1:2 of 1:2 god 1:2 moved 1:2 upon 1:2 the 1:2 face 1:2 of 1:2 the 1:2 waters ...
Oportunamente serão dadas instruções sobre a forma da entrega do exercício que deverá ser feita em Java padrão, processável sem erros em JDK, e através de um ou mais arquivos enviados pela rede numa interface a ser especificada.
Recomendamos a leitura atenta dos capítulos 8 e 12 do livro de Arnold e Gosling para informações sobre o manuseio de String's e sobre o sistema de Entrada/Saída do Java.
Para orientar o seu trabalho, os monitores da disciplina gentilmente prepararam três programas, cat, tr e wc que podem ser encontradas nesta página: fonte de utilitários semelhantes ao cat, tr e wc do Unix. A idéia de disponibilizar estes programas é mostrar paradigmas de Entrada/Saída de arquivos texto que Vocês possam usar como exemplos. Estes programas foram inspirados nos uti;itários (muito mais flexíveis) do Unix. Sugere-se pesquisar as páginas man destes programas para se informar da funcionalidade destes programas.
A saída do programa deve estar num arquivo texto ASCII.
Um exercício opcional extremamente interessante é usar utilitários padrão do Unix, como cat, tr, sort, uniq, perl, etc. para produzir um programa de algumas linhas equivalente ao programa Java que Vocês devem escrever.
Existe um produto comercial que eventualmente pode servir de fonte de inspiração para quem queira fazer um trabalho mais sofisticado.
Boa sorte, e não deixe o trabalho para a última hora!
| Home page da disciplina MAC 324 | Mapa do sítio da disciplina |
e-mail:
Imre Simon <is@ime.usp.br>