Uma biblioteca contém uma grande coleção com os mais variados conteúdos: livros, artigos, reportagens e vários outros. Depois de ter digitalizado cada item de seu acervo como um arquivo de texto, ela irá implementar uma nova funcionalidade em seu site: uma busca contextual. O objetivo é encontrar frases ou períodos em algum texto que contenham uma ou mais palavras próximas. Um período é sempre terminado por um ponto.

Por exemplo, considere o texto abaixo:

Se tu falas muitas palavras sutis. Se gostas de senhas, sussurros, ardis. A lei tem ouvidos pra te delatar. Nas pedras do teu próprio lar.

Se trazes no bolso a contravenção. Muambas, baganas e nem um tostão. A lei te vigia, bandido infeliz. Com seus olhos de raios X.

Se vives nas sombras, frequentas porões. Se tramas assaltos ou revoluções. A lei te procura amanhã de manhã. Com seu faro de doberman.

Se procurarmos pela palavra lei, encontraremos três frases, uma em cada estrofe:

A lei tem ouvidos pra te delatar.
A lei te vigia, bandido infeliz.
A lei te procura amanhã de manhã.

Já, se procurarmos por lei te, temos que procurar as duas palavras consecutivas e encontramos apenas duas frases:

A lei te vigia, bandido infeliz.
A lei te procura amanhã de manhã.

Um motor de buscas é um conjunto de algoritmos e estruturas de dados que servem para encontrar informação rapidamente. O objetivo é preprocessar um ou mais arquivos ou dados de diferentes formatos de forma que, quanto uma consulta for realizada, seja possível responder rapidamente.

Sua tarefa é projetar e implementar as estruturas de dados adequadas para indexar aquivos de texto da biblioteca, de maneira que os períodos com os termos buscados sejam encontrados rapidamente. Você irá construir um pequeno servidor chamado buscador para responder as requisições de busca do site.

Entrada

Cada linha da entrada corresponde a uma requisição ao servidor no formato do exemplo aquivo.txt?q=termos buscados.

dados/hino.txt?q=lei
dados/hino.txt?q=lei te
dados/hino.txt?q=estorvo es
dados/hino.txt?q=nocivo es

Nesta tarefas, suponha que a entrada contém requisições para um único arquivo. Além disso, os arquivos contêm apenas caracteres ASCII e todo período tem menos que 1024 caracteres e é terminado por um único ponto. Veja um exemplo

Hino de Duran.
Chico Buarque.

Se tu falas muitas palavras sutis.
Se gostas de senhas, sussurros, ardis.
A lei tem ouvidos pra te delatar.
Nas pedras do teu proprio lar.

Se trazes no bolso a contravencao.
Muambas, baganas e nem um tostao.
A lei te vigia, bandido infeliz.
Com seus olhos de raios X.

Se vives nas sombras, frequentas poroes.
Se tramas assaltos ou revolucoes.
A lei te procura amanha de manha.
Com seu faro de doberman.

E se definitivamente a sociedade.
So te tem desprezo e horror.
E mesmo nas galeras es nocivo.
Es um estorvo, es um tumor.
A lei fecha o livro, te pregam na cruz.
Depois chamam os urubus.

E se pensas que burlas as normas penais.
Insuflas, agitas e gritas demais.
A lei logo vai te abracar infrator.
Com seus bracos de estivador.

Se pensas que pensas.
Estas redondamente enganado.
E como ja disse, o Dr Eiras.
Que vem chegando ai.
Junto com o delegado.
Pra te leva.

Saída

Para cada requisição, o servidor deve mostrar até três períodos em que as palavras foram encontradas, na ordem em que esses períodos aparecem no arquivo. Caracteres de pontuação (vírgula, hífen, ponto-e-vírgula, etc.) são ignorados quando procurando palavras consecutivas, mas todas as palavras devem estar no mesmo período. Apenas períodos com as palavras inteiras e com a mesma capitalização devem ser listados. Por exemplo, uma busca por lei não corresponde ao período A Lei 12669 dispoe sobre obrigacoes do produtor de leite. Esse período também não corresponde a uma busca por produtor leite.

Buscando 'lei'
   -> encontrado em 'A lei tem ouvidos pra te delatar'
   -> encontrado em 'A lei te vigia, bandido infeliz'
   -> encontrado em 'A lei te procura amanha de manha'
   -> e em mais 2 periodos...

Buscando 'lei te'
   -> encontrado em 'A lei te vigia, bandido infeliz'
   -> encontrado em 'A lei te procura amanha de manha'

Buscando 'estorvo es'
   -> encontrado em 'Es um estorvo, es um tumor'

Buscando 'nocivo es'
   -> 'nocivo es' nao encontrado

Dicas

Como sempre, pense muito calmamente no seu algoritmo antes de começar a programar. Particularmente nessa tarefa, é importante parar e refletir sobre suas estruturas de dados. Faça um desenho de suas estruturas de dados e escreva o algoritmo com esse desenho em mente. Se perceber que elas não são adequadas, repense e projete estruturas melhores antes de programar.

Se quiser, você pode supor que cada período tem no máximo 100 palavras e que cada arquivo tem no máximo 80000 palavras.

Critérios

As estruturas de dados para realizar a indexação do arquivo devem ser baseadas em tabela de espalhamento. É obrigatório adicionar um comentário breve (entre 15 e 40 palavras) na sua função de hashing explicando a sua escolha. Se quiser, é permitido pesquisar outras funções de hashing na internet, mas é mandatório adicionar um link acessível para a fonte e é proibido copiar trecho de código: faça sua própria implementação.

O diretório da tarefa já contém uma implementação ingênua da tarefa que não utiliza tabela de espelhamento nos arquivos buscador.c, utils.h, utils.c, indice.h e indice.c. Esses arquivos já contêm funções para ler a entrada e mostrar a saída na tela. É parte da tarefa ler e entender como o programa é organizado.

Você deve alterar apenas o arquivo indice.c que contém a implementação do índice. Se desejar, pode adicionar novos arquivos à implementação, mas não é necessário nesta tarefa.

Para obter conceito C, basta implementar busca com uma única palavra.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de submetida a versão final da tarefa, você deverá apresentá-la a um monitor PED. Para isso, você deve procurar atendimento em algum horário com monitor PED e digitar apresentar 8 no canal fila-apresentar para entrar na fila.

← Anterior Voltar Próximo →