Motores de pesquisa: história, como funcionam e o futuro

Motores de pesquisa: história, como funcionam e o futuro
04 . Novembro . 2013
  • seo
  • search engine marketing

Os motores de pesquisa são uma tecnologia incontornável no nosso dia-a-dia, é através deles que começam as nossas viagens no ciberespaço. Logo que nos surge uma dúvida ou uma necessidade, basta-nos pensar numa palavra e logo a estamos a digitar numa caixa de texto, e ainda sem sequer ter pressionado o enter, já estamos a ser bombardeados com os resultados.

Os motores de pesquisa não mudaram muito no seu aspeto geral ao longo dos tempos, a sua estrutura foi-se mantendo a mesma ao longo da sua evolução:

  1. uma caixa de texto para digitar as palavras;
  2. um botão para iniciar a pesquisa;
  3. uma secção para mostrar os resultados paginados.

Os avanços mais significativos atingidos ao longo da sua história foram conseguidos sobretudo na sua retaguarda, ou seja, nos algoritmos que constroem o seu motor, na velocidade a que eles funcionam e finalmente na quantidade de informação com que são alimentados. Não podemos também excluir os progressos de que o hardware foi alvo em termos de velocidade e capacidade de processamento, assim como no facto do custo e a capacidade do armazenamento terem evoluído em sentidos completamente opostos com o amadurecer destas tecnologias.

Existem diversos tipos de motores de pesquisa, mas vamos concentrar o nosso estudo nos motores de pesquisa da World Wide Web (WWW) baseados em rastreamento (crawler-based). Vamos apresentar de seguida um resumo das principais inovações e descobertas conseguidas até à data presente no que diz respeito à indústria dos motores de pesquisa. Após isso apresentaremos os conceitos base aplicados ao seu funcionamento, e faremos uma sugestão de uma solução para implementar o seu próprio motor de pesquisa. Por fim apresentaremos as mais recentes evoluções que foram aplicadas nos motores de pesquisa comerciais.

História dos motores de pesquisa

A maior parte dos métodos de pesquisa usados pelos motores de pesquisa atuais têm origem nos desenvolvimentos efetuados nos anos 70 e 80 pela área da informática que se dedica à Recuperação de Informação (RI). A ciência da Recuperação de Informação estuda o uso das tecnologias de computadores para aquisição, organização, armazenamento, recuperação e distribuição de informação. Com o advento da WWW e do uso geral da internet, a RI é uma parte diária das nossas vidas, sempre que fazemos uma pesquisa no Google estamos a usar tecnologias de Recuperação de Informação. A Recuperação de Informação pode ser expressa como uma "equação" do tipo: recuperação = indexação + pesquisa. A indexação é uma tabulação dos conteúdos dos documentos na recolha e a pesquisa consiste em corresponder a uma consulta a essas tabelas. Por sua vez, a pesquisa pode ser representada por outra "equação" deste tipo: pesquisa = processamento da consulta + correspondência (+ pontuação). A pontuação só ocorre nos casos onde se pretende uma recuperação ordenada por classificação.

A primeira ferramenta que surgiu para pesquisar na internet foi o motor de pesquisa Archie, em 1990. Nesta data ainda não tinha sido inventada a WWW. Devido às limitações de armazenamento disponível existentes na altura, este motor de pesquisa limitava-se a indexar o nome dos ficheiros disponíveis nos servidores FTP (File Transfer Protocol) de acesso livre. Como resultado da popularidade alcançada pelo Archie, surgiu um novo protocolo em 1991 – o Ghoper – que pretendia ser uma alternativa ao Archie. Para este novo protocolo surgiram dois novos interfaces (motores de pesquisa), primeiro o Veronica e mais tarde o Jughead.

Em 1991, através de Tim Berners-Lee surge a WWW e o primeiro browser. Mas é apenas em 1993 que é lançado o Mosaic, o browser que viria a popularizar o uso da WWW.

