Algoritmos/Arquivos/Listas invertidas

Lista invertida

Nos dias atuais, temos diversas maneiras de armazenar e buscar dados. Tendo grandes quantidades de dados é sempre necessário inovar e melhorar nossas técnicas. Uma destas técnicas de busca é a lista invertida.

Lista invertida ou índice invertido é um estrutura de dados que permite mapear um conjunto de palavras e símbolos dentro de um arquivo. Desta maneira, facilita a busca de informações em uma estrutura de dados. É usada principalmente na busca de informações em WEB como por exemplo a busca no Google.

Como funciona

Nas listas invertidas todos os "termos" são identificadores, e para cada um deles, temos a informação de onde ele está no nosso arquivo.

Exemplo, temos as seguintes frases abaixo:

1.Olá mundo java.
2.Eu amo java.
3.Eu confio no java. 
4.Java é o melhor.
5.Melhor do mundo.

Vamos colocar as frases acima em uma lista invertida:

"amo" : { 2 }
"confio" : { 3 }
"eu" : { 2 , 3 }
"java" : { 1 , 2 , 3 . 4}
"melhor" : { 4 , 5 }
"mundo" : { 1 , 5 }
"olá"  : { 1 }

Observação: Não é preciso colocar na lista palavras ou símbolos que não tem significado, e após fazer a inserção, é necessário que tudo esteja ordenado.

Agora vamos supor que eu queira pesquisar "mundo java":

Primeiro termo é "mundo" que esta nas frases: { 1 , 5 } 
Segundo termo "java" esta nas frases: { 1 , 2 , 3 , 4 } 
Depois da interseção das duas frases
A única frase que irei encontrar é a frase 1 " Olá mundo java "

Vantagens e Desvantagens

A vantagem de se usar um índice invertido é a grande rapidez das buscas de registros dentro de uma estrutura de dados. Comparado com uma busca sequencial, a busca pelas listas invertidas é muito rápida.Porém a inserção acaba sendo mais difícil devido a complexidade de sua estrutura.

Bibliografia

• Kutova, Marcos (2017) Slides e Vídeo-aulas no AVA
• Wikipedia Lista invertidas