IR - 02 - Inverted-Index II

Volendo utilizzare un approccio brute force, l'idea è quella di indicizzare tutti i bigrammi (biwords), ovvero tutte le coppie di parole adiacienti presenti nel testo. Ad esempio, un testo del tipo

\[\text{Friends, Romans, Countrymen}\]

andrebbe a generare i seguenti bigrammi:

\[\{\text{Friends Romans}\}, \{\text{Romans Countrymen}\}\]

Utilizzando questo approccio il processamento di query con due parole sarebbe immediato. Le query che contengono più di due parole possono invece essere spezzate in query più piccole, ciascuna di due parole, messe in AND tra loro.

Le problematiche di questo approccio sono:

• Presenza di falsi positivi: Notiamo che così facendo le query possono ritornare dei falsi positivi quando cerchiamo sequenze di più di due parole, in quanto anche se magari troviamo i bigrammi \(\{\text{Friends Romans}\}, \{\text{Romans Countrymen}\}\), non è necessariamente detto che nel testo le tre parole appaiono consecutivamente.

• Problemi di memorizzazione: L'indice diventa molto grande, specialmente se andiamo ad indicizzare trigrammi di parole, o in generale \(n\) -grammi di parole.

Negli approcci moderni quindi, questo approccio di indicizzare coppie o triple o \(n\) -uple di parole non viene utilizzato da solo, ma viene inserito all'interno di soluzioni generali più standard.

Un'altra possibile soluzione è quella di memorizzare la posizione di ogni termine all'interno di ogni documento, andando quindi non a modificare la parte del dizionario, ma la parte delle posting lists.

Per implementare questa soluzione la struttura dati deve infatti cambiare nel seguente modo: al posto di avere che ogni termine punta ad una posting list di \(\text{docIDs}\), questa volta abbiamo che per ogni \(\text{docID}\) nella posting list associata al termine abbiamo anche la lista delle posizioni in cui quel termine appare in quel documento. Graficamente quindi abbiamo, per ogni termine, la seguene struttura

\[\begin{split} (\text{term}, \text{doc_frequency}) \longrightarrow& \,\, [\,\, \text{docID}_1: \text{pos}_1, \text{pos}_2, \ldots \text{pos}_{m_1}, \\ &\,\,\,\,\,\, \text{docID}_2: \text{pos}_1, \text{pos}_2, \ldots \text{pos}_{m_2}, \\ &\,\,\,\,\,\, \text{docID}_3: \text{pos}_1, \text{pos}_2, \ldots \text{pos}_{m_3}, \\ &\,\,\,\,\,\, \text{docID}_4: \text{pos}_1, \text{pos}_2, \ldots \text{pos}_{m_4}, \\ &\,\,\,\,\,\,\,\,\,\,\,\, \vdots \\ &\,\,\,\,\,\, \text{docID}_k: \text{pos}_1, \text{pos}_2, \ldots \text{pos}_{m_k}] \\ \end{split}\]

Il processamento delle query utilizzando questa struttura dati avviene quindi nel seguente modo:

• Prendo le posting lists dei vari termini nella query e mi trovo tutti i documenti in cui appaiono i vari termini utilizzando la solita merge() operation;

• Per ogni documento calcolato prima, verifico se in questo documento i termini appaiono nell'ordine corretto. In particolare quindi, se sto cercando \(\text{Tor Vergata}\), dovrò controllare che ci sia almeno una occorrenza di \(\text{Tor}\), la cui posizione è adiaciente ad una occorrenza di \(\text{Vergata}\).

Notiamo che con questa struttura aggiunta si è in grado di rispondere anche a query con richieste di prossimità, ovvero query del tipo

\[\text{Tor /3 Vergata}\]

dove quel \(\text{/3}\) sta per "within 3 words of", e indica il fatto che vogliamo tutti i documenti che contengono le parole \(\text{Tor}\) e \(\text{Vergata}\) che si trovano distanti tra loro di al massimo \(3\) parole.

Il seguente codice scritto in python implementa query del genere, in cui \(k\) è la distanza entro la quale le due parole si devono trovare per essere riportate. Il codice è ripreso dal capitolo \(2\) del libro del corso.

def positional_intersect(p1, p2, k):
    answer = []
    while p1 and p2:
        if p1.docID < p2.docID:
            p1 = p1.nextDoc
        elif p2.docID < p1.docID:
            p2 = p2.nextDoc
        else:
            pp1 = p1.positions
            pp2 = p2.positions
            while pp1:
                l = []
                while pp2:
                    if abs(pp1.pos - pp2.pos) <= k:
                        l.append(pp2.pos)
                    elif pp2.pos > pp1.pos:
                        break
                    pp2 = pp2.nextPos
                for pos in l:
                    answer.append([p1.docID, pp1.pos, pos])
                pp1 = pp1.nextPos
            p1 = p1.nextDoc
            p2 = p2.nextDoc
    return answer

