Curs nr. 03 - Indexare (2).pdf

Indexarea documentelor WEB Similaritatea documentelor Discutii Bibliografie

Regasirea Informatiilor pe WEBCurs 03: Indexare (2)

s.l. dr. ing. Alexandru [email protected]

Facultatea de Automatica si Calculatoare, Iasi

an universitar: 2014 2015

RIWeb 2014 2015/C03: Indexare 2 1/ 16


Cuprins

1 Indexarea documentelor WEBConstruirea indecsilor directiConstruirea indecsilor inversi

Algoritmul BSBIAlgoritmul SPIMI

2 Similaritatea documentelor

RIWeb 2014 2015/C03: Indexare 2 2/ 16


Tipuri de indexare curs 2


Indexarea directa

Definitie: reprezinta modalitatea de indexare ce are drept scop determinareaindecsilor relativ la document.

Utilizeaza structuri de date ordonate, pentru care cheia primara de ordonareeste data de un identificator unic al documentului.

Sinonim indexare orizontala.

Forma generala

< docID : {termIDx |termIDx docID} >unde:

docID identificator numeric atasat unui document;

termIDx identificator numeric atasat unui token (cuvant obtinut dupapre-procesare) inclus n documentul curent.

RIWeb 2014 2015/C03: Indexare 2 3/ 16



Tipuri de indexare (2) curs 2

Indexarea inversa

Definitie: reprezinta modalitatea de indexare ce are drept scop determinareadocumentelor relativ la index.

Utilizeaza structuri de date ordonate, pentru care cheia primara de ordonareeste data de indecsi sau de identificatori unici ai indecsilor.

Sinonim indexare verticala.

Forma generala

< termID : {docIDy |termID docIDy} >unde:

termID identificator numeric atasat unui token (cuvant obtinut dupapre-procesare);

docIDy identificator numeric atasat unui document n cadrul caruia seregaseste token curent.

RIWeb 2014 2015/C03: Indexare 2 4/ 16


Construirea indecsilor directi

Construirea indecsilor directi

Pasi implicati pentru fiecare document din colectie

1 se identifica/extrage, rand pe rand, fiecare cuvant din cadrul documentului;

2 fiecare cuvant astfel identificat este filtrat (testat contra listelor de exceptii sicontra listei de cuvinte de tip zgomot stopwords) si retinut n formacanonica;

3 n functie de tipul de indexare dorita se poate retine cuvantul determinat,cuvantul determinat si numarul de aparitii, pozitiile cuvantului determinat ncadrul documentului, etc.

Rezultat

Colectii de fisiere, n mod uzual cu numele dat de identificatorul de documentdocID, ce contin valori de forma termID.

RIWeb 2014 2015/C03: Indexare 2 5/ 16


Construirea indecsilor inversi

Algoritmul Blocked Sort-Based Indexing BSBI

Pseudocod (preluare din [1])

Algoritm 1 BSBI()

1: n 02: while all documents have not been processed do3: n n + 14: block PARSENEXTBLOCK()5: BSBI-INVERT(block)6: WRITEBLOCKTODISK(block, fn)7: end while8: MERGEBLOCKS( f1, . . . , fn; fmerged )

RIWeb 2014 2015/C03: Indexare 2 6/ 16



Algoritmul Blocked Sort-Based Indexing BSBI (2)

Detalii

Algoritmul presupune segmentarea colectiei de documente n blocuri dedimensiuni aproximativ egale.

Pentru fiecare bloc:

sunt parsate documentele si se determina toate perechile de formatermID-docID (metoda PARSENEXTBLOCK);pentru fiecare bloc n parte, perechile obtinute sunt sortate dupa cheie primaratermID, cheie secundara docID (n cadrul metodei BSBI-INVERT);se determina apoi listele de indecsi inversati concatenarea informatiilorpentru acelasi termID (n cadrul metodei BSBI-INVERT);

Algoritmul se finalizeaza prin reuniunea tuturor rezultatelor intermediare subforma unei indexari unice (metoda MERGEBLOCKS)

RIWeb 2014 2015/C03: Indexare 2 7/ 16



Algoritmul Single-Pass In-Memory Indexing SPIMI

Pseudocod (preluare din [1])

Algoritm 2 SPIMI (token stream)

1: output file new file()2: dictionary new hash()3: while free memory available do4: token next(token stream)5: if term(token) / dictionary then6: postings list addToDictionary(dictionary, term(token))7: else8: postings list getPostingsList(dictionary, term(token))9: end if

