Bé, tal vegada no ens ho troba tot, però segurament estareu d’acord amb mi en que, des de fa uns anys, Google ens ajuda força, no?

Us heu preguntat algun cop com és que Google ens troba el que cerquem, i a més ens ho troba ràpid?

No és pas perquè tingui grans ordinadors als seus centres de dades. De fet, i en contra d’algunes noticies que han aparegut darrerament, Google gasta molt poca energia en cada una de les cerques que fem. Una d’aquestes cerques necessita unes tres deumil·lèsimes de kilowatt hora.

En informàtica, com en d’altres camps, la força bruta per si sola, el hardware, no és suficient. Cal pensar i trobar maneres de resoldre els problemes amb menys esforç. Ja diuen que “val més enginy que força”. Google ens ho troba tot (o quasi tot) gràcies als seus algorismes de cerca. Els algorismes són receptes, són conjunts ben definits d’instruccions que permeten resoldre problemes mitjançant passos succesius que no han de generar dubtes a qui els ha de realitzar (sigui una persona o una màquina). Un mateix problema el podem resoldre, en un mateix ordinador, amb diferents algorismes. Alguns seran ràpids, d’altres no tant. Els algorismes de Google són altament sofisticats. Molts d’ells es guarden en secret, com els secrets que guarden alguns pastissers i artesans. Els algorismes són el “cervell” dels nostres ordinadors. Així com les abelles “saben” construir cel·les hexagonals en els seus ruscs, els ordinadors de Google “saben” fer cerques de manera ràpida i eficient. L’evolució ha programat el cervell de les abelles, però nosaltres som els que hem de programar els algorismes dels nostres ordinadors.

Per a poder ser eficients en una cerca, cal haver ordenat la informació. Això és el que sempre hem fet, en els diccionaris. Imaginem un cas molt senzill, i suposem que tenim un diccionari (no electrònic, sinó en paper!) només amb setze fulls. Quan volem cercar una paraula, l’obrim pel mig. Ens poden passar dues coses. O bé trobem la paraula just a les pàgines per les que hem obert el diccionari, o no. En el primer cas, fem la consulta i ja hem acabat. Quan no trobem la paraula, és quan fem servir la propietat que el diccionari està ordenat: immediatament sabem si l’hem de cercar a la meitat de l’esquerra, o a les pàgines de la meitat de la dreta. Repetim el procés i tornem a obrir pel mig, però només amb el trosset de vuit fulls on sabem que podem trobar la paraula. És fàcil veure que la tercera vegada farem la cerca en quatre fulls, i que al final trobarem la paraula havent obert no més de cinc vegades el diccionari. Aquest esquema de cerca és el que ens porta als algorismes de cerca dicotòmica i als arbres binaris de cerca que actualment utilitzem en els nostres ordinadors. Aquests algorismes tenen complexitat logarítmica: cada cop que dupliquem el volum de les nostres dades, només hem de fer un pas més de cerca. De la mateixa manera que ens cal un màxim de cinc passos per trobar paraules en un diccionari de setze pàgines, ens caldran sis passos per un diccionari de 32 pàgines. Tot és degut a que, en cada pas, descartem la meitat del diccionari. Repetint el raonament diverses vegades en sentit ascendent, veureu que cal un màxim de 11 passos en un diccionari de 1024 pàgines, o un màxim de 33 passos en un diccionari de 4294 milions de pàgines.  I podeu continuar, afegint un pas cada cop que dobleu la mida del diccionari.

No és sorprenent? Si tenim la informació ben ordenada, podrem localitzar qualsevol informació en un diccionari amb 17 mil milions de termes, només amb un màxim de 35 passos. És com trobar agulles en pallers. El secret està en l’ordenació. Recordeu les guies telefòniques? Algunes estaven ordenades alfabèticament, d’altres per adreces. Eren molt útils, però no permetien trobar persones a partir del seu número de telèfon, perquè no estaven ordenades per telèfons.

Els algorismes dels cercadors com Google treballen en diverses fases. Els seus servidors construeixen i mantenen actualitzats els fitxers d’índexs, els ordenen, fan les cerques que els demanem i finalment reuneixen i organitzen la informació i ens la presenten. La construcció, manteniment i ordenació dels fitxers d’índexs és una feina que es va fent contínuament, tant si la gent demana cerques com si no. Aquests algorismes preparen i entrenen els cercadors. És com els esportistes: s’han de preparar bé, per poder després ser eficients en el moment de la cursa dels cent metres. Per a la creació i actualització dels fitxers d’índexs, els ordinadors analitzen periòdicament totes les pàgines web del món i “les inverteixen”. A cada pàgina web se li assigna un nombre, un codi. I els fitxers d’índexs no són més que diccionaris: per a cada paraula trobada en alguna pàgina, es crea una nova entrada al diccionari que conté (enlloc de la seva definició) la llista de tots els codis de pàgines on s’ha trobat aquesta paraula. Un cop ordenats, els fitxers d’índexs, immensos, estan ja preparats per acceptar cerques i peticions de tots nosaltres (aquests diccionaris són tan grans perquè han d’incloure paraules de molts idiomes i fins i tot informacions numèriques com telèfons i codis postals). Saber ordenar és essencial, en informàtica. Per això els anomenem ordinadors, a les màquines que executen els nostres algorismes…

Després, quan volem fer una cerca, no cal pas gaire potència de càlcul. Tal com ja hem vist, podem cercar en fitxers d’índexs ordenats i, donada una paraula, podem trobar la llista de pàgines web que la contenen, en molts pocs passos. Un cop feta la cerca cal, però, resumir la informació i organitzar-la per a la seva presentació final a l’usuari. Quan la cerca la fem tot indicant diverses paraules, cal intersecar les llistes parcials de pàgines i trobar el conjunt de pàgines que contenen totes les nostres paraules. I finalment, si el resultat són uns quants milers de pàgines, cal prioritzar i decidir quines són les pàgines que mostrarem en primer lloc i a dalt de tot. Alguns aspectes d’aquests algorismes de priorització són  secrets ben guardats, a Google.

Google és el resultat de la tesi doctoral de Larry Page i Sergey Brin, l’any 1998 a Stanford. Aquí teniu l’article que van escriure, el mateix any 1998, descrivint els seus algorismes. Un cop més, veiem la importància que pot tenir la investigació en la creació de noves empreses exitoses.

La paraula algorisme prové de Al-Jwārizm, matemàtic persa que va estudiar i treballar a Bagdad a principis del segle IX. A la seva obra “Algoritmi de numero Indorum” (que només coneixem per una versió llatina del segle XII) descriu el sistema indi de numeració posicional en base 10, utilitza el cero com a indicador posicional i proposa diferents algorismes de càlcul aritmètic.