Indici inversi – Introduzione

Chi si interessa di motori di ricerca ha sicuramente incontrato gli Indici Inversi (o Inverted Index per chi ama l’anglofonia).
Croce e delizia dei motori di ricerca, gli inverted index sono una organizzazione ottimizzata per recuperare tutti i contenuti (files, pagine web e tutto quello che c’è di testuale al mondo) in maniera rapida.

Cosa sono gli inverted index o indici inversi

Per spiegare cosa sono gli indici inversi dobbiamo prima fare degli assunti su come salviamo i nostri testi.
Per comodità farò riferimento alla tabella dei contenuti di wordpress, wp_post, tenendo in considerazione solo 2 campi: ID e post_content.

ID è l’identificativo univoco della pagina o del post, mentre il testo vero e proprio è salvato in post_content

Se volessi fare una ricerca per trovare i post che contengono la parola “wordpress” utilizzando l’SQL dovrei scrivere qualcosa come:

SELECT * FROM wp_post WHERE post_content like '%wordpress%';

Poi dovrei eseguire la query e aspettare i risultati.
Se ho qualche decina di post il risultato è immediato, ma se ho migliaia e migliaia di post potrei aspettare parecchi secondi se non minuti.

Questo perché il database dovrà cercare nel testo di tutti i post la parola “wordpress”, uno per uno, lettera per lettera.
Un lavoraccio.

Cambiare punto di vista

Per evitare questo lavoro certosino al database bisogna cambiare il punto di vista.
Nella nostra tabella wp_post abbiamo i dati concettualmente salvati in questo modo:

ID	post_content
1	il mio primo sito in wordpress
2	il mio primo post su wordpress
3	wordpress è un bel cms

In pratica abbiamo, in ogni riga, l’identificativo univoco del post e un elenco di parole.
E se noi invertissimo questo concetto, quindi se mettessimo in ogni riga una parola e l’elenco dei post che la contengono?
Verrebbe fuori una cosa simile a questa:

parola	post_id
il	1,2
mio	1,2
primo	1,2
sito	1
in	1
wordpress	1,2,3
è	2
un	3
bel	3
cms	3

Per cercare i post che contengono la parola “wordpress” dovrò fare una query estremamente più semplice e diretta:

SELECT post_id FROM wp_invertedindex WHERE parola='wordpress';

Il risultato è il valore “1,2” che ci indica esattamente quali sono i post che dovrò andare a prendere.

Semplice no?

E se ho 2 o più parole?

Se devo cercare 2 o più parole la query cambia, ma non perde di efficacia, vediamo come diventa se volessi cercare “il mio wordpress”:

SELECT post_id FROM wp_invertedindex WHERE parola IN ('il','mio','wordpress');

Il risultato è di 3 righe con i valori “1,2”, “1,2” e “1,2,3”.
Non mi resta che prendere questi valori e organizzarli, per esempio in array:

risultato['il']=[1,2];
risultato['mio']=[1,2];
risultato['wordpress']=[1,2,3];

In pratica abbiamo 3 insiemi di numeri interi, a questo punto posso eseguire su questi tutte le operazioni sugli insiemi che voglio.
Se voglio tutti i post che contengono tutte e tre le parole mi basterà fare l’intersezione dei 3 insiemi:

[1,2] ∩ [1,2] ∩ [1,2,3] = [1,2]

Se invece voglio tutti i post che contengono almeno una delle parole cercate farò l’unione tra i 3 insiemi:

[1,2] ∪ [1,2] ∪ [1,2,3]=[1,2,3]

Con un po’ di sforzo posso anche ordinarli in modo che i post che contengono il numero più alto di parole cercate appaiano per primi, basterà contare gli id dei post.
Il post 1 appare 3 volte, il post 2 appare 3 volte, il post 3 appare una volta.
Anche qui basta un dizionario o un array_associativo, dove la chiave è l’id del post e il valore il numero delle occorrenze:

for (parola,ids) in risultato{
   for id in ids{
        risultatoPesato[id]++;
   }
}

print reverse(sort(risultatoPesato))

Dovremmo avere qualcosa come questa:

risultatoPesato[1]=3
risultatoPesato[2]=3
risultatoPesato[3]=1

Et voilà, il gioco è fatto.

Crea il tuo indice inverso

Se volete divertirvi vi lascio gli statement SQL per creare e giocare con gli indici inversi su MySQL.
Attenzione alle dimensioni dei campi, e ricordatevi di togliere spazi e tutti i caratteri che non sono lettere o numeri.
Ricordatevi sempre che nei database vale la regola aurea: “garbarge IN, garbage OUT”

CREATE TABLE invertedindex (
word varchar(32) NOT NULL,
post_id longblob NOT NULL,
PRIMARY KEY (word)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

INSERT INTO invertedindex VALUES ('il','1,2'), ('mio','1,2'),('primo','1,2'),('sito','1'),('in','1'),('wordpress','1,2,3'),('é','3'),('un','3'),('bel','3'),('cms','3');

SELECT * FROM invertedindex WHERE word='wordpress';

Occhio alla dimensione del campo word, 32 caratteri possono bastare, a meno che non dobbiate lavorare con nomi scientifici, come la proteina Titina ad esempio, che ha un nome lungo 189.819 caratteri.
Ovviamente c’è una soluzione anche a questi problemi, ve ne parlerò in futuro.

PS: tranne l’SQL il resto è pseudo codice, traducetelo nel linguaggio che più vi piace.