Listas invertidas
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}
Aplicação
[editar | editar código-fonte]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.
