Construindo o índice

Depois que as aranhas completaram a tarefa de localização das informações nas páginas da Web (e devemos notar que essa é uma tarefa nunca realmente concluída: a natureza constantemente alterável da Web significa que as aranhas estão sempre rastejando), o mecanismo de busca deve armazenar as informações de uma forma que as torne úteis. Existem dois componentes-chave envolvidos na reunião de dados acessíveis aos usuários:

• as informações armazenadas com os dados;
• o método pelo qual as informações são indexadas.

No caso mais simples, um mecanismo de busca poderia simplesmente armazenar a palavra e a URL onde ela foi encontrada. Na realidade, isso funcionaria para um mecanismo de uso limitado, já que não haveria maneira de dizer se a palavra foi usada de uma maneira importante ou trivial em uma página, se ela foi usada uma vez ou muitas vezes ou se a página continha links para outras páginas contendo a palavra. Em outras palavras, não haveria maneira de construir a lista de classificação que tenta apresentar as páginas mais usadas no topo da lista dos resultados da busca.

Para criar mais resultados úteis, a maioria dos mecanismos de busca armazena mais do que simplesmente a palavra ou URL. Um mecanismo pode armazenar o número de vezes que a palavra aparece em uma página. O mecanismo pode atribuir um peso a cada entrada, com valores crescentes atribuídos às palavras à medida que elas aparecem próximas ao topo do documento, em subtítulos, em links, nas meta tags ou no título da página. Cada mecanismo de busca comercial tem uma fórmula diferente de atribuir peso às palavras em seu índice. Essa é uma das razões pelas quais uma busca pela mesma palavra em diferentes mecanismos de busca produzirá listas diferentes, com as páginas apresentadas em ordens diferentes.

Independentemente da combinação precisa de partes adicionais de informações armazenadas por um mecanismo de busca, os dados serão codificados para economizar espaço de armazenamento. Por exemplo, o documento original do Google descreve o uso de 2 bytes, de 8 bits cada, para armazenar informações sobre a classificação do peso das palavras: se a palavra estava em letras maiúscula, seu tamanho de fonte, posição e outras informações para ajudar na classificação. Cada fator pode consumir até 2 ou 3 bits dentro de um grupamento de 2 bytes (8 bits = 1 byte). Como resultado, uma grande quantidade de informações pode ser armazenada de uma forma muito compacta. Depois que as informações são compactadas, elas estão prontas para indexação.

Um índice tem um único propósito: ele permite que as informações possam ser encontradas o mais rapidamente possível. Existem bem poucas maneiras para se construir um índice, mas uma das maneiras mais efetivas é construir uma tabela hash. Em um hashing, uma fórmula é aplicada para anexar um valor numérico a cada palavra. A fórmula é projetada para distribuir igualmente as entradas por um número predeterminado de divisões. A distribuição numérica é diferente da distribuição de palavras no alfabeto, e essa é a chave para a eficácia de uma tabela hash.

Em inglês, existem algumas letras que iniciam muitas palavras, ao passo que outras iniciam menos palavras. Você descobrirá, por exemplo, que a seção "M" do dicionário é muito mais grossa que a seção "X". Essa diferença significa que localizar uma palavra que comece com uma letra muito "popular" poderia demorar muito mais do que encontrar uma palavra que comece com uma letra menos popular. O processo de hashing iguala a diferença e reduz o tempo médio gasto para encontrar uma entrada. Ele também separa o índice da entrada real. A tabela hash contém o número hashed juntamente com um ponteiro para os dados reais, que podem ser classificados de qualquer maneira que permita que eles sejam armazenados mais eficientemente. A combinação de indexação eficiente e armazenamento eficaz possibilita a obtenção de dados mais rapidamente, mesmo quando o usuário cria uma busca complicada.