CURSO DE BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
RECUPERAÇÃO DE INFORMAÇÃO II

Última alteração: 16. Janeiro 2007

${2}^{\underline{\rm o}}$ semestre de 2005
Professor: Nivio Ziviani (ICEx - Sala 4024)
Monitor: Álvaro Pereira Jr
Trabalho Prático 1: 11/08/2005
Data de Entrega: 05/09/2005
Penalização por Atrazo: 1 ponto até 09/09/2005 mais 1 ponto por dia útil a seguir

Arquivos Invertidos

O objetivo deste trabalho é projetar e implementar um sistema de programas para recuperar eficientemente informação em grandes arquivos armazenados em memória secundária, utilizando um tipo de índice conhecido como arquivo invertido. As principal referências para este trabalho são Witten, Moffat e Bell (1999), Neubert (2000) e Moffat e Bell (1995). Nesta primeira parte do trabalho o seu programa deverá ser capaz de construir o índice sem necessidade de ser in situ, e sem necessidade de usar compressão.

O conceito de arquivo invertido será apresentado a seguir. Considere um conjunto de documentos. A cada documento é atribuído um conjunto de palavras-chave ou atributos. Um arquivo invertido é constituído de uma lista ordenada (ou índice) de palavras-chave (atributos), onde cada palavra-chave tem uma lista de apontadores para os documentos que contêm aquela palavra-chave. Este é o tipo de índice utilizado pela maioria dos sistemas para recuperação em arquivos constituídos de texto.

A utilização de arquivo invertido aumenta a eficiência de pesquisa em várias ordens de magnitude, característica importante para aplicações que utilizam grandes arquivos constituídos de texto. O custo para se ter essa eficiência é a necessidade de armazenar uma estrutura de dados que pode ocupar entre 2% e 100% do tamanho do texto original, dependendo da quantidade de informação armazenada no índice, mais a necessidade de atualização do índice toda vez que o arquivo de documentos sofre alguma alteração.

O que fazer

A estrutura de dados a ser implementada deverá ser constituída do vocabulário do texto, incluindo o número de documentos associados com cada palavra-chave e uma lista de ocorrências da palavra na coleção de documentos. Cada entrada da lista indica o número do documento onde a palavra ocorreu e o número de ocorrências. O formato da lista invertida deve ser o formato apresentado em Moffat e Bell (1995) e Witten, Moffat e Bell (1999). Para cada termo $t$ devem ser armazenados todos os pares $<d,f_{d,t}>$, onde $d$ é o número do documento onde $t$ ocorre e $f_{d,t}$ é a freqüência do termo $t$ no documento $d$.

As listas de números de documentos dentro da lista invertida contém números inteiros positivos em ordem ascendente. Existem métodos de compressão específicos para conjuntos de números em ordem ascendente que levam a boas taxas de compressão. três destes métodos são codificação unária, Elias-$\gamma$ e Elias-$\delta$, todos descritos nas referências citadas abaixo. Este trabalho não exige o uso de compressão do índice. Entretanto, quem decidir usar compressão terá 10% de pontos extras.

Processamento de Consultas

O sistema de programas recebe do usuário uma ou mais palavras e imprime todos os documentos que satisfaçam a consulta. No caso deste trabalho a linguagem de consulta pode conter:

a)

um conector lógico and entre duas palavras,

b)

um conector lógico or entre duas palavras.

A saída será apenas a impressão dos documentos (seus identificadores) que satisfaçam a consulta.

Como fazer

Utilize os arquivos de documentos da coleção TREC disponível na rede do DCC, com as seguintes características:

Coleção	Tamanho (Mb)
wsj88	109
wsj88_10	10
wsj88_20	20
wsj89	2.8

A seguir é mostrado um documento típico da coleção TREC.

<DOC>
<DOCNO> WSJ891102-0193 </DOCNO>
<DD> = 891102 </DD>
<AN> 891102-0193. </AN>
<HL> Who's News: @ Economist Newspaper Ltd. </HL>
<DD> 11/02/89 </DD>
<SO> WALL STREET JOURNAL (J) </SO>
<CO> WNEWS </CO>
<DATELINE> ECONOMIST NEWSPAPER Ltd. (London)  </DATELINE>
<TEXT>
Pierre Vinken, 61 years old, will join the board as a nonexecutive director
Nov. 29. Mr. Vinken is chairman of Elsevier N.V., the Dutch publishing group.
</TEXT>
</DOC>

Apresente uma boa documentação do trabalho, contendo pelo menos os seguintes itens: saída legível mostrando o funcionamento do código, código bem estruturado, comentários explicativos sobre os algoritmos e estruturas de dados, análise da complexidade e análise dos resultados.

Referências

Ian H. Witten, Alistair Moffat e Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999, second edition.

Marden Neubert: Algoritmos Distribuídos para a Construção de Arquivos Invertidos, Dissertação de Mestrado, Curso de Pós-Graduação em Ciência da Computação da UFMG, Março de 2000.

Alistair Moffat e Timothy C. Bell: In Situ Generation of Compressed Inverted Files, Journal of the American Society for Information Science, 46(7), 1995: 537-550.

Ricardo Baeza-Yates and Berthier Ribeiro-Neto: Modern Information Retrieval, Addison Wesley, 1999, 513 pages.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 ri05tp1

The translation was initiated by Nivio Ziviani on 2007-01-16