Analisi - Università di Pisa

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.52.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