Desafio PET
Estrutura de Dados I
PET - Engenharia de Computação
Universidade Federal do Espı́rito Santo
http://www.inf.ufes.br/~pet
[email protected]
Monitores:
Arthur Fioresi Altoé
[email protected]
Marcos Vinicius G. Cypriano
[email protected]
Professores:
Lucas de Paula Veronese
Patrı́cia Dockhorn Costa
1
Objetivo
Alocação dinâmica, ordenação, listas, pilhas, árvores, hash, dentre outros,
são itens importantes apresentados em estrutura de dados I. Esse desafio
visa testar o aprendizado adquirido na disciplina e mostrar alguma aplicação
interessante para esses itens.
Descrição
Para o funcionamento de uma máquina de busca, como o Google, a base é a
construção de ı́ndice invertido para uma coleção de documentos.
Para isso, dada uma coleção de documentos um ı́ndice invertido é uma estrutura contendo uma entrada para cada palavra (termo) que ocorre em pelo
menos um documento da coleção. Cada entrada associa à palavra pares de
informações que identificam o número de ocorrência dessa palavra e em qual
documento ocorre.
occurrence number; doc id;
Exemplo com coleção de 2 arquivos
Listing 1: arquivo1.txt
O doce perguntou para o doce :
Qual e o doce mais doce que o doce de b a t a t a doce ?
Listing 2: arquivo2.txt
O doce respondeu para o doce que o doce mais doce e o
doce do doce de b a t a t a doce .
Assumindo identificadores 1 e 2 para arquivo1.txt e arquivo2.txt, respectivamente, o ı́ndice invertido fica:
Listing 3: Índice invertido para a coleção dos arquivos 1 e 2
b a t a t a −> ( 1 , 1 ) ( 1 , 2 )
de −> ( 1 , 1 ) ( 1 , 2 )
do −> ( 1 , 2 )
doce −> ( 6 , 1 ) ( 7 , 2 )
e −> ( 1 , 1 ) ( 1 , 2 )
mais −> ( 1 , 1 ) ( 1 , 2 )
2
o −> ( 4 , 1 ) ( 4 , 2 )
para −> ( 1 , 1 ) ( 1 , 2 )
perguntou −> ( 1 , 1 )
q u a l −> ( 1 , 1 )
que −> ( 1 , 1 ) ( 1 , 2 )
respondeu −> ( 1 , 2 )
Perceba que junto a cada palavra há uma lista de pares de números,
que representam o número de ocorrências de uma palavra em um documento e o identificador do documento em que ocorre essa palavra (occurrence number,doc id), respectivamente.
Observe também que as palavras estão organizadas por ordem alfabética e a
lista de pares de números pelos identificadores.
Para o objetivo do desafio deve-se implementar um sistema para produzir
um ı́ndice invertido.
Importante:
• O sistema deve ser capaz de atribuir um identificador único para os
documentos a partir do nome dos arquivos de entrada;
• Os textos não terão acentuação e os sinais de pontuação devem ser
ignorados. Palavras são letras;
• Palavras com letras maiúsculas e minúsculas não devem ser diferenciadas;
• Nenhuma palavra terá mais do que 20 caracteres.
• Deve-se utilizar tabela hash bem dimensionada com lista encadeada.
• Esse sistema deve ser executado a partir de entrada e saı́da padrão de
arquivos. ./executable <input >output
Arquivo de entrada
N
arquivo1
arquivo22
arquivo30
...
3
No exemplo acima N é o número de documentos da coleção e as N linhas
seguintes contém os nomes dos arquivos desses documentos. Lembrando que
os nomes dos arquivos podem não seguir uma lógica exata.
O sistema deve processar arquivo por arquivo, lendo cada palavra e construindo o ı́ndice invertido. Considere que os arquivos, caso existam, estarão no
diretório de execução.
Arquivo de saı́da
word −> ( occurrence number , d o c i d ) . . .
word −> ( occurrence number , d o c i d ) . . .
word −> ( occurrence number , d o c i d )
...
O ı́ndice invertido.
Entrega
O desafio deve ser enviado para o email [email protected] até as 23:59:59
do dia 25 de junho de 2012, com o assunto no seguinte formato:
desafioPETed1XX:NomeSobrenome, onde XX deve ser substituı́do por
CC para os alunos da turma de Ciência da Computação e EC para os alunos
da turma de Engenharida de Computação.
Os arquivos devem estar compactados e anexados com o mesmo nome do
assunto do email. desafioPETed1XX:NomeSobrenome.tar.gz
Se não for enviado nesse perı́odo ou fora do padrão exigido, a nota será zero.
Obs.: Os alunos da turma de Engenharia de Computação, professor Lucas, devem enviar o desafio em cópia para o email [email protected]
Avaliação
O desafio vale 1 ponto extra na média de acordo com os professores.
Para a avaliação do trabalho serão levados em conta os seguintes itens:
• Padrão das exigências; (Entrada e Saı́da dos dados)
• Alocação de espaço adequado para as palavras;
• Utilização de uma tabela hash bem dimensionada com lista encadeada;
4
• Documentação do código; (Faça útil dos comentários)
• Modularização do código;
• Compilação correta e Makefile;
• Vazamento de memória; (valgrind)
• Erro de contexto; (valgrind)
• Resposta do problema;
• NÃO SERÁ TOLERADO PLÁGIO;
• O trabalho deve ser escrito em C.
NOTA: Alguns trabalhos serão escolhidos aleatoriamente e será realizada
uma entrevista sobre os recursos utilizados.
Obs.: Os alunos da turma de Engenharia de Computação, professor Lucas, terão uma avaliação diferenciada, já que o desafio tem peso de terceiro
trabalho na disciplina, ou seja, serão corrigidos junto ao professor e a nota
afeta diretamente o cálculo da média final.
5