Programas em Linguagem C

Descrição do trabalho
O profissional deve escrever um programa para ler um arquivo tipo texto contendo as descrições de documentos textuais de uma coleção. Os documentos já foram pré-processados, tal maneira que cada linha do arquivo corresponde a um documento da coleção. Cada linha tem o seguinte formato:
c t1:ft1 t2:ft2 t3: ft3 …..
O primeiro valor c de uma linha corresponde à um número inteiro indicando a categoria a qual o documento pertence (esportes, cultura, Matemática, etc). Após o valor de classe há uma sequência de pares do tipo ti:fti, onde ti é um número inteiro correspondente a uma palavra (ou termo) que aparece no documento e fti é a frequência com que o termo ti aparece nesse documento (linha). Por exemplo, suponha que na j-ésima linha do arquivo há uma linha (correspondendo ao j-ésimo documento), com os seguintes valores:
5 0:13 1:1 6:1 10:1 13:2 15:2 17:1 18:2 26:16 27:3 28:17 29:2 30:3 36:3 37:54 40:21
Essa linha indica o seguinte: o documento j é da categoria 5 e é composto pelos termos indicados pelos primeiros componentes dos pares seguintes. Por exemplo, o termo 0 ocorre 13 vezes nesse documento, o termo 1 ocorre apenas uma vez os termos 3, 4 e 5 não ocorrem nesse documento. Repare que os pares aparecem ordenados em ordem crescente dada pelo valor dos termos.
O trabalho consiste em criar, inicialmente em memória, um índice invertido para a coleção.


O índice permite saber quais documentos possuem um determinado termo. O índice invertido é uma estrutura de dados utilizada em diversas aplicações, tais como máquinas de busca (como Google, Bing), para classificação de documentos e para agrupamento de documentos.
Por exemplo, se quisermos saber quais documentos possuem os termos t1 e t5, o índice nos permite concluir que apenas o documento d300 possui os dois termos.

O profissional deve construir um índice invertido para a coleção de documentos descrita acima. Para isso, ele deve ler o arquivo tipo texto contendo a coleção. O conjunto de termos do índice deve permitir que se encontre rapidamente um termo. Como em uma coleção de documentos podem existir dezenas de milhares ou centenas de milhares de termos distintos, uma busca sequencial no conjunto de termos não é desejável. Uma possibilidade seria implementar o conjunto de termos como um vetor de termos e mate-lo ordenado pelos termos e utilizar uma pesquisa binária sempre que se quiser pesquisar um termo no conjunto. Repare que o conjunto de documentos associados a um termo varia de tamanho entre os termos. Isso ocorre porque alguns termos são mais comuns em documentos do que outros. Cada elemento do conjunto de documentos possui três campos: o identificador do documento, a frequência do termo no documento (ft,d) e a classe do documento.

O programa deve permitir efetuar uma pesquisa no índice. Na pesquisa é informada uma sequência de termos e o programa deve consultar o índice invertido e deve retornar os documentos que possuem todos os termos informados na pesquisa.
O programa deve permitir que o índice invertido seja gravado em arquivo binário. No início da execução do programa, se um arquivo binário com o índice não existir, o programa deve pedir o arquivo texto e construir o índice em memória e depois grava-lo em um arquivo no disco. Se o arquivo binário existir, o programa deve abri-lo e passar a aceitar consultas.