O browser NCSA Mosaic 3.0 for Windows, 1993O browser NCSA Mosaic 3.0 for Windows, 1993

No início da WWW não existiam motores de pesquisa propriamente ditos, existiam apenas catálogos ou diretorias das páginas existentes. É apenas em 1993 que surge o primeiro motor de pesquisa da WWW, o Wanderer, que consistia num web robot desenvolvido na linguagem de programação PERL que navegava pela web existente e criava um índice das páginas encontradas. Ainda no mesmo ano surge outro motor de pesquisa, o Aliweb, que não recorria a um web robot mas sim a um sistema de notificações em que eram os administradores dos websites que informavam o motor de pesquisa que havia novo conteúdo. No final desse ano surge o JumpStation, aquele que foi o primeiro motor de pesquisa a usar as três principais funcionalidades de um motor de pesquisa moderno (rastreamento, indexação e pesquisa), embora ainda limitado na pesquisa aos títulos e cabeçalhos das páginas que indexava. É apenas em 1994 que começam a surgir motores de pesquisa que indexavam todo o conteúdo das páginas, sendo exemplo o Webcrawler, o Lycos e o Infoseek.

Em 1995 os motores de pesquisa aumentam a sua popularidade e é nesse ano que surge o Altavista que se manteria o líder até ao surgimento do Google. O Altavista é o primeiro motor de pesquisa a permitir consultas em linguagem natural. É também em 1995 que nasce o SAPO em Portugal.

Durante este período outros motores de pesquisa surgem, mas é em 1998 que surge aquele que é até ao presente o motor de pesquisa mais popular e líder em praticamente todo o mundo (Rússia e China são exceções) – o Google.

O Google em 1998O Google em 1998

O Google salta para a liderança logo em 2000 fruto da inovação conseguida através do seu algoritmo de ranking dos resultados, o PageRank. Este algoritmo avalia a importância relativa de cada página na web levando em consideração o número de hiperligações que apontam para essa página relativamente a todas as outras páginas na web, conseguindo dessa forma estabelecer uma importância relativa para cada uma das páginas. Mas não foi apenas esta inovação no campo tecnológico que fez com que o Google conseguisse a liderança deste setor, foi também a ideia de vender pequenos anúncios de texto (PPC) (Google AdWords) que apareciam juntamente com os resultados da pesquisa para palavras-chave relacionadas.

Como seria de esperar também surgiram motores de pesquisa baseados em tecnologias open source, sendo a mais popular atualmente a combinação do Apache Lucene com o Apache Solr e Apache Nutch. O Apache Lucene surge pela primeira vez em 1999 pelas mãos do seu criador Doug Cutting, passando mais tarde em 2001 a ser suportado pela fundação Apache.

Como funcionam os motores de pesquisa

O trabalho do motor de pesquisa começa muito antes de o utilizador digitar um conjunto de palavras-chave na caixa de texto e submeter essa pesquisa. Podemos mesmo afirmar que essa é a última parte de um ciclo que se repete indefinidamente. As três fases fundamentais no funcionamento de um motor de pesquisa são:

  1. Rastreamento (crawling)
  2. Indexação (indexing)
  3. Pesquisa (searching)

Rastreamento

Antes de ser possível pesquisar é necessário que o motor de pesquisa preencha o seu índice com os documentos sobre o qual efetuará a pesquisa. O motor de pesquisa delega essa tarefa de rastreamento, ou seja, encontrar na WWW os documentos que vão fazer parte do seu índice, a um software que se denomina por web crawler (também podendo ser denominado de spider ou internet bot). A este web crawler é fornecido uma lista de URLs (chamada de semente) a partir dos quais ele começa a seguir todos as hiperligações encontradas nessas páginas e nas páginas seguintes e assim sucessivamente até ter visitado e copiado todas as páginas pretendidas. Existem milhares de bots a percorrer a web constantemente, o bot do Google chama-se muito apropriadamente Googlebot. É com estas cópias das páginas que o motor de pesquisa constrói o seu índice. A dimensão da internet atual é tão grande que estes crawlers não a conseguem rastrear completamente. A internet que não está indexada pelos motores de pesquisa é designada por Web Invisível (Deep Web).