10: if isFull(postings list) then11: postings list doublePostingsListSize(dictionary, term(token))12: end if13: addToPostingsList(postings list, docID(token))14: end while15: writeBlockToDisk(sorted terms, dictionary, output file)16: return output file

RIWeb 2014 2015/C03: Indexare 2 8/ 16



Algoritmul Single-Pass In-Memory Indexing SPIMI(2)

Detalii

Principiul algoritmului este de a construi dinamic indexul invers, fara acolecta si sorta perechi de forma < termID docID > (precum n cazulalgoritmului BSBI) [1].

Algoritmul are urmatoarele particularitati: [1]1 nu realizeaza asocieri de forma termID term, ceea ce ar putea conduce la o

organizare mai buna a memoriei (practic, nu mai este necesara tabelei dedispersie ce ar asocia un cuvant de un identificator numeric);

2 un token include atat cheia de indexare (cuvantul) cat si valorile acestei chei(respectiv, n cazul acest particular, documentul/documentele ce includcuvantul curent).

RIWeb 2014 2015/C03: Indexare 2 9/ 16


Similaritatea documentelor

Cautarea documentelor implica...

... identificarea unui set de atribute ale documentelor (???) si a unei metode decalcul a ,,distantei dintre doua documente.

Abordarea standard similaritatea cosinus

reprezentarea documentelor sub forma vectoriala se obtine foarte rapiddintr-un index direct cantitativ (index direct pentru care se retine sinumarul de aparitii al ficarui cuvant);

similaritatea a doua documente este data (n acest caz) de unghiul formatde vectorii corespunzatori celor doua documente:

cos(^d1,d2) =d1 d2d1d2

(1)

RIWeb 2014 2015/C03: Indexare 2 10/ 16


Similaritatea documentelor (2)

Abordarea standard similaritatea cosinus (2)

Exemplificare calculati, utilizand ecuatia (1), similaritatea urmatoarelor fraze:

d1 : ,,Data mining este o technica noua de analiza a datelor

d2 : ,,Tehnicile data mining pot aduce informatii noi

d3 : ,,Datele sunt colectate prin tehnici specifice

d4 : ,,Profesorul de RIW este gamer

RIWeb 2014 2015/C03: Indexare 2 11/ 16




Problema cat de important este un anumit cuvant ntr-un anumit context?

Rezolvare ponderarea indexului direct cantitativ al fiecarui document prin

1 determinarea importantei unui anumit cuvant n cadrul documentuluicurent (P1);

2 determinarea importantei unui anumit cuvant n cadrul unui anumitdomeniu de documente (P2).

RIWeb 2014 2015/C03: Indexare 2 12/ 16




Coeficienti utilizati

P1 frecventa de aparitie a cuvantului k n cadrul documentului d (n eng.:term frequency)

tf (k , d) =count(k)

|d | (2)

P2 frecventa inversa de aparitie a cuvantului k n cadrul multimii dedocumente D (n eng.: inverse document frequency)

idf (k) = log|D|

1 + |{d : k d}| (3)

Vectorul asociat fiecarui document va fi:

d = {key : tf (key , d) idf (key)} (4)

RIWeb 2014 2015/C03: Indexare 2 13/ 16




Exemplificare calculati, utilizand ecuatia (1) si reprezentarea (4), similaritateaurmatoarelor fraze:

d1 : ,,Data mining este o technica noua de analiza a datelor

d2 : ,,Tehnicile data mining pot aduce informatii noi

d3 : ,,Datele sunt colectate prin tehnici specifice

d4 : ,,Profesorul de RIW este gamer

RIWeb 2014 2015/C03: Indexare 2 14/ 16


Problema

Determinare tf /idf

Cum se determina eficient valorile tf /idf ?

RIWeb 2014 2015/C03: Indexare 2 15/ 16


Bibliografie

1 Christopher D. Manning, Prabhakar Raghavan and Hinrich Schutze,Introduction to Information Retrieval, Cambridge University Press. 2008

2 Raymond J. Mooney Information Retrieval and Web Search (note de curs)

RIWeb 2014 2015/C03: Indexare 2 16/ 16

Indexarea documentelor WEBConstruirea indecsilor directiConstruirea indecsilor inversi

Similaritatea documentelor

Curs nr. 03 - Indexare (2).pdf

Documents

Transcript of Curs nr. 03 - Indexare (2).pdf