Inverted index

Inverted index

Meccanismo di indicizzazione di collezioni di testi word-oriented, per velocizzare la ricerca. Composto da due elementi:

• vocabolario
• occorrenze (posting list)

Per ogni termine $t$, viene generata una lista contenente tutti i documenti che lo contengono. I documenti sono identificati da un serial number.

flowchart LR
	A[Brutus] ==> B["1|2|4|11|31|45|173|174"]
	C[Caesar] ==> D["1|2|4|5|6|16|57|132"]
	E[Calpurnia] ==> F["2|31|54|101"]

Posting list

Per ogni termine, viene generata una lista di occorrenze:

• Document-based: lista di documenti con la corrispondente term frequency
• Word-based: lista di documenti con il corrispondente posizionamento dei termini

Document based

flowchart LR
	A["Brutus|3"] ==> B["D7, 4|B9, 3|S2, 1"]
	C["Caesar|2"] ==> D["F3, 2|A2, 2"]
	E["Calpurnia|1"] ==> F["A2, 1"]

Dove la parte sinistra è composta dal termine indicizzato, e la document frequency, $df$. La posting list, invece, è composta dall’id del documento e dalla term frequency di quel termine in quel documento.

Word-based

flowchart LR
	A["Brutus|3"] ==> B["D7, 50, 90, 120, 221|B9, 34|S2, 23, 32"]
	C["Caesar|2"] ==> D["F3, 122, 345, 654|A2, 44, 65"]
	E["Calpurnia|1"] ==> F["A2, 1"]

Nella parte sinistra, come per la document based, troviamo il termine indicizzato e la sua document frequency. La posting list, invece, è composta dall’id del documento e dalla lista delle posizioni in cui si trova il termine nel documento.

• D7: id documento
• 50, 90, 120, 221: posizione del termine nel documento. $w{p}_i$. Favorisce la ricerca.

Spazio richiesto

Lo spazio richiesto per un vocabolario è piuttosto piccolo. Dalla legge di Heap, si ha che il vocabolario cresce con $O(n^b)$, con $b\in [0,1]$, solitamente $[0.4,0.6]$. Tutto il resto dello spazio è occupato dalle posting list word-based, che pesano O(n) ed è circa il 40% della dimensione del testo se si eliminano le stopwords, l’80% se si tengono. Posting list document based sono più leggere e occupano dal 20% al 40% delle dimensioni del testo.