Gli algoritmi di indicizzazione dei motori di ricerca

Nascondi

Quella che segue è una trascrizione automatica dell'episodio.

Salve a tutti e bentrovati per un nuovo episodio di Pensieri in Codice. Prima di iniziare vi ricordo rapidamente che in descrizione trovate tutti i link inerenti al progetto, sia per sostenerlo sia per partecipare unendovi al canale e al gruppo telegram che ormai conta più di una sessantina di iscritti. Vi ricordo inoltre che per tutto il mese di aprile potete, se vi va, prenotare delle lezioni private gratuite sulla piattaforma Docety, quindi se avete bisogno di ripassare qualcosa di informatica o di programmazione mi trovate lì, come al solito link in descrizione. Tutti sappiamo cosa sia un motore di ricerca, tutti nella vita ne abbiamo utilizzato almeno uno che si chiama Google e molti magari ne hanno utilizzati anche altri. Alcuni funzionano meglio, altri hanno funzioni speciali, altri prediligono particolari aspetti come il rispetto della privacy o della protezione dell’ambiente, tutti però sono in grado di restituire in pochi centesimi di secondo la lista di pagine web relative alle parole che abbiamo digitato scavando in archivi di miliardi di documenti. E come possono fare una cosa del genere? Di certo non possiamo pensare che basti solo avere centinaia di server potentissimi sparsi per il mondo per essere in grado di verificare in un batter d’occhio se una parola è presente o meno in un’immensa lista di pagine web. E per immensa intendo proprio immensa. Vi lascio in descrizione un link per avere un’idea delle attuali dimensioni del web, escludendo ovviamente il deep e il dark web. Al momento in cui sto registrando Google indicizza qualcosa come 65 miliardi di pagine. Com’è possibile dunque anche avendo una potenza di calcolo sconfinata cercare una parola in tutti questi documenti in così poco tempo? E’ ovvio che qualsiasi sia il motore di ricerca di cui stiamo parlando è necessario che esso possa contare su un algoritmo che riduca enormemente il carico di lavoro necessario. Questo algoritmo è appunto quello che viene comunemente chiamato algoritmo di indicizzazione. In effetti però qui la parola indicizzazione viene utilizzata per semplicità ma in realtà essa nasconde due concetti ben distinti che sono l’indicizzazione appunto e la classificazione. La prima ci permette di individuare la lista di documenti che contengono una o più parole e la seconda ci permette di ordinare questa lista posizionando per primi i risultati più attinenti alla nostra ricerca. Cerchiamo però di non correre troppo e proviamo ad affrontare un po’ di questioni partendo dalla più semplice per proseguire poi via via verso quelle più complesse. Alla base del funzionamento di un qualsiasi motore di ricerca ci sono quindi due concetti chiave e noi li analizzeremo separatamente in modo da provare a capire al meglio come funziona l’algoritmo che li racchiude entrambi. Iniziamo quindi con il chiederci come funziona l’indicizzazione e in effetti dalla parola possiamo già intuire che il segreto è tutto nell’utilizzo di un indice. Esattamente come l’indice analitico di un libro infatti ogni motore di ricerca costruisce e mantiene aggiornato un enorme elenco nel quale tiene traccia delle parole presenti nelle pagine web. Semplificando all’osso possiamo immaginare che questo indice proprio come quello che troviamo in fondo ad un libro sia composto da un elenco ordinato alfabeticamente di parole ciascuna delle quali è seguita dal numero di ciascuna pagina in cui la parola è presente. Ovviamente rispetto ad un libro per un motore di ricerca la lista sarà enormemente lunga e i numeri di pagina saranno in realtà degli identificativi con i quali è possibile riconoscere la pagina web ma per noi come al solito è il concetto quello che conta. Con una soluzione del genere quando noi inseriamo una parola nel campo di ricerca il motore non deve cercarla in tutti i documenti dell’archivio ma solo nell’indice che ha preparato precedentemente e questo rappresenta un’operazione particolarmente semplice perché trovare un elemento in un elenco ordinato alfabeticamente è una di quelle cose che i calcolatori sanno fare benissimo. Sfruttando quindi un’idea piuttosto comune si risolve brillantemente il problema di cercare una parola in una sconfinata mole di documenti e per estensione potremmo anche pensare di usare la stessa tecnica per cercarne due di parole o anche tre o quattro eccetera. Con il nostro indice se proviamo a cercare due parole ad esempio un motore di ricerca può rapidamente trovare la lista delle pagine che contengono la prima parola e altrettanto rapidamente la lista di quelle che contengono la seconda parola e restituirci solo le pagine che si trovano in entrambe le liste e lo stesso potrebbe valere se cercassimo tre parole o quattro e così via. In tutto questo processo però c’è solo un piccolo problema. Il risultato che otteniamo in questo modo non ha un gran valore per chi sta effettuando la ricerca. Se ci riflettiamo un attimo infatti ci accorgiamo che il solo fatto che due parole si trovino nello stesso testo non è automaticamente sufficiente ad affermare che quel testo soddisfi la ricerca di quelle due parole. Cosa voglio dire? Pensiamo ad esempio a come siamo soliti usare un motore di ricerca. Se scriviamo due parole ci aspettiamo che i risultati presentino quelle due parole vicine o almeno nella stessa frase. In generale è più probabile che un testo che contiene le due parole vicine sia più interessante per noi rispetto ad uno che contiene quelle stesse due parole ma in due paragrafi differenti. In pratica quando noi mettiamo due o più parole in un motore di ricerca stiamo implicitamente richiedendo non semplicemente di ottenere le pagine che contengono quelle due parole quanto piuttosto vogliamo le pagine che hanno quelle due parole il più vicine possibile. Nel momento in cui ci rendiamo conto che non tutte le pagine che contengono le parole che cerchiamo hanno lo stesso valore ai fini di un buon risultato di ricerca fa il suo ingresso il secondo concetto a cui abbiamo accennato prima e cioè la classificazione. All’interno della lista dei documenti che un motore di ricerca è in grado di restituire gli elementi vengono inseriti in un All’interno della lista dei documenti che un motore di ricerca è in grado di restituire gli elementi vengono fondamentalmente ordinati posizionando in testa quello che sembra il più pertinente come secondo quello un po’ meno pertinente e così via. Ora capiamoci nella realtà la classificazione dei risultati non si basa unicamente sulla distanza tra due parole ma su moltissime variabili che per forza di cose non possiamo analizzare in un podcast di un quarto d’ora. Oltre a ciò gli algoritmi di classificazione sono spesso complessi e differiscono da motore a motore. Il famoso algoritmo PageRank ad esempio ha moltissime regole che contribuiscono al posizionamento di ogni singolo risultato e ciò ha permesso a google di sovrastare letteralmente tutti i suoi concorrenti nel corso degli anni. Noi però come al solito siamo interessati a capire come funzionano le cose e quindi prendiamo in considerazione gli aspetti base della classificazione dei risultati e cioè la distanza tra le parole e il loro peso all’interno del testo. Come abbiamo già accennato qualche minuto fa minore è la distanza fra le parole cercate maggiore è da considerare il valore della pagina che esse identificano. Quindi ci serve un meccanismo per valutare questa distanza che sia al tempo stesso preciso e permetta di effettuare i calcoli in pochi istanti. La soluzione a questo problema in realtà è più semplice di quanto possa sembrare. Ci basta potenziare il nostro indice, quello che utilizziamo per trovare le pagine che contengono le parole cercate, aggiungendovi un’ulteriore informazione e cioè la posizione della parola nel testo. Con questa modifica il nostro indice è diventato una lista di parole in ordine alfabetico per ciascuna delle quali è indicato in quali pagine si trovano e per ciascuna pagina in quali posizioni la parola compare. Mi rendo conto che può sembrare un concetto un po’ complicato ma in realtà non lo è. In pratica volendo fare un esempio prendete un qualsiasi libro con indice analitico, leggete la prima parola dell’indice, trovatela nelle pagine indicate e contate dopo quante parole dall’inizio della pagina essa compare. Ora aggiungete questo numero all’indice dopo il numero di pagina. Se lo fate per tutte le parole vi troverete con un indice che contiene informazioni di questo tipo. La parola codice compare nella pagina 10 come ventitresima parola, nella pagina 60 come diciottesima parola, nella pagina 200 come quarantesima. La parola pensieri invece compare nella pagina 10 come venticinquesima parola e nella pagina 50 come ottava e trentesima e così via fino ad ottenere l’indice di tutte le parole del libro con la pagina e la posizione in cui compaiono. Il nostro motore di ricerca con un indice del genere diventa in grado di individuare le pagine che contengono tutte le parole cercate e anche di classificarle calcolando le differenze tra i numeri di posizione. Minore sarà il risultato di questa operazione di sottrazione e maggiore sarà la vicinanza tra le due parole e quindi maggiore sarà il valore della pagina ai fini della nostra ricerca. Abbiamo dunque capito come creare un meccanismo veloce per cercare tra l’immensa quantità di documenti presenti nel web e abbiamo anche scogitato un modo per dare una risposta più efficace alle ricerche di più parole contemporaneamente. Ora però come ultimo sforzo ci resta da chiederci se pensiamo che tutte le parole di un testo abbiano lo stesso valore. La risposta a questa domanda è ovviamente no. Se ad esempio cerchiamo la frase pensieri in codice e abbiamo una pagina web in cui le parole pensieri e codice compaiono nel titolo beh questa sarà probabilmente più attinente alla nostra ricerca rispetto ad una pagina in cui queste stesse parole appaiono ad esempio in un elenco puntato. Se vogliamo quindi che il nostro motore di ricerca produca dei risultati migliori ci tocca trovare un modo di valutare questo diverso peso fra le varie parti del testo. Per ottenere ciò come prima cosa serve un meccanismo per individuare le varie parti di una pagina web titolo, paragrafi, sezioni, liste, parole evidenziate eccetera. Ma guarda caso questo lavoro di valorizzazione dei testi è proprio l’obiettivo primario del linguaggio html, cioè quel linguaggio che compone praticamente ogni pagina web. L’html è infatti un linguaggio di markup, ne abbiamo già parlato in altri episodi, e ci permette di dare uno specifico valore alle varie parti del testo utilizzando delle parole chiave che prendono il nome di tag. Il titolo di una pagina web ad esempio sarà racchiusa tra due parole speciali che aprono e chiudono il tag title e la stessa cosa varrà per i sottotitoli, i paragrafi, le didascalie e tutti gli altri elementi del testo. Questo vuol dire che ogni pagina contiene già le informazioni di cui abbiamo bisogno per effettuare la nostra classificazione. Ci occorre solo un meccanismo che sia efficace e veloce nel consultarle e che non ci costringa a ricontrollare ogni pagina per capire se la parola individuata si trova nel titolo o in un paragrafo o in una nota. Ancora una volta la soluzione è nel nostro fedele indice e non ci richiede nemmeno di modificarlo, ci basta semplicemente indicizzare anche le parole speciali che derimitano i tag html. In questo modo possiamo usare l’indice per sapere anche la posizione dei tag all’interno della pagina e molto facilmente quando valutiamo il peso di una parola possiamo capire se si trova in mezzo tra la parola chiave che apre un tag e quella che lo chiude. Fatto questo quando effettuiamo una ricerca non ci resta altro che assegnare un valore alle pagine risultanti in base alla vicinanza delle parole trovate e alla loro posizione nel testo e il gioco è fatto. La pagina col punteggio maggiore sarà la prima, quella con il secondo punteggio sarà la seconda e così via. Mi rendo conto che parlare in modo astratto di questi concetti possa risultare un po’ complicato e nel caso vogliate approfondire vi metto in descrizione il link affiliato a amazon del libro 9 algoritmi che hanno cambiato il futuro dal quale ho preso l’idea per questo e per altri episodi del podcast. Detto questo vi ringrazio per aver ascoltato, vi saluto e vi ricordo che il programmatore risolve problemi, a volte anche usando il computer.

Nascondi