Indicizzazione di documenti semistrutturati Sistemi informativi – AA 2006-2007 D’Este Laura Overview Indicizzazione di documenti semistrutturati 2 Overview I sistemi di IR nascono per cercare informazioni su testi senza una struttura stabilita, locali o sul web. I DB nascono per cercare informazioni in tabelle di dati ben strutturati: insiemi di elementi che presentano valori per attributi ben definiti. Indicizzazione di documenti semistrutturati 3 Overview Oggi ci occuperemo dei problemi che si trovano nel creare un motore di ricerca per i dati semistrutturati, in particolare nella fase dell’indicizzazione. Indicizzazione di documenti semistrutturati 4 Overview: dati semistrutturati (1) Un database di dati semistrutturati può essere visto come un albero in cui le foglie contengono testo e i nodi specificano quale ruolo semantico ha quella stringa all’interno del documento. Indicizzazione di documenti semistrutturati 5 Overview: dati semistrutturati (2) <article> <title>XML is Everywhere</title> <abstract> <paragraph>XML is..</paragraph> <paragraph>The main goal</paragraph> <paragraph>...... </paragraph> </abstract> <section> <title>XML come</title> <paragraph>XML become</paragraph> <paragraph>...... </paragraph> </section> </article> Indicizzazione di documenti semistrutturati 6 Overview: indicizzazione (1) L’indexing è quel processo in cui i dati su cui compiere la ricerca vengono analizzati e organizzati in un indice che agevolerà le operazioni di ricerca. Indicizzazione di documenti semistrutturati 7 Overview: indicizzazione (2) Esempi: Indice analitico Inverted index … Indicizzazione di documenti semistrutturati 8 XML: lo standard per i dati semistrutturati eXtended Markup Language: XML XML viene utilizzato per i contenuti Web, per alcuni programmi aziendali, per lo scambio di testi e per molte altre applicazioni. Indicizzazione di documenti semistrutturati 9 Problemi Indicizzazione di documenti semistrutturati 10 Problema 1 Mancanza di un’unità naturale per il documento, non è facile individuare una indexing unit. Bisogna rispettare lo Structured document retrieval principle: a system should always retrieve the most specific part of a document answering the query. Indicizzazione di documenti semistrutturati 11 Problema 1 La strategia ricercata è quella che ci permette di ritornare come risultato la più piccola unità che contiene l’informazione richiesta. Sono state assunte diverse soluzioni alla questione. Indicizzazione di documenti semistrutturati 12 Problema 1 1. Indicizzare tutti i componenti che possono essere restituiti in una ricerca: I risultati possono contenere unità ridondanti che vengono filtrate in un secondo momento. Indicizzazione di documenti semistrutturati 13 Problema 1 2. Raggruppare i nodi in pseudodocumenti non coincidenti. Risolve il problema della ridondanza ma le unità scelte potrebbero essere meno intuitive per l’utente e difficili da gestire, in quanto fissate durante l’indexing e non legate alla ricerca effettuata. Indicizzazione di documenti semistrutturati 14 Problema 1 3. Fissare un attributo XML come unità di documento. Come nella tecnica precedente le unità di indexing sono fissate costringendoci a rielaborare i risultati in un post-processing. Indicizzazione di documenti semistrutturati 15 Problema 2 Necessità di distinguere il diverso contesto di un termine a seconda dell’attributo a cui è legato. Ad esempio distinguere uno scritto di Bruno Vespa con un libro sul ciclo di vita di una vespa. Indicizzazione di documenti semistrutturati 16 Problema 2 E’ necessario dunque collegare ad ogni contenuto il suo contesto: autore/”Vespa” titolo/”Vita di una vespa” Indicizzazione di documenti semistrutturati 17 Problema 3 Gli schemi dei documenti XML spesso sono differenti tra loro dunque uno stesso attributo può variare nome o addirittura essere smembrato in più parti. Indicizzazione di documenti semistrutturati 18 Problema 3 L’unica soluzione disponibile è quella di collegare manualmente o semiautomaticamente (anche se con un peggiore risultato) le diverse etichette che rappresentano lo stesso attributo. Indicizzazione di documenti semistrutturati 19 Un indexer per XML Index Fabric Cooper, Sample, Franklin, Hjaltason, Shadmon Proceedings of the 27th VLDB Conference, Roma, Italy, 2001 Indicizzazione di documenti semistrutturati 20 Index Fabric Our solution encodes paths as strings, and inserts those strings into a special index that is highly optimized for long and complex keys. Indicizzazione di documenti semistrutturati 21 Index Fabric L’idea che è al centro di questo progetto è quella di rappresentare ogni elemento con il suo percorso e di rappresentare questo path come una stringa da inserire in un database altamente ottimizzato per la ricerca di stringhe. Indicizzazione di documenti semistrutturati 22 Index Fabric: il database Viene utilizzato il Patricia Trie, una tecnica che permette di lavorare agilmente con un grande numero di stringhe. L’albero ottenuto è a sua volta elaborato per permetterci di avere il risultato con un numero piccolo e costante di operazioni di I/O. Indicizzazione di documenti semistrutturati 23 Fabric Index: il database, un esempio Indicizzazione di documenti semistrutturati 24 Fabric Index: il database, un esempio Indicizzazione di documenti semistrutturati 25 Fabric Index: il database, un esempio Indicizzazione di documenti semistrutturati 26 Fabric Index: il database, un esempio Indicizzazione di documenti semistrutturati 27 Fabric Index: il database, un esempio Indicizzazione di documenti semistrutturati 28 Fabric Index: il database, un esempio Una sola operazione di I/O Memoria Disco Indicizzazione di documenti semistrutturati 29 Dal documento XML alla stringa Indicizzazione di documenti semistrutturati 30 Row paths & Refined paths Oltre alla rappresentazione “grezza” dell’albero del documento, si possono inserire dei percorsi “raffinati” che aumentano la velocità di alcune ricerche che sono ritenute frequenti”. Es.”Trova le fatture in cui la compagnia X ha venduto alla compagnia y.” Assegnamo Z come designatore a questo path e troviamo le corrispondenze. Se Acme Inc ha venduto ad ABC Corp potremo scrivere “Z ABC Corp Acme Inc” ed inserire questa stringa nell’index. Indicizzazione di documenti semistrutturati 31 Risultati sperimentali Indicizzazione di documenti semistrutturati 32 Bibliografia Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2007 B. Cooper, N. Sample, M. J. Franklin, G. R. Hjaltason, and M. Shadmon. A fast index for semistructured data. In Proceedings of VLDB, 2001. http://citeseer.ist.psu.edu/cooper01fast.html B. Cooper, N. Sample, and M. Shadmon. A parallel index for semistructured data. ACM Symposium on Applied Computing 2002, to appear. http://citeseer.ist.psu.edu/cooper02parallel.html Indicizzazione di documenti semistrutturati 33