Índices Invertidos

Um índice invertido mapeia cada termo em uma coleção para uma lista de ocorrências dos documentos que o contêm, permitindo que um sistema de busca encontre documentos correspondentes sem escanear cada documento.

Definition

Um índice invertido é uma estrutura de dados que consiste em um dicionário de termos indexados, cada um apontando para uma lista de ocorrências que enumera os documentos que contêm o termo, frequentemente anotada com frequências e posições do termo, para que a recuperação possa ser realizada pela interseção ou fusão de listas de ocorrências.

Scope

Este tópico abrange a estrutura e a construção do índice invertido: o dicionário de termos, as listas de ocorrências registrando identificadores de documentos, frequências de termos e posições, e os algoritmos que constroem e atualizam índices em grandes coleções, incluindo indexação baseada em ordenação por blocos e indexação em memória de passagem única. Ele aborda informações posicionais para consultas de frase e a engenharia da manutenção do índice, enquanto deixa a compressão e a estratégia de avaliação de consultas para tópicos adjacentes.

Core questions

• O que contém uma entrada de dicionário e sua lista de ocorrências?
• Como as posições são armazenadas para suportar consultas de frase e proximidade?
• Como um índice invertido é construído quando a coleção é muito grande para a memória?
• Como um índice é atualizado à medida que documentos são adicionados, alterados ou excluídos?
• Como as listas de ocorrências suportam a interseção eficiente para consultas conjuntivas?

Key concepts

• dicionário de termos
• lista de ocorrências
• identificadores de documentos
• índice posicional
• armazenamento de frequência de termos
• indexação baseada em ordenação por blocos (BSBI)
• indexação em memória de passagem única (SPIMI)
• fusão e atualizações de índice

Key theories

Organização do dicionário e das ocorrências

Separar um dicionário de termos compacto de listas de ocorrências de comprimento variável permite que o sistema procure um termo rapidamente e, em seguida, transmita apenas os documentos relevantes, o que é a base estrutural de toda a recuperação por índice invertido.

Construção de índice escalável

Métodos baseados em disco, como a indexação baseada em ordenação por blocos e a indexação em memória de passagem única, constroem arquivos invertidos para coleções muito maiores do que a memória, acumulando e mesclando índices parciais.

Clinical relevance

O índice invertido é a estrutura de dados central de praticamente todos os sistemas de busca de texto, incluindo motores de busca na web, plataformas de busca de código aberto como Lucene e seus derivados, e busca de texto completo em bancos de dados. Seu design governa quais tipos de consulta são suportados e quão rápida e economicamente eles podem ser respondidos.

History

Arquivos invertidos foram usados em sistemas de recuperação bibliográfica iniciais e se tornaram a estrutura padrão para busca de texto completo à medida que as coleções cresciam. Pesquisas nas décadas de 1990 e 2000, incluindo métodos de construção escaláveis como a indexação em memória de passagem única, tornaram prático indexar corpora em escala web, e a estrutura agora sustenta bibliotecas de busca de código aberto amplamente utilizadas.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

Por que é chamado de índice 'invertido'?

Um índice normal (direto) lista, para cada documento, os termos que ele contém. O índice invertido reverte esse mapeamento para listar, para cada termo, os documentos que o contêm. Essa inversão é exatamente o que torna a busca baseada em termos rápida.

Para que é usado um índice posicional?

Um índice posicional armazena as posições em que cada termo ocorre dentro de cada documento. Isso permite que o sistema responda a consultas de frase e consultas de proximidade, onde a ordem ou a proximidade dos termos importa, em vez de apenas se os termos aparecem em algum lugar no documento.