Gli Inverted File per l’indicizzazione dei file di testo

Uno dei nodi cruciali per l’indicizzazione dei file di testo è la scelta della struttura in cui memorizzare le informazioni. Esistono tante strutture come i Flat file, gli Inverted files, i Signature files, gli alberi e i grafi.

Un file invertito. Tra le strutture che si possono utilizzare spiccano gli Inverted files, una struttura molto particolare e largamente usata da molti motori di ricerca. Si tratta di un semplice file in cui sono contenute poche informazioni, per l’esattezza un inverted file contiene un insieme di righe di testo, in cui ogni riga contiene:

  1. Il termine che si vuole cercare;
  2. Una sequenza di puntatori a documenti e/o records che contengono quel termine;

La parola “inverted” deriva dalla struttura del file. Si ha prima la parola chiave e poi il documento che contiene la chiave.

Le operazioni che si possono effettuare con le parole chiave sono solo tre: AND, OR e NOT. Facciamo un esempio, come si vede dall’aimmagine se la nostra query utilizza l’operatore AND significa che vogliamo cercare tutti quei file (record) che contengono entrambi (essendo un AND) i termini ricercati (i nostri TERM).

Gli Inverted File per l'indicizzazione dei file di testo

Solo il documento Record_3 contiene sia il termine TERM_1 che il termine TERM_2, pertanto sarò l’unico documento ad essere restituito all’utente.

A differenza dei flat-file non si analizzano i documenti interi ma solo l’inverted file da cui si ricavano i collegamenti ai documenti che contengono la chiave o che soddisfano la query. Si ha un approccio molto più efficiente.

Inverted File con operazioni estese. Un’integrazione alle operazioni che si possono effettuare con un qualsiasi inverted file ci vengono date dagli Inverted File con operazioni estese che servono a fornire differenza importanza (peso) tra un termine ed un altro, la posizione in cui un termine compare e la sua frequenza di apparizione all’interno di un documento. Vengono così introdotte due nuove operazioni:

  1. WITHIN SENTENCE:

    Term i WITHIN SENTENCE Term j

    I Term i e j sono presenti nella stessa frase del record recuperato.

  2. ADJACENT:
    Term i ADJACENT Term j

    I Term i e j confinanti nel record recuperato.

Di conseguenza anche la struttura dell’Inverted File cambierà, non avremo più termini e record, ma sarà del tipo:

Term i: Record_n°, Paragrafo_n°, Frase_n°, Parola_n°

Pubblicato in Informatica, Motori di Ricerca Taggato con: , , , , , , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*