Indexação

A compreensão dessa página pode ser facilitada com a leitura da seção como a Google funciona.

À medida em que os robots vão rastreando a web, as páginas encontradas vão sendo armazenadas nos discos rígidos das Search Engines; as páginas passam por um processo de compressão, mas todo o texto é armazenado.
Cada página recebe um identificador; a Google, por exemplo, denominou esse identificador docID (identificador de documento); qualquer referência à página é feita por meio do identificador.
Nesse estágio, a SE já tem um banco de dados contendo páginas da web; entretanto, nesse formato de armazenamento, torna-se difícil a pesquisa por [palavras-chave], já que, para se analisar o conteúdo de uma página, é necessário recuperá-la, ler seu conteúdo e armazená-la novamente.
Para facilitar (ou melhor, tornar possível) o trabalho de pesquisa, o próximo passo no trabalho das SEs é criar um índice, chamado índice invertido (em inglês, inverted index).
A melhor maneira de se entender o processo de indexação é através de um exemplo simples. Suponhamos que os bots tenham encontrado e armazenado uma página que tenha o seguinte corpo:

A primeira coisa a fazer é atribuir um identificador para o documento; por exemplo, docID=E29A.
A seguir, são feitos alguns ajustes no texto.
Primeiramente, são filtrados os termos muito comuns, como "de", "um", "e", etc, que não são indexados. Nota: a Google filtra os termos comuns em inglês (que ela chama de "stop words"), como "of", "to", etc e informa, na página de respostas, que o termo foi filtrado; leia as instruções da Google para barrar o filtro; palavras comuns em português não são filtradas, mas suporemos no exemplo que elas sejam.
O ajuste seguinte é nas palavras que sobram: todas as palavras têm seus acentos removidos e a caixa é convertida para letra minúscula. Além disso, todos os acentos e sinais de pontuação são eliminados do texto. Isso explica por que pesquisas por [Máquinas de Busca] e [maquinas de busca] geram o mesmo resultado na Google.
Assim, o texto ajustado ficaria:

Cada palavra remanescente recebe um identificador, chamado pela Google wordID. No nosso exemplo, seriam criadas as wordIDs: estudo (wordID=#0001); ferramentas (wordID=#0002); busca (wordID=#0003); tipo (wordID=#0004); e assim por diante. Observe cada palavra recebe um único wordID; assim, a segunda ocorrência da palavra ferramentas não causa a criação de uma nova wordID. O conjunto de palavras compõe o que a Google denominou Lexicon.
O índice invertido é um banco de dados que armazena, para cada palavra (ou seja, cada wordID), os documentos (docIDs) em que elas ocorreram, bem como detalhes da apresentação da palavra. A ocorrência de uma wordID em um documento é chamada Hit.
Num exemplo bem simplificado, poderíamos armazenar apenas os Hits (os docIDs em que a palavra ocorreu) e a posição da palavra no texto. Assim, o início de nosso índice invertido ficaria assim:

wordID	Hits
#0001	(E29A, 1)
#0002	(E29A, 2); (E29A, 12); (E29A, 14)
#0003	(E29A, 3)
#0004	(E29A, 4)
(...)	(...)
#0013	(E29A, 18)
(...)	(...)

Observe que a a palavra "ferramentas", wordID=#0002, teve três hits registrados; observe também que a palavra "usuários", apesar de estar na 18a. posição, recebeu wordID="0013", por conta dos termos que aparecem repetidos.

O processo acima é repetido para todos os documentos armazenados pela Search Engine, e para todas as palavras (excluídas as stop words) encontradas.
Se no documento seguinte uma palavra nova é encontrada, ela recebe uma wordID, é adicionada ao Lexicon, e os hits correspondentes passam a ser registrados.
Suponhamos que, num outro documento de docID="390A", a palavra "ferramentas" ocorra na posição 310 do texto. O registro correspondente a essa palavra seria modificado para refletir a ocorrência desse hit, ficando da seguinte forma:

wordID	Hits
(...)	(...)
#0002	(E29A, 2); (E29A, 12); (E29A, 14); (390A, 310)
(...)	(...)

O índice invertido está completo após o registro da última palavra do último documento.

Utilidades do Índice Invertido

Mesmo nesse modelo bastante simplificado, as utilidades do índice invertido já começam a se tornar evidentes: para cada palavra pesquisada, é possível saber em quantos documentos ela ocorre (é dessa forma que a Google informa "Resultados 1 - 10 de aproximadamente 61.000.000 para [brasil]), e em qual posição do texto elas se encontram; já seria possível fazer uma Search Engine extremamente rudimentar.
Para o caso em que a pesquisa contém duas ou mais palavras, são necessárias duas ou mais pesquisas ao índice invertido; os documentos comuns a todas as pesquisas conterão todas as palavras (mas não necessariamente na ordem pesquisada). Também através de refinamentos das páginas retornadas para cada palavra, já se poderia implementar alguns operadores booleanos, como "or" e "not", Para se encontrar as páginas em que as palavras-chave apareçam na ordem em que foram digitadas, basta fazer uma análise adicional das páginas retornadas para cada palavra, lembrando que palavras adjacentes têm posições de hits consecutivas.
Entretanto, com alguns aprimoramentos, o índice invertido pode tornar-se muito mais útil. Leia a próxima seção, aprimorando o índice invertido.