Introdução a Recuperação de Informação (Information Retrieval)

Recuperação de Informação (em inglês, Information Retrieval) é uma área da computação que lida com o armazenamento de documentos e a recuperação automática de informação associadas a eles. (Wikipedia)

Com o crescimento exponencial das informações disponíveis na web, tornou-se praticamente inviável encontrarmos as informações necessárias, navegando entre elas. Além disto, estima-se que 80% dos dados não são estruturados, tornando esta busca mais difícil.

Neste cenário, um dos problemas é a necessidade de que estas informações sejam recuperadas de forma rápida e assertiva, além de que o usuário que efetua esta consulta não esta disposto a analisar muitos resultados, e por este motivo a consulta deve conter os resultados mais relevantes nas primeiras posições.

Considerando este cenário, técnicas de Recuperação de informação (IR) são utilizadas, pois ela foca em recuperar documentos de natureza não-estruturada, geralmente textos, que satisfazem a necessidade de informação.

Neste artigo abordarei primeiramente o modelo de recuperação booleana(que geralmente é utilizado para buscas em e-mail) e o índice invertido, para introduzirmos o assunto de buscas.

No próximo artigo, explanarei sobre os passos padrões para a recuperação de informação, desde a coleta de documentos até a consulta e retorno dos resultados para o usuário, e alguns processos que são executados em cada uma dessas fases.

Para todo sistema de IR(Information Retrieval), são dois os principais pontos chaves: A precisão, ou seja, a fração dos resultados que são relevantes para as necessidades de informação do usuário, e o recall, que é a fração dos documentos relevantes que foram retornados pelo sistema. Baseado nestes conceitos, abaixo darei uma visão geral de como funcionam os mecanismos de buscas padrões.

Modelo de Recuperação Booleana (Boolean Retrieval Model)

É um modelo de recuperação de informação que é baseada em expressões booleanas sobre os termos (em palavras, ex.: “Hong Kong”, “I-9”, etc), ou seja, onde os termos da busca são baseados em operadores lógicos (AND, OR, NOT). Este modelo visualiza os documentos como um conjunto de palavras.

Por exemplo, podemos criar um vetor com os termos do documento e gerarmos a tabela abaixo, onde visualizamos as palavras na 1ª coluna (Arroz, Feijão, etc) e os documentos na 1ª linha (Receita 1, Receita 2, etc). Desta forma podemos ver em quais documentos as palavras aparecem (valor 1) e em quais não aparecem (valor 0).

Dada a tabela, se quisermos recuperar os documentos que tenham Arroz, Feijão e NÃO tenham Batata, pegamos o vetor de cada termo, que contém a informação em quais documentos eles aparecem (valor 1), e aplicamos a operação AND, como por exemplo:

Arroz = 1111
Feijão = 1001
Batata = 0110 (como é negação, se torna) 1001

Assim: Arroz AND Feijão AND Batata => 1111 AND 1001 AND 1001 = 1001, nos mostrando que esta combinação de termos está contida no documento 1 (Receita 1) e no 4 (Receita 4).

Índice Invertido (Inverted Index)

No exemplo anterior, onde criamos uma tabela relacionando os termos com os documentos, informando 1 nos termos que existem e 0 para os que não existem, podemos verificar que a matriz fica extremamente esparsa, ou seja, com diversos 0’s que nos causa um uso de memória desnecessário no processamento.

Uma melhor representação desta matriz seria armazenarmos a posição dos termos que ocorrem (1´s), não armazenando as correlações dos termos X documentos que não ocorrem (0’s).

Assim, a ideia central do Índice Invertido é armazenarmos somente as posições dos documentos onde os termos aparecem e, opcionalmente, a frequência que esses termos aparecem no documento. Não por menos, o Índice Invertido se tornou o termo padrão na Recuperação de Informação e um dos mais utilizado. Com as mesmas informações do exemplo anterior, criamos um exemplo básico da ideia principal do Índice Invertido:

Resumindo, o Index Invertido cria um dicionário de termos, e para cada termo associamos uma lista das posições (ou dos IDs) dos documentos onde esses termos ocorrem.

Adicionalmente, podemos utilizar as consultas (queries) booleanas. Por exemplo, se quisermos os documentos que contém os termos Arroz e Feijão, utilizando o Índice invertido, efetuamos os seguintes passos:

1. Localizamos o termo Arroz, e recuperamos a lista de documentos que contém esse termo.

2. Localizamos o termo Feijão, e recuperamos a lista de documentos com Feijão

3. Realizamos a intersecção das duas listas de documentos

4. O resultado são os documentos que contém os 2 termos, que no exemplo acima são os documentos 1 e o 4.

OBS: Como veremos posteriormente na seção Criação de Índices do próximo artigo, este algoritmo funciona somente se as listas dos documentos estiverem ordenadas.

Outra possibilidade é a utilização da busca por proximidade. Resumidamente, se desejarmos buscar Arroz e Feijão, mas considerando que no mesmo documento eles estejam numa distância máxima de 3 termos, a consulta retornará o documento se, e somente se, a palavra Arroz estiver perto de Feijão, na distância máxima de 3 palavras, como por exemplo: “Arroz com Feijão” (2 termos de distância), ou “Arroz com bastante Feijão” (3 termos de distância).

Caso a frase seja “Arroz com batata frita, adicionado com Feijão”, o documento não será considerado, devido a distância entre Arroz e Feijão, que fazem parte da consulta, terem distância maior que 3 entre eles.

Para que este tipo de busca seja possível, além da lista de documentos, é necessário associarmos ao índice do termo a posição em que ele aparece dentro do documento.

Finalizando, o Modelo de Recuperação de Informação Booleana pode responder qualquer consulta que contém uma expressão booleana com a utilização dos operadores AND, OR e NOT. Ela também é precisa pois os termos estão ou não estão nos documentos.

Muitos sistemas de buscas o utilizam, como as buscas do email, intranet, busca em arquivos, etc.

Sistemas de buscas mais rebuscados, como Google e o Bing, não utilizam o modelo booleano. Eles utilizam a Recuperação por Ranking.

Para que a consulta sobre este e demais modelos seja possível, é necessário a criação da estrutura e dos índices. Para isto, existem algumas técnicas e procedimentos, que descreverei nos próximos artigos, e que estarão organizadas da seguinte forma:

1. Recuperação dos documentos

2. Análise e pré-processamento linguístico

3. Criação dos Índices

4. Consulta

5. Scoring e Rankeamento

6. Exibição do resultado

Neste artigo tivemos uma breve introdução sobre IR (Information Retrieval), exibindo duas formas de recuperação de informação em documentos, a Booleana e o Índice Invertido.

Como citado, no próximo artigo falarei sobre algumas técnicas e procedimentos utilizadas no processo de recuperação de informação.

Espero que tenham gostado e que esta introdução tenha sido útil ! ;)