Indexação

A fase de indexação corresponde ao processo pelo qual o motor de pesquisa extrai a informação necessária desses documentos e a armazena na sua base de dados para que as pesquisas a serem efetuadas sobre esse índice sejam rápidas e precisas. Se não houvesse este processo de indexação, as pesquisas sobre o conjunto de documentos (corpus) poderia demorar horas ou mesmo dias para apenas uma consulta.

O índice tem normalmente a forma de um índice invertido. A ideia é manter um vocabulário de todos os termos encontrados nos documentos com a indicação (lista) de onde esses termos existem. Este índice é um fator chave na eficiência dos sistemas de Recuperação de Informação, dos quais os motores de pesquisa fazem parte.

Os principais passos necessários para a construção de um índice invertido são:

  • Recolha dos documentos a serem indexados.
  • Tokenização” do texto. Tarefa de separar um conjunto de carateres em palavras, ou, mais precisamente, os “tokens”. Este passo é fundamental para uma análise mais aprofundada e, sem ela, seria difícil extrair informações de alto nível a partir de qualquer tipo de documento.
  • Processamento linguístico dos tokens (termos).
  • Indexação dos documentos onde ocorre cada um dos termos.

Pesquisa

O primeiro passo na resposta a uma consulta é analisar (fazer o parsing) dessa consulta. O tipo de consultas disponíveis em sistemas de Recuperação de Informação são diversas, podemos ter consultas booleanas, consultas de proximidade, consultas wildcard e consultas com correções ortográficas automáticas, entre outras.

Depois de interpretada a consulta, o sistema de RI irá procurar todos os documentos que correspondem à palavra-chave(s) usada na consulta. Nesta fase não há ordenação (ranking) entre documentos processados, apenas se pretende identificar todos os documentos que são candidatos a pertencer à lista de resultados possíveis. Como o número de resultados pode ser na ordem das centenas ou mesmo milhares, é importante que alguma ordenação se aplique à lista dos resultados. Os resultados encontrados são assim devolvidos numa lista de resultados ordenados por ordem de relevância. A determinação da ordem da relevância obedece a um algoritmo de ranking/scoring. Um dos métodos mais populares para fazer o scoring dos documentos é o ''Term Frequency-Inverse Document Frequency'' (tf-idf), mas existem vários outros métodos, como por exemplo o Okapi BM25 ou o Latent Semantic Indexing (LSI).

Como implementar um motor de pesquisa personalizado

Os motores de pesquisa comerciais permitem algum tipo de personalização. Alguns deles até vendem versões que podem ser instalados em redes privadas de computadores. No entanto, existe uma solução completamente grátis e de código aberto que pode ser usada para desenvolver um motor de pesquisa numa rede de computadores interna ou mesmo para pesquisar toda a internet. Este sistema consiste na junção de três projetos open source, o Apache Lucene, o Apache Solr e o Apache Nutch. São três projetos distintos, que juntaram forças para fornecer uma poderosa e eficaz ferramenta de pesquisa, com todos os recursos necessários à construção de um motor de pesquisa. O Solr é um servidor de pesquisa com um interface REST API e o Lucene é um motor de pesquisa de texto sobre um índice de elevado desempenho, sendo atualmente a biblioteca em formato livre mais popular, isto devido à sua escalabilidade e performance. O Apache Nutch é o crawler que alimentará o índice do Lucene.

Apache nutch, Apache Lucene e Apache Solr

As principais funcionalidades encontradas no Lucene, além do seu índice invertido para eficiente recolha de documentos por termos indexados, são um conjunto de componentes de analisadores de texto encadeáveis entre si, que permitem adaptar o índice e o sistema de interpretação dos termos de pesquisa à linguagem pretendida e sistema de scoring completamente personalizável e adaptável.

