Il database dei vettori di termini

Il database dei vettori di termini permette al motore di ricerca di controllare in maniera estremamente veloce quali termini rilevanti contenga ogni documento e quale sia il loro peso.

Un vettore di termini consiste in linea di massima in una serie di coppie “termine-peso” di lunghezza variabile, dipendente dal numero di termini che compongono il documento di cui si costruisce il vettore.

Dal documento in esame vengono estratte tutte le sequenze di caratteri non separate da spazi, trovate fuori dai tag HTML o dentro i metatag, senza considerare le sequenze contenute fra l’inizio e la fine di una sezione <script>. I termini così estratti dal documento vengono chiamati “termini candidati”.

I termini candidati vengono filtrati mantenendo solo quelli presenti nel “terzo di mezzo” dell’indice globale dei termini di tutta la collezione indicizzata. In parole povere, dopo aver redatto l’elenco completo dei termini contenuti in tutti i documenti dell’indice ed averli ordinati per numero di occorrenze, l’elenco viene diviso in tre parti di identica ampiezza ed al momento del filtraggio dei termini candidati, per ogni documento vengono scartati sia i termini appartenenti alla sezione di indice contenente i termini usati più raramente sia quelli appartenenti alla sezione contenente i termini utilizzati più frequentemente.

Questo è utile perché i termini usati più frequentemente sono poco indicativi, apparendo spesso nella maggior parte dei documenti a prescindere dalla loro similitudine, e tendono così a rendere più difficoltosa la discriminazione fra i vettori, mentre quelli usati meno frequentemente generano “interferenze” che peggiorano l’analisi della similarità dei vettori. Pensate per esempio ad un termine digitato in modo sbagliato: esso verosimilmente apparirà su poche pagine, che però potranno trattare anche temi completamente diversi. Se questo termine venisse considerato avrebbe molto peso, in virtù della sua scarsità all’interno della collezione dei documenti, e indurrebbe a calcolare fra le pagine una forte relazione in realtà inesistente.

Dopo il filtraggio, i termini vengono “pesati”, dividendo il numero di volte in cui appaiono nel documento per il numero di volte in cui appaiono nell’intera collezione dei documenti indicizzati. Questo metodo per calcolare il peso dei termini è denominato TF-IDF (term frequency-inverse document frequency) e nelle sue molteplici variazioni è uno standard fin dai primi anni 70, quando fu ideato da Sparck-Jones.

Con l’etichetta generica TDF-IDF vengono spesso indicati metodi di calcolo molto diversi, alcuni molto semplici ed altri estremamente sofisticati. Quelli semplici consistono praticamente nella sola divisione fra il numero di occorrenze del termine nel documento e nella collezione, seguita da una normalizzazione allo scopo di compensare la lunghezza variabile dei documenti. Tutti i metodi TDF-IDF però si basano sugli stessi due concetti principali.

Termini che appaiono molte volte in un documento sono considerati rilevanti.

Termini che appaiono spesso nell’intera collezione dei documenti sono considerati poco rilevanti.

Quando è stato stabilito un peso per ogni termine presente nel documento che ha passato il primo filtraggio, vengono memorizzati nel vettore i 50 termini con peso maggiore.

Nonostante il filtraggio dei termini sia stato eseguito con un metodo TF-IDF, in questo esperimento nel database non viene memorizzato tale peso bensì la semplice frequenza del termine, ovvero il numero di volte nel quale il termine compare all'interno del documento, oltre alla lunghezza della pagina espressa sia in byte, sia in numero di termini. Questo viene fatto per mettere a diposizione i dati “grezzi” di partenza e lasciare alle applicazioni la maggior libertà possibile di pesare i termini con i metodi che vengono considerati di volta in volta più adatti.

Il database così costruito permette con due semplici chiamate di funzione di confrontare fra loro i vettori di termini di due documenti e stabilirne il grado di similarità. Per pura curiosità il database dell’esperimento ha sfruttato l’indice di Altavista (quello dell'anno 2000 ovviamente) e conteneva 272 milioni di vettori occupando uno spazio di 33Gb.

Vedremo insieme nel prossimo articolo quali applicazioni sono state realizzate a titolo di esempio con questo database e con quali risultati.

Ultima modifica: 21/10/2005 - 11:35