I due schemi descritti in precedenza, i biword indexes e i positional indexes, possono essere combinati tra loro per definire degli schemi ibridi che utilizzano entrambi gli approcci. Ad esempio, per le espressioni terminologicamente significative, come \(\text{San Diego}\), è opportuno mantenere la loro forma composta, e non risulta necessario mantenere la loro positional posting list.

Uno schema di indicizzazione ancora più complesso è quello di costruire un indice extra per cercare di rispondere alle query più richieste dagli utenti. Questo approccio ovviamente aumenta la memoria utilizzata, ma permette di dare delle risposte in modo più efficiente.

Notiamo poi che anche se le stop-words hanno principalmente un ruolo grammaticale,non portano significato alla frase, occupano un sacco di spazio, e quindi tendenzialmente è meglio rimuoverle dall'indice, per gestire i termini composti che contengono stop-words, come \(\text{The Who}\) l'idea è quella di memorizzare il termine come se fosse un singolo token.

Avendo la possibilità di fare pos-tagging, una tecnica ripresa dall'NLP, possiamo dividere ogni parola in nomi (\(\text{N}\)), o articoli, proposizioni, e in generale function words (\(\text{X}\)). A questo punto possiamo buttare le function words e tenere solo i nomi.

Le stringhe della forma \(\text{NX*N}\) sono dette delle extended biwords, e vengono memorizzate nell'indice utilizzando solo i nomi \(\text{NN}\). Così facendo otteniamo ad esempio la seguente trasformazione

\[\text{lenti a contatto} \longrightarrow \text{lenti contatto}\]

Effettuando lo stesso processamento sulla query siamo in grado di rispondere alle query in modo abbastanza corretto.

Infine un ulteriore approccio che possiamo utilizzare è quello statistico. Una possibile idea potrebbe infatti essere quella di calcolare la frequenza di due parole in isolamento, e la frequenza di quando stanno assieme: se la frequenza di quando stanno assieme è più alta di quando sono separate, allora potrei pensare di considerare le due parole come parte di una compound form.

Per mostrare qualche esempio concreto, consideriamo la collezione di articoli di Reuters, una testata giornalistica abbastanza famosa. Le statistiche più importanti del dataset sono le seguenti

• Totale documenti \(= N = 800.000\)

• Numero medio di token per documento \(= L = 200\)

• Numero termini distinti \(= M = 400.000\)

• Numero medio byte per token con spazi/punteggiatura \(= 6\)

• Numero medio byte per token senza spazi/punteggiatura \(= 4.5\)

• Numero medio byte per termine \(= 7.5\)

• Non positional postings \(= 100.000.000\)

Il dispositivo di memorizzazione utilizzato per salvare in modo persistente le nostre strutture dati è l'hard disk. L'SSD invece, per quanto veloce possa essere, ha una obsolescenza programmata, che dipende dal numero di scritture medio, e dunque non soddisfa i nostri requisiti di persistenza.

Dato che l'hard disk è un dispositivo diviso in blocchi, e dato che per leggere un blocco l'hard disk deve spostare una testina fisica nel particolare settore in cui il blocco è situato, l'accesso ai dati sul disco è significativamente più lento dell'accesso dei dati in memoria. In particolare una delle misure più importanti per capire le performance degli hard disk è il desk seek, ovvero il tempo necessario per spostare la testina nel settore del disco in cui dobbiamo scrivere e/o leggere. L'idea è quindi quella di minimizzare il numero di letture e scritture che effettuiamo sul disco, cercando di utilizzare la memoria principale nel modo migliore possibile.

Per terminare la lezione, riportiamo due algoritmi, il cui obiettivo è proprio la creazione di un indice inverso nel modo più efficiente possibile.

Il Blocked Sort-Based Indexing (BSBI) è un metodo utilizzato per costruire un indice inverso non posizionale, e si basa sull'idea di spezzare il dataset in vari blocchi.

Per rendere la costruzione più efficiente i termini del dizionario verranno rappresentati da interi chiamati \(\text{termIDs}\) anziché da stringhe. Il mapping \(\text{term} \longrightarrow \text{termID}\) può essere costruito on the fly durante il processamento della collezione.

I passi eseguiti dal BSBI sono i seguenti:

1. Si dividono le coppie \(\text{(termID, docID)}\) in vari blocchi, ciascuno con la stessa grandezza.

2. Si effettua il sorting delle coppie in ogni blocco direttamente in memoria, creando degli indici inversi parziali.

3. Si salvano sul disco questi indici inversi parziali come risultati intermedi.

4. Una volta che tutti i documenti sono stati processati, si effettua il merge di questi indici parziali per ottenere l'indice inverso finale.

L'algoritmo può essere descritto dal seguente pseudocodice

