Please enable JavaScript.
Coggle requires JavaScript to display documents.
Indicizzazione - Coggle Diagram
Indicizzazione
Indexing
L'input della fase di Indexing è una lista di token normalizzati per ogni documento, che può essere anche visto come una lista di coppie termine-documento.
Lo step principale di questa fase è ordinare queste coppie termine-documento, dopo si procede alla creazione del dizionario e delle posting.
Istanze dello stesso termine per lo stesso documento vengono unite, mentre per documenti diverse vengono raggruppate per termine e si ottengono le posting dai documenti
Il dizionario salva alcune statistiche come il numero di documenti che contiene ogni termine (document frequency)
-
Indice Invertito
Costruire una matrice termine-documento standard non è efficace, enorme e molto sparsa
Esempio 500K termini e 1M di documenti produce centinaia di miliardi di celle da memorizzare e se consideriamo un documento di 1000 parole non più dello 0.2% dei record sono non zero
-
-
Query Processing
Step per risolvere una query A and B in un modello Booleano
- Cerca A nel dizionario
- Ottieni la posting list di A
- Cerca B nel dizionario
- Ottieni la posting list di B
- Ottieni l'intersezione delle due posting list
Intersezione, chiamata anche merging delle posting lists è cruciale, bisogna essere efficienti per trovare rapidamente i documenti che contengono entrambi i termini.
Un modo semplice ed efficace consiste nel mantenere un puntatore in entrambe le liste e scorrere attraverso queste in tempo lineare.
Ad ogni step si comparano i due docID:
- Se è uguale, il documento viene aggiunto ai risultati
- Altrimenti avanza solo il puntatore con il docID più piccolo
O(x + y) -->O(N)
Ottimizzazione Query
Nel caso ci sono più di 2 termini nella query è più efficiente fare merge delle posting lists più piccole (così il risultato non sarà più grande della posting list più piccola) e si fa meno lavoro dopo.
A questo serve salvare la document frequency
Si può stimare (ad esempio nel caso di un OR) la dimensione del risultato semplicemente sommando le singole document frequency
-
-
-
-