Saltar para o conteúdo

Listas invertidas

Origem: Wikipédia, a enciclopédia livre.

Em ciência da computação, Lista Invertida (do inglês inverted list ou inverted index) é uma estrutura de dados que mapeia termos às suas ocorrências em um documento ou conjunto de documentos, armazenados em um banco de dados. É uma estratégia de indexação que permite a realização de buscas precisas e rápidas, em troca de maior dificuldade no ato de inserção e atualização de documentos.

É a mais popular estratégia de sistemas para obtenção de dados, usada em larga escala em sistemas de gerenciamento de bancos de dados (como o Adabas) e serviços de busca (como o Google).

Funcionamento

[editar | editar código-fonte]

A lista invertida geralmente é construída com base em uma lista tradicional de documentos, e é assim chamada por inverter a hierarquia da informação - ao invés de uma lista de documentos contendo termos, é obtida uma lista de termos, referenciando documentos (através de um identificador único, como uma chave primária).

Junto deste identificador, podem ser armazenadas outras informações, conforme adequado para as buscas desejadas - por exemplo, amazenar a posição do termo no documento é útil para uso de algoritmos que calculem a relevância dos resultados utilizando a proximidade de palavras.

Por exemplo, dada a seguinte lista de documentos:

1: "Sei que sou"
2: "Sou o que sei"
3: "Sou uma banana"

Obtemos a seguinte lista invertida:

"sei" : {1, 2}
"que" : {1, 2}
"sou" : {1, 2, 3}
"o" : {2}
"uma" : {3}
"banana" : {3}

Listas invertidas são um elemento central de sistemas de busca, pois estes visam trazer resultados de forma rápida e eficiente.

Buscas por termos em uma lista tradicional exigiram percorrer cada documento e cada palavra dentro destes em busca do termo, enquanto que, com o uso de um índice reverso, pode-se saltar diretamente para o termo buscado. Logo, o uso deste recurso permite que os resultados sejam obtidos de forma consideravelmente mais rápida (a diferença de desempenho tende a ser cada vez mais significativa conforme aumenta a quantidade de documentos).

O uso de listas invertidas tem o potencial de deixar as buscas mais eficientes, dado que estas permitem que sejam armazenadas informações adicionais que, acompanhadas de algoritmos adequados, tornam fácil a classificação e ordenação dos resultados.

O custo destes benefícios vem na forma de trabalho adicional para a manutenção desta lista; já que é preciso manter a lista invertida atualizada conforme documentos são inseridos, alterados e excluídos da lista tradicional.