Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um…

Questão

Descreva com precisão o algoritmo e as estruturas de dados (registros, hash ou listas) para construir um índice invertido: dado uma coleção de documentos, produzir uma estrutura que permita, para qualquer termo, retornar a lista de documentos que o contêm. Explique como representar cada entrada, como atualizar ao processar cada documento e como realizar a busca por termo.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Estruturas: tabela hash (mapa) de termo ? lista de postagens; cada postagem é um registro com campos {docID, frequência, (opcional) posições}. Algoritmo de construção: para cada documento D com id docID, tokenizar o texto; para cada token t, procurar t na tabela hash; se ausente, inserir chave t com lista vazia; na lista de postagens, se o último registro não tem docID igual a docID, anexar novo registro {docID,1, [pos]}; caso contrário, incrementar frequência e acrescentar posição. Para evitar duplicados ao processar um mesmo documento, atualizar o registro existente em vez de adicionar outro. Representação das postagens: listas ligadas ou arrays dinâmicos; manter postagens ordenadas por docID facilita operações de interseção em consultas múltiplas. Busca por termo: buscar t na tabela hash (O(1) médio) e retornar a lista de postagens associada; para consulta multi-termo, intersectar listas ordenadas (merge). Complexidade: construção O(total_tokens) tempo médio; busca por termo O(1) para localizar a lista, mais custo de varredura das postagens. Observações: para escala, usar compressão de postagens, blocos ou estruturas em disco e manter vocabulário em hash ou trie para memória eficiente.

Explicação

A explicação apresenta de forma clara as estruturas de dados necessárias para implementar um índice invertido, detalhando como cada entrada é representada e atualizada durante o processamento dos documentos. O algoritmo descrito assegura eficiência tanto na construção do índice quanto na busca por termos, otimizando operações com o uso de tabelas hash e listas de postagens. Além disso, menciona considerações práticas para escalabilidade e eficiência em consultas, o que é fundamental em sistemas de busca.

Raio-X da questão

Questões parecidas com resolução

• Em um grafo denso, qual representação — matriz de adjacência ou lista de adjacência — permite verificar em tempo…
• Descreva sucintamente como verificar se um grafo simples não direcionado é k-regular usando sua lista de adjacência; que…
• Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
• Em um autômato orientado por eventos que registra leituras periódicas de um sensor, qual estrutura de dados é mais…
• Projete um autômato baseado em eventos para gerenciar reservas de salas multimídia na escola: descreva estados, eventos…
• Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…

Todas as questões de Organização e representação da informação