BSBIndexConstruction()
  n <- 0
  while (all documents have not been processed)
    do n <- n + 1
    block <- ParseNextBlock()
    BSBI-Invert(block)
    WriteBlockToDisk(block, fn)
  f_merged <- MergeBlocks(f1, f2, ..., fn)
  return f_merged

Notiamo che la grandezza del blocco deve essere tale da permettere una memorizzazione in memoria fisica (RAM) del blocco senza troppi problemi, ottenendo così un sorting in-memory performante.

Per fare l'ultimo passo di merge, è possibile effettuare dei binary merges, come mostrato nella figura

Un altro modo per fare quest'ultimo passo di merge in modo molto efficiente è il seguente: Supponiamo di avere due blocchi, \(B_1\) e \(B_2\). Scorro linearmente parola per parola i due blocchi, e quando trovo la stessa parola in entrambi i blocchi, posso semplicemente appendere la posting list della parola in un blocco alla posting list dell'altro blocco, a seconda di come ho diviso i documenti nei vari blocchi. Notiamo che questo metodo funziona solo quando abbiamo partizionato bene i documenti nei vari blocchi. Così facendo il costo del merging diventa lineare, e riusciamo anche a ottimizzare la posizione dei dati nel disco fisico.

La complessità di questo metodo è \(\Theta(T \cdot \log T)\), dove \(T\) è un upper bound per il numero di oggetti che dobbiamo ordinare, ovvero per le coppie \(\text{(termID, docID)}\) presenti nel dataset. Detto questo, il tempo di costruzione utilizzando il BSBI è tipicamente dominato dal tempo richiesto per parsare i documenti tramite la funzione ParseNextBlock() e per fare il final merge tramite la funzione MergeBlocks().

Anche se il BSBI è molto scalabile, questo metodo necessita di tenere nella memoria fisica una la struttura dati utilizzata per memorizzare il mapping \(\text{term} \longrightarrow \text{termID}\). Per collezioni molto grandi, questa struttura dati, simile in un certo senso ad un dizionario, potrebbe non entrare tutta quanta nella memoria. Necessitiamo dunque di soluzioni ancora più scalabili.

Un altro metodo per la costruzione di un indice inverso è il Single-Pass In-Memory Indexing (SPIMI). L'idea di questo metodo è di processare la collezione token per token, continuando a costruire l'indice fino a quando non si satura completamente la memoria fisica. Una volta che non c'è più memoria si scrive l'indice parziale ottenuto sul disco, e si procede nuovamente con il token successivo.

L'algoritmo procede quindi nel seguente modo

1. Vengono generati dei dizionari per ciascun blocco. Un dizionario generalmente è rappresentato da una hash table.

2. Non si eseguono sort, ma si accumulano i postings nelle postings list ogni volta che vengono trovati nel processamento.

L'algoritmo può essere descritto dal seguente pseudocodice. L'idea è quella di chiamare la funzione SPIMI-Invert sul token stream fino a quando l'intera collezione non è stata processata.

SPIMI-Invert(token_stream)
  output_file = NewFile()
  dictionary  = NewHash()

  while (free memory available)
    do token <- next(token_stream)
    if term(token) not in dictionary
      postings_list = AddToDictionary(dictionary, term(token))
    else
      postings_list = GetPostingsList(dictionary, term(token))

    if full(postings_list)
      postings_list = DoublePostingsList(dictionary, term(token))

    AddToPostingsList(postings_list, docID(token))

  sorted_terms <- SortTerms(dictionary)
  WriteBlockToDisk(sorted_terms, dictionary, output_file)
  return output_file

Una differenza fondamentale tra SPIMI e BSBI è che SPIMI aggiunge direttamente il posting alla propria postings list, che è una lista dinamica che cresce con l'aumentare dei postings.

Quando la memoria viene completamente esaurita, scriviamo l'indice del blocco (che è formato da un dizionario e da delle postings lists). Notiamo che prima di fare questo step dobbiamo effettuare il sorting dei termini, in modo che il final merge può essere fatto in modo efficiente.

Il merge finale viene fatto in modo analogo al merge effettuato nel BSBI.

La complessità del SPIMI è \(\Theta(T)\), in quanto non dobbiamo effettuare il sorting dei tokens, e tutte le operazioni sono al più lineari rispetto al size della collezione.

In ultima analisi, l'utilizzo di SPIMI rispetto a BSBI porta ai seguenti vantaggi:

• L'algoritmo in generale è più veloce, in quanto non c'è bisogno di effettuare dei sorting.

• L'algoritmo è anche più efficiente in termine di memoria, in quanto per ogni posting lists sappiamo a quale termine fa riferimento, e dunque non dobbiamo memorizzare più volte lo stesso \(\text{termID}\).

• È possibile utilizzare la compressione sul dizionario e sulle postings lists per salvare ulteriormente spazio quando si memorizza l'indice sul disco.