Motori di Ricerca presente e futuro prossimo Cosa è un Analizzatore Lessicale ? Paolo Ferragina, Università di Pisa Codifica di un testo ASCII (1963) 8 bit per carattere (7+1) Sufficiente per l’inglese ma non italiano e tedesco. XML (W3C 1998, o SGML IBM 1986) Distinguiamo struttura – contenuto – visualizzazione Standard aperto e personalizzabile, ma well-formed o valido Indipendente dalla piattaforma, in quanto puramente testuale <email> <from> Paolo Ferragina </from> <to> Elena Pierazzo </to> <subject> prova </subject> <bodymsg> bla bla... </bodymsg> </email> Paolo Ferragina, Università di Pisa XML: un nuovo “e-alfabeto” Tag Progetto Gutemberg Contenuto + Annotazione Liceo Galluppi 26-30 Aprile 2003 \320\317^Q\340\241\261^Z\341 ^@^@^@..... .. .. <brochure> Progetto Gutemberg </titolo> ..<titolo> Progetto Gutemberg <luogo> Liceo Galluppi </luogo> ...^@^S Liceo SHAPE Galluppi \* MERGEFORMAT <data> ^T^H^A^U^M 26 Aprile^M ore... <inizio> 26 Aprile 2003 </inizio> 26 Aprile 2003 2003 </fine> <fine> 30 Aprile 30 Aprile 2003 </data> <testo> Il progetto nasce .... </testo> Il progetto nasce .... <interventi> <intervento> <data> 26 Aprile 2003 </data> 26 Aprile 2003 <ora> 9 </ora> 9<relatore> Prof. A. Vitale </relatore> Prof. Apertura A. Vitale Lavori </titolo> <titolo> Apertura </intervento> Lavori <intervento> ..... </intervento> ... </interventi> </brochure> %!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: C:Progetto.doc %%CreationDate: Tue Apr 22 2003 %%Pages: 30 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 .... Programma.doc Il progetto nasce..... 26 Aprile • ore 9: apertura lavori, Prof. A. Vitale • ore 10: .... motore di ricerca universale e “semantico” File puramente testuale /TeXDict 300 dict def TeXDict begin /N{def}def/B{bind def}N/S{exch}N /X{SN}B/A{dup}B/TR{translate}N/isls Visualizzazione (fogli di stile) Paolo Ferragina, Università di Pisa Programma.ps XML e Linguistica CIBIT: consentirà l’accesso a tutti i testi della letteratura italiana in XML. Corpus Dantesco (Prof. Tavoni) Opere del Vasari (Cribecu, SNS) Giordano Bruno (Cribecu, SNS) Corte dei Conti (CNR, Pisa) I Letterati si preoccupano di fornire una annotazione corretta e completa. Gli Informatici si preoccupano di sviluppare strumenti potenti ed efficienti per l’elaborazione. I Grafici si preoccupano di visualizzare il tutto in modo accattivante. Perché XML ? Nuovo alfabeto standard e indipendente dalla piattaforma per codificare le informazioni. Molti strumenti pubblici per elaborare questa codifica. Paolo Ferragina, Università di Pisa Disaccoppiamento tra fase di annotazione e fase di sviluppo degli strumenti per l’analisi. Passi principali dell’Analizzatore Figure from Baeza-Yates & Ribeiro-Neto Fase di analisi delle pagine (eterogenee) Varie difficoltà per la “normalizzazione” State-of-the-art, U.S.A. vs. USA, a.out 3/12/91, Mar. 12, 1991, 55 B.C., B-52, 100.2.86.144 Cooper’s vs Cooper vs Coopers résumé vs resume Google: kid’s toys, kids toys, kid’s toy (anche singolare/plurale in italiano) Stemming: riduce le parole alle loro radici Dipende dal linguaggio (inglese: Porter) Errori: automate(s), automatic, automation automat for example compressed and compression are both accepted as equivalent to compress Paolo Ferragina, Università di Pisa for exampl compres and compres are both accept as equival to compres Proprietà statistiche dei testi I token non sono distribuiti uniformemente nel testo Ma seguono la cosiddetta “legge di Zipf” Pochi elementi sono molto frequenti Un numero medio di essi ha frequenza media Moltissimi sono infrequenti Il numero di token distinti non cresce linearmente Ma secondo la “legge di Heaps” (|T|b con b<1) Le parole interessanti hanno una caratterizzazione Sono quelle mediamente frequenti (Luhn) Paolo Ferragina, Università di Pisa Un esempio di “Curva di Zipf” Paolo Ferragina, Università di Pisa La legge di Zipf, nel dettaglio Il prodotto della frequenza (f) di un token e il suo rango (r) è approssimativamente constante r*f=cN f=cN/r Legge di base f = c N / ra a = 1.52.2 Legge generale Un modo alternativo di vedere la cosa: Il termine di rango 1 occorre C volte Il secondo termine più frequente occorre C/2 volte Il terzo termine occorre C/3 volte … Paolo Ferragina, Università di Pisa Dove occorre la Legge di Zipf ? Distribuzione parole in una collezione testuale, indip. linguaggio Richista di pagine web Link in uscita e in ingresso a pagine Web Dimensione dei documenti sul Web Paolo Ferragina, Università di Pisa Consequenze della Legge di Zipf Esistono pochi token molto frequenti che non fungono da buoni discriminatori. Le cosiddette “stop words” in IR Inglese: to, from, on, and, the, ... Italiano: a, per, il, in, un,… Esistono anche moltissimi token che occorrono una volta sola nel testo e quindi sono poco utili per gli algoritmi (errore / corretto?). Inglese: Calpurnia Italiano: Precipitevolissimevolmente (o, paklo) Parole mediamente frequenti Paolo Ferragina, Università di Pisa Parole discriminanti Frequenza vs. Potere discriminante (Luhn) Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Cosa è un Compressore ? Paolo Ferragina, Università di Pisa Perché comprimere ? Obiettivo: Eliminazione della ridondanza nei testi Riduzione spazio 33% tecniche standard (gzip, winzip,...) 20% tecniche avanzate (bzip, ppm) Miglioramento delle prestazioni CPU L1 L2 RAM HD rete registri Cache Pochi Mbs Alcuni nanosecs Poche words Paolo Ferragina, Università di Pisa Pochi Gbs Decine di nanosecs Alcune words Pochi Tbs Pochi millisecs B = 32K Molti Tbs Anche secs Pacchetti Gzip (’77-’78, raggiunge il 30%) Elimina ridondanza copiando pezzi di testo già visti T = a b a a b b a b a a a ..............a b a b a b a b b < 2,5,b > < 6,4,a > T = a b a a b b a b a a a .... <0,0,a> <2,1,a> <0,0,b> Paolo Ferragina, Università di Pisa <3,1,b> <6,4,a> Più è lungo il testo, più ripetizioni ci aspettiamo, più risparmio otteniamo Huffman (’50, raggiunge il 60%) Elimina ridondanza assegnando codeword corte a simboli frequenti Codeword = sequenza di bit (a = 01, b = 10) 100 0 ASCII [NO: a=0, b=01] 1 55 Assegna 8 bits a tutti i simboli indipendentemente dalla loro frequenza 0 1 30 0 1 25 14 0 Symb:freq f:5 Paolo Ferragina, Università di Pisa a=1 b = 011 c = 010 d = 001 e = 0001 f = 0000 1 e:9 0 d:16 c:12 1 b:13 a:45 Compresso = Albero + codifica di T Huffword (raggiunge il 30%) I simboli sono i token: parole o separatori L’albero è molto grande 100 0 1 55 0 1 30 0 1 25 14 0 Symb:freq cane:5 Paolo Ferragina, Università di Pisa =1 , = 011 . = 010 il = 001 gatto = 0001 cane = 0000 spazio 1 0 gatto:9 il:16 . :12 1 ,:13 spazio:45 Compresso = Albero (grande) + codifica di T Tagged Huffword (supporta la ricerca) Dividiamo ogni parola di codice in gruppi di 7 bit Aggiungiamo in testa a ogni gruppo un bit di tag 0 per l’ultimo gruppo 1 per tutti gli altri gruppi , = 011 cane = 0000 cuccia = 1111111 11 011 00110000 0000 00000000 1111111 11 11111111 01100000 Esempio: Sincronizzazione: Fine parola di codice = byte che inizia con 0 Decompressione: Elimino il bit di tag da ogni byte, e scopro la parola di codice guardando dall’inizio la sequenza rimasta La ricerca sul compresso è possibile Paolo Ferragina, Università di Pisa