O Solr pode ser considerado uma espécie de camada que corre sobre o Lucene que o estende com novas funcionalidades e o tornam mais flexível e o permite integrar com uma variedade de linguagens de programação e sistemas. As funcionalidades acrescentadas são nomeadamente:

  • Um esquema de dados flexível, com campos dinâmicos, chaves únicas, etc
  • Extensões para o Lucene Query Language
  • Pesquisa facetada e filtragem dinâmica
  • Pesquisa geoespacial
  • Analisadores de texto configuráveis
  • Altamente configurável e User Cache Extensible
  • Otimizações de desempenho
  • Configuração externa via XML
  • Uma interface de administração
  • Registo de eventos
  • Atualizações incrementais do índice
  • Replicação dos índices
  • Pesquisa distribuída altamente escalável com índices distribuídos por vários nós
  • JSON, XML, CSV / texto delimitado e formatos binários de atualização
  • Formas fáceis de importar dados de bases de dados e ficheiros XML a partir do disco local e fontes HTTP
  • Indexação e parsing de vários formatos de ficheiros (PDF, Word, HTML, etc) usando Apache Tika
  • Integração com o Apache UIMA para a extração de metadados configuráveis
  • Índices de pesquisa múltiplos

O índice do Lucene pode ser alimentado através de outros crawlers que não o Apache Nutch, mas existem vantagens significativas em usa-lo. Talvez a mais importante seja a de que como também é um projeto Apache a interoperabilidade com os outros sistemas Apache é maior e dessa forma temos a garantia de um motor de pesquisa mais coeso. As outras vantagens são o ser altamente escalável e com um conjunto e funcionalidade que o torna muito flexível, assim como permitir uma personalização completa do algoritmo que decide quais as páginas a rastrear.

Esta plataforma composta por três projetos open source pode ser instalada em qualquer sistema operativo capaz de correr Java.

O futuro dos motores de pesquisa

Os mais recentes avanços na tecnologia dos motores de pesquisa consistem em passar para uma nova fase, ou seja, a Recuperação de Informação (RI) é um desafio vencido, tenta-se agora conquistar um novo desafio – a Extração de Informação (EI). A EI tenta encontrar informação útil nos documentos sem que seja necessário para o utilizador ler o texto completo, podemos assim considerar o campo da Extração de Informação como um subcampo do processamento de linguagens naturais (NLP) que se foca em encontrar factos específicos em documentos relativamente não estruturados. É diferente do RI que tenta encontrar documentos contendo determinada informação.

Dentro deste campo começamos a ver serem dados os primeiros passos, como é exemplo o “Knowledge Graph” desenvolvido pela Google e que conta já na sua base de dados com mais de 570 milhões de conceitos e relações entre si. O Google já é desta forma capaz de aplicar técnicas de Reconhecimento de Entidades Mencionadas (REM) e extrair informação sobre as mesmas dos documentos indexados. O REM é o primeiro passo para identificar relações num sistema de Extração de Informação.

Reconhecimento de entidades no GoogleReconhecimento de entidades no Google

Simultaneamente os motores de pesquisa desenvolvem cada vez mais as suas capacidades de processamento de linguagem natural, como é também exemplo a mais recente atualização ao motor de pesquisa Google que denominou por Hummingbird.

Reconhecimento de entidades no GoogleConsulta comparativa no Google

Os motores de pesquisa caminham para se tornarem mais do que “simples” motores de pesquisa e passarão também a responder às perguntas feitas pelos seus utilizadores em linguagem natural. Estes sistemas – Question Answering (QA) – integram os campos científicos nas áreas de Recuperação de Informação (RI) e processamento de linguagem natural (NLP).

A evolução nesta indústria não pára, exemplo disso é este infográfico que mostra as principais inovações no motor de pesquisa Google durante os últimos 15 anos.

Evolução do Google nos últimos 15 anos

Por José Fernandes

Twitter

Facebook