Para construir um índice, seja uma matriz de incidência ou um índice invertido, alguns detalhes em relação aos documentos e aos termos do vocabulário devem ser considerados.
Documentos
O primeiro ponto a se considerar é o que será indexado, o que será um documento no índice.
Um livro pode ser considerado um documento, o problema é que existem muitas palavras em um livro e diferentes palavras podem ocorrer em capítulos diferentes gerando um resultado não esperado.
Por exemplo, se o livro Introduction to Algorithms for indexado, ele pode ser o resultado para a consulta graph AND quicksort.
Não que o resultado esteja errado, essas palavras existem no livro, mas talvez o objetvo da consulta era encontrar uma forma de ordenar um grafo com quicksort.
A solução é indexar partes menores do conteúdo, capítulos, páginas ou parágrafos.
Se levar esse concceito adiante, é possível indexar frases, porém o conteúdo será tão granular que muitas consultas podem falhar porque duas palavras não aparecem na mesma frase, mas no mesmo parágrafo.
Também é importante notar que a quantidade de documentos tem influência direta no tamanho do índice.
Portanto, será necessário um índice grande para armazenar muitos documento pequenos.
Vocabulário (termos)
A outra parte importante do índice é o vocabulário, ou os termos que serão indexados. Antes de entrar em detalhes sobre os processos é importante mencionar a diferença entre token, tipo (type) e termo (term). Dada a frase Blumenau é uma cidade e Gaspar é uma das cidades vizinhas, as definições são:
- token:
["Blumenau", "é", "uma", "cidade", "e", "Gaspar", "é", "uma", "das", "cidades", "vizinhas"] - tipo (type):
["Blumenau", "é", "uma", "cidade", "e", "Gaspar", "é", "uma", "das", "cidade", "vizinha"]- Esse é o resultado após um pré-processamento. Normalmente, palavras são normalizadas para uma forma padrão.
- Note que
cidades->cidadeevizinhas->vizinha.
- termo (term):
["Blumenau", "cidade", "Gaspar", "vizinha"]- Apenas os tokens que foram indexados, nesse caso as stop-words não foram indexadas
A primeira parte a considerar é como obter os tokens a partir de um documento. Esse processo se chama tokenizaton e é, basicamente, separar o texto em espaços em branco. Porém, alguns casos podem gerar alguns problemas:
- isn’t deve ser: is not, isn’t, isn t (esse caso acontece com nomes também)
- Alguns idiomas não separam algumas (Chinês, Japonês)
- Los Angeles será separado em Los e Angeles
- Indexar quantidades numéricas (idades, valores monetários)
De forma geral, pode ser necessário identificar o idioma do documento antes de fazer a tokenization para decidir quais regras aplicar. Uma alternativa é indexar sequências de k letras ao invés de palavras separadas.
O próximo passo é obter os tipos (types), ou seja, fazer equivalência de classes.
A forma mais simples, é manter todos os token em lower case.
Porém, nomes próprios como Blumenau deveriam ficar com a primeira letra maiúscula.
Nesse caso também é necessário ponderar se os usuários escrevem as consultas sempre com letras minúsculas ou não.
Outra abordagem é manter um mapeamento de tokens que podem ocorrer nos documentos para a versão normalizada.
Aqui, é possível mapear windows (janelas) para Windows (sistema operacional) assim como manter Windows inalterado.
A dificuldade é em manter esse mapeamento atualizado e também a decisão de expandir a consulta ou indexar todas as versões variantes.
Para evitar o processo manual, existem duas técnicas que tentam automatizar esse processo: stemming e lemmatization.
Ambas removem partes dos tokens para obter uma forma normalizada.
A diferença é que stemming apenas remove partes do token enquanto lemmatization tenta fazer uma análise morfológica e obter a forma normal (como em um dicionário) do token.
Em inglês, saw (ver):
- stemming:
saw->s - lemmatization:
saw->saw(serra) ousee(ver) dependendo do contexto
É importante notar que stemming e lemmatization não ajudam muito no inglês, mas podem ser muito importantes em outros idiomas. Esses detalhes podem variar entre idiomas, como o uso de acentos e mudam com o tempo, conforme o idioma evolui. No caso do português brasileiro, a remoção de acentos é uma forma de normalizar e fazer equivalência de classes.
O “último” passo antes de indexar os tokens é uma possível remoção de stop-words. Stop-words são palavras que não agregam em conteúdo, mas são necessárias para dar fluência ao texto. O prinicipal motivo para a remoção dessas palavras é o tamanho do índice a ser mantido, visto que essas palavras aparecem em praticamente qualquer documento. Em tempos mais antigos era comum remover essas palavras, mas atualmente elas já podem fazer parte do índice, visto que o custo de armazenamento diminuiu com o tempo. Outro motivo é que algumas consultas poderiam falhar, por exemplo:
- President of the USA -> President USA, portanto, qualquer consulta com essas duas palavras seria retornada
- A banda The Who não seria mapeada, visto que the e who são stop-words em inglês
- Algo similar iria acontecer com Let it be (música dos Beatles) e To be or not to be (frase de Shakespeare)
Assim, manter as stop-words no índice com o custo de um pouco de armazenamento pode melhorar consideravelmente os resultados.
Existem muitos casos que podem acontecer ao montar um índice. Como na maioria dos cenários, não existe uma abordagem única que pode ser utilizada em todos os casos. É necessário analisar o contexto do problema e ver o que funciona em cada caso para tomar as decisões necessárias.