10 BOLLETTINO DEL CILEAN.118DICEMBRE 2011
Information Retrieval: concetti e principi di base
Susanna Mornati
*
, Andrea Marchitelli
**
*CILEA, Servizi per l’Università — Area Ricerca ,**CILEA, Servizi applicativi e assistenza
Abstract
“Information Retrieval” è un’espressione usata in ambito informatico per indicare le tecniche, i sistemi e i servizi di ricerca, manipolazione e rappresentazione di dati digitali espressi in linguaggio umano e raccolti in vaste collezioni di documenti, con l’obiettivo di facilitarne l’accesso ai contenuti. Gli ambiti di applicazione sono molteplici. Ai giorni nostri il più noto è costituito dai motori di ricerca nel World-Wide Web, utilizzati quotidianamente da milioni di persone per il lavoro, gli affari, l’apprendimento, il divertimento, la vita quotidiana. Il presente articolo offre una breve panoramica delle caratteristiche principali dei sistemi di information retrieval, dei processi sottesi e delle cri-ticità, per terminare con un cenno al sistema di ricerca più diffuso.
“Information Retrieval” is about techniques, systems and services concerned with search, manipulation and repre-sentation of digital data, expressed in human language and stored in vast document collections. Information Re-trieval is about facilitating discovery of document contents. Application context are varied and popular, such as web search engines that are used by millions of people for work and business, learning and entertainment, daily life. This article briefly covers information retrieval main features, processes and problems, ending with a hint to the most popular search system.
Keywords: Information Retrieval, Lucene, Solr
Definizione e ambiti di applicazione
“Information Retrieval” (in italiano “recupero di informazioni”, d’ora in poi IR) è un’espressione usata in ambito informatico per indicare le tecniche, i sistemi e i servizi di ricer-ca, manipolazione e rappresentazione di dati digitali espressi in linguaggio umano e raccolti in vaste collezioni di documenti, con l’obiettivo di facilitarne l’accesso ai contenuti [1].
Gli ambiti di applicazione dell’IR sono molte-plici. Ai giorni nostri il più noto è costituito dai motori di ricerca nel World-Wide Web, utilizzati quotidianamente da milioni di persone per il la-voro, gli affari, l’apprendimento, il divertimen-to, la vita quotidiana, per recuperare informa-zioni di ogni genere: notizie ed eventi, persone e aziende, acquisti e trasporti, tecniche e oggetti, consigli, ricette e così via.
Un ambito più ristretto riguarda le biblioteche digitali, collezioni di testi in formato elettronico, in parte proprietarie, a pagamento e destinate all’informazione specialistica: medica, economi-ca, scientifieconomi-ca, tecnologieconomi-ca, legale, ma anche re-pertori di prodotti e servizi online, sia commer-ciali sia erogati da pubbliche amministrazioni,
fino alle biblioteche tradizionali con i cataloghi in linea.
Sistemi enterprise o desktop di IR sono adot-tati in contesto aziendale o personale per la ge-stione e l’archiviazione di documenti, e-mail, rapporti, schede, sia a supporto dei processi di business, sia per funzioni di knowledge mana-gement.
Infine anche singole applicazioni, ad esempio programmi di videoscrittura o client per la po-sta elettronica, prevedono delle funzioni interne per la ricerca e il recupero di informazioni.
L’abbondanza di informazioni che quotidia-namente produciamo e di cui abbiamo bisogno rende i sistemi di IR un complemento indispen-sabile dei nostri strumenti di produttività. Architettura dei sistemi di IR
I sistemi di IR condividono lo stesso modello architetturale e organizzativo di massima adat-tandolo ai diversi contesti applicativi.
Il primo componente è il bisogno informativo (information need o topic) dell’utente, che sot-tende all’intero processo di ricerca e recupero.
In base a questo l’utente costruisce e sottopo-ne all’IR un’interrogaziosottopo-ne (query), tipicamente
S.MORNATI BOLLETTINO composta d termini (ter Si utilizz perché potr da una par musicale, u consenta c esempio il t la radice) p role: “info “informatic Sebbene l interrogazi o pochi ter supportano pio dotate d tors) e di matching), gere i risult L’interrog motore di r principale è index o inv cumenti (do L’indice c dati utilizz colo della ri La funzio mappatura ve collocazi Per esegu levanza (re mantiene s esempio il n un determi mine per ci Il calcolo score) cons fase di pres Altre elab di risultati Mediante e di altri da restituisce zione. Il problem il più cruc trieval. Il process TI,A.MARCH NO DEL CILEA da una ristre rm). a “termine” rebbe tratta rola, ad esem un numero corrisponden termine “inf potrebbe cor rmare”, “in ca” e così via la maggior p oni costituit rmini giust o spesso sint di operatori corrisponde che consen tati delle ric gazione dell’ ricerca (sear è gestire un verted file) document coll costituisce l ata dal mot ilevanza. one di base a (mapping) ioni nella col uire algoritm elevance ran statistiche numero di d inato termin iascun docum del puntegg ente l’ordin sentazione d borazioni co ridondanti o l’utilizzo de ati ed elabo all’utente i ma di restitu ciale nel ca o è rapprese HITELLI EAN.118DIC etta quantit ” anziché “p arsi di qualc mpio una d , un operat nze (match) form*” (con a rrispondere nformativo”, a. parte degli u te da un sem tapposti, i s tassi più ric
booleani (B enza di mo ntono di filtr cerche. ’utente è ela rch engine), indice inver per una col llection). a principale tore per la ri e dell’indice fra i termin llezione in c mi di misura nking) il mot associate a documenti ch ne, le occorr mento e così gio di rilevan namento dei dei risultati. onsistono ne o duplicati. ell’indice, de razioni, il m risultati de uire risultat ampo dell’in entato in Fig CEMBRE 201 à (due-tre) parola” (wor osa di diver ata, una no tore jolly ch ) parziali, a asterisco do a diverse p “informale utenti esprim mplice termin sistemi di I cche, ad esem Boolean oper delli (patte rare e restri aborata da u il cui compi rtito (invert llezione di d e struttura icerca e il ca e è fornire ni e le rispet cui si trovano azione della tore di ricer agli indici, a he contengon renze del te ì via. nza (relevan documenti ella rimozion elle statistich motore dunqu ella interrog ti pertinenti nformation r g. 1. SERVIZI P 11 di rd) rso ota he ad po pa-e”, ma ne IR m- ra-ern in-un ito ted do-di al-la tti-o. ri-rca ad no er-nce in ne he ue ga-i è re-F te re st di re ne ti a st PER L’UNIVER Fig. 1 – Ar unzioni ac Alcune colle eche digitali e l’IR, ad trutturate in ivisi. Tuttav e migliorata e applicabili i, sovrappon problemi pi Di seguito s ta applicazio routing, fi mentre un luta le in collezione stradamen luta nuovi sieme di utenti. Es gregatori d sta; categoriza raggruppa condivise, “apprendim stema le condo il si da sé; summariz porzioni r snippet di cerche web Informatio menti spe date, e le c RSITÀ rchitettura di cessorie d ezioni di doc i, supportan esempio de n metadati via l’efficacia anche da te i a collezioni nendo temat ù strettame si segnalano one: filtering e se na tipica app terrogazioni di docume nto, filtraggi i documenti interrogazi sempi di ap di news o i f ation e clust are docume il primo m mento” inse diverse cat istema impi zation - ridu rappresenta testo mostr b; on extractio cifiche entit collega fra lo Information dei sistemi cumenti, qua no apparati escrizioni d secondo sta a del recupe ecniche di m i non dotate tiche di bibl ente informa o alcune tec elective diss plicazione di i a fronte d enti, un sist io o dissemi a fronte di ioni già fo pplicazione s filtri antispa stering - con enti secondo metodo tram eriti per illu tegorie, men
iega modelli uce i docume ative, ad e
rati con i ris on - identific tà, ad esemp oro; 10-13 11 Retrieval di IR ali le biblio-per facilita-egli oggetti andard con-ro può esse- manipolazio-e di mmanipolazio-etada- metada-ioteconomia atici. niche di vasemination -i r-icerca va-di una data tema di in-inazione va-un dato in-ornite dagli sono gli ag-am della po-nsentono di o proprietà mite dati di strare al si-ntre nel se-i che scopre enti a brevi esempio gli sultati di ri-ca nei docu-pio luoghi e 3 1 -i -a -- -a -i -i à i -e i i -e
S.MORNATI,A.MARCHITELLI SERVIZI PER L’UNIVERSITÀ 10-13
12 BOLLETTINO DEL CILEAN.118DICEMBRE 2011
topic detection e tracking - identifica eventi in flussi e ne segue le evoluzioni.
A questi se ne aggiungono altri, che estendono le funzionalità dei sistemi di IR per obiettivi specifici, ad esempio la ricerca in oggetti mul-timediali quali file audio, video e immagini. I processi degli IR
Per procedere alla costruzione di indici inver-titi, i documenti vengono innanzitutto convertiti in testo grezzo (raw text), semplice flussi di ca-ratteri, che viene poi ulteriormente elaborato. Tutte le lettere maiuscole vengono convertite in minuscole, in modo da considerare le occorrenze di termini come “PENNA”, “Penna” e “penna” come equivalenti. Quindi il testo viene converti-to in sequenze di “getconverti-toni” (converti-token) ossia sequen-ze di caratteri alfanumerici separati da uno spazio o da particolare segni di punteggiatura.
La costruzione degli indici avviene abbinando a ciascun token un numero intero (integer) che ne indica la posizione nel testo o nella collezione di testi. L’insieme di token distinti, o simboli (symbols), in una collezione di testi è chiamato vocabolario (vocabulary). Mentre i simboli sono astrazioni, i token sono le loro istanze, le occor-renze nei testi.
La disponibilità di modelli linguistici costruiti con algoritmi complessi consente di effettuare altre operazioni significative per gli indici, ad esempio la determinazione della frequenza di determinati termini, i più frequenti dei quali possono essere esclusi dai termini di ricerca (stop words, ad esempio gli articoli).
La presenza di modelli è utile per determinare la probabilità che un nuovo frammento faccia parte di un corpus già esistente o addirittura generare nuovo testo. Altra applicazione signifi-cativa è il modello di compressione, sempre ba-sato sulle caratteristiche peculiari della lingua, che consente di ridurre le dimensioni degli indi-ci senza influenzarne le prestazioni.
Formati e caratteristiche dei testi
Come definito nell’introduzione, i sistemi di IR lavorano con dati digitali espressi in linguaggio umano. I testi elettronici sono dunque il mate-riale grezzo dell’IR, che richiede la conoscenza dei formati e delle caratteristiche dei testi in essi codificati.
Il primo aspetto da considerare in un testo è il contenuto, ossia la sequenza di parole nell’ordine in cui dovrebbero essere normalmen-te elaboranormalmen-te. Il secondo aspetto è la struttura del testo, ossia la sua eventuale organizzazione in capitoli e paragrafi, pagine e così via.
Contenuto e struttura possono essere codifica-ti in numerosissimi formacodifica-ti di documencodifica-ti, fra cui HTML, XML, PDF, PostScript, RTF, LaTeX, e altri, anche proprietari, prodotti dai principa-li programmi di elaborazione di testi.
Di particolare interesse e importanza per l’ambito dell’IR è XML (eXtensible Markup Language), non strettamente un formato ma piuttosto un metalinguaggio per definire forma-ti di documenforma-ti, con cui è possibile cioè costruire codifiche leggibili e comprensibili sia a noi sia agli elaboratori. Questo attributo lo rende idea-le per la codifica della struttura logica dei testi da indicizzare. La determinazione della struttu-ra fisica: font, layout, impaginazione, può essere gestita al momento della presentazione.
I testi codificati in linguaggi di programma-zione (ad esempio, in parte, il formato PDF) rendono difficile l’estrazione del contenuto per-ché non viene separato dalle istruzioni per la sua formattazione. Si utilizzano dunque stru-menti di conversione che impiegano un approc-cio euristico per “indovinare” il contenuto dei documenti, per non parlare della struttura logi-ca che rimane perlopiù sconosciuta. Anche HTML presenta problemi analoghi, e in aggiun-ta le pagine web il cui contenuto è generato da script rendono impossibile l’indicizzazione.
I formati proprietari presentano i maggiori problemi, nonostante alcuni siano documentati e produttori come Microsoft si stiano orientando verso formati aperti basati su XML.
Infine, anche la codifica dei caratteri può rap-presentare un ostacolo all’indicizzazione e al re-cupero dell’informazione. Per la lingua inglese possono essere codificati a sette bit (valori ASCII). Tuttavia l’ASCII non è sufficiente a rappresentare i caratteri in altre lingue, che non possono essere contenuti in un byte. Per questo motivo occorre impiegare UTF-8, una rappresentazione di Unicode che fornisce una codifica estesa fino a 4 byte per i caratteri della quasi totalità di lingue note, viventi o estinte. Problematiche dei sistemi di IR
Le criticità dei sistemi di IR si rivelano in par-ticolare rispetto a collezioni di grandi dimensio-ni.
Le collezioni di documenti sono spesso dina-miche, ossia soggette ad estensioni e aggiorna-menti. Il modello di aggiornamento può essere relativamente semplice e prevedere solamente l’aggiunta o la cancellazione dei documenti. Tuttavia nelle collezioni di grandi dimensioni, che hanno indici di dimensioni proporzionali, è
S.MORNATI,A.MARCHITELLI SERVIZI PER L’UNIVERSITÀ 10-13
BOLLETTINO DEL CILEAN.118DICEMBRE 2011 13
importante che il sistema di IR preveda mecca-nismi incrementali (append).
Può essere importante riuscire a misurare le prestazioni di un sistema di IR, in particolare efficienza ed efficacia. Per la prima l’aspetto più visibile è costituito dal tempo di risposta (laten-cy o response time) all’interrogazione, ma anche altri parametri possono risultare significativi, ad esempio quante interrogazioni simultanee possono essere gestite o quanto spazio disco è disponibile per gli indici.
L’efficacia è più difficile da misurare in quanto dipende in larga misura da parametri soggetti-vi. Il concetto fondamentale alla base dell’efficacia, che costituisce l’obiettivo principa-le di tutti i sistemi di IR, è la riprincipa-levanza (reprincipa-le- (rele-vance). Un documento è considerato rilevante rispetto a una determinata interrogazione se i suoi contenuti soddisfano, parzialmente o com-pletamente, il bisogno informativo rappresenta-to dall’interrogazione stessa. Il valore di rile-vanza assegnato può essere binario (rilevante o non rilevante) oppure graduato (molto rilevan-te, abbastanza rilevanrilevan-te, poco rilevanrilevan-te, ecc.).
La nozione di rilevanza può essere estesa a considerare altri aspetti dei documenti, quali le dimensioni, la specificità, l’esaustività, il grado di novità rispetto ad altro materiale reperito. Sistemi open source di IR
Esiste un’ampia scelta di sistemi di IR a codi-ce aperto, ma indubbiamente il più diffuso è Lucene della fondazione Apache. Si tratta di un software per indicizzazione e ricerca che con-sente agli sviluppatori di definire le proprie re-gole e formule di indicizzazione e recupero.
Nel 2010 Lucene è stato incorporato da Solr, piattaforma di ricerca che incorpora le librerie di Lucene potenziando la ricerca full text e ag-giungendo una serie di funzionalità interessan-ti, dalla ricerca a faccette al testo cercato evi-denziato. Inoltre sono state sviluppate interfac-ce estese per la sua utilizzazione in molti conte-sti applicativi anche con diversi linguaggi di programmazione [2].
CILEA ha adottato Solr in diversi contesti di servizio, come descritto in altri contributi del presente fascicolo del “Bollettino”, rafforzando così ulteriormente la propria presenza nei set-tori più innovativi dell’ICT.
Bibliografia
[1] Il presente lavoro è parzialmente basato sui capitoli introduttivi del recente e autore-vole manuale di S. Büttcher, C.L.A. Clarke, G.V. Cormack, Information Retrieval: Im-plementing and Evaluating Search Engines, MIT Press, Cambridge, Mass., 2010. Il testo originale è molto più esteso e presenta un elevato livello di approfondimento su tutte le tematiche legate all’indicizzazione e agli al-goritmi applicabili all’IR, oltre a numerose indicazioni pratiche di implementazione per motori di ricerca e altre applicazioni.
