Structuri de date: Tema 3Grafuri de cuvinte

Tudor Berariutudor.berariu@gmail.com

10 mai 2015

1 Pe scurt...

Pentru rezolvarea acestei teme va trebui construit un graf de cuvinte (pebaza unui text dat). Se va parcurge apoi acel graf pentru a construi fraze cencep s, i se termina cu doua cuvinte date.

2 Graful de cuvinte

Se da un text n limba romana. Se va parsa acest text s, i se vor separacuvintele (fara semne de punctuat, ie, cratime, etc.). Fiecare cuvant va deveninod ntr-un graf de cuvinte. Intre fiecare doua cuvinte consecutive din textva exista o muchie. Costul unei muchii va reprezenta un scor pentru aceasecvent, a de doua cuvinte calculat dupa cum urmeaza.

Pentru doua cuvinte wordA s, i wordB vom calcula o matrice de contingent, a:

V = wordB V 6= wordBU = wordA O

AB11 O

AB12

U 6= wordA OAB21 OAB22unde:

OAB11 reprezinta numarul total de aparit, ii ale sintagmei word1 word2 ntext.

1

OAB12 reprezinta numarul total de aparit, ii ale unor sintagme n careword1 este urmat de alt cuvant n afara de word2.

OAB21 reprezinta numarul total de aparit, ii ale unor sintagme n careword2 este precedat de alt cuvant n afara de word1.

OAB22 reprezinta numarul total de aparit, ii ale unor sintagme n careprimul cuvant nu este word1, iar cel de-al doilea nu este word2.

Desigur, OAB11 + OAB12 + O

AB21 + O

AB22 = M (numarul total de secvent,e

consecutive de doua cuvinte).Pe baza tabelei de contingent, a a doua cuvinte wordA s, i wordB se calcu-

leaza o masura1 pentru sintagma (colocat, ia) wordAwordB:

OddsRatio(wordA, wordB) = log

(OAB11 OAB22OAB12 OAB21

)= log

(OAB11

)+ log

(OAB22

) log (OAB12 ) log (OAB21 )

Deoarece este posibil ca unii termeni sa fie zero, n practica se foloses,te:

OddsRatio(wordA, wordB) = log

((OAB11 + 0.5

) (OAB22 + 0.5)OAB12 OAB21

)= log

(OAB11 + 0.5

)+ log

(OAB22 + 0.5

) log (OAB12 + 0.5) log (OAB21 + 0.5)

Deoarece masura OddsRatio(wordA, wordB) este o masura a cat de pu-ternica este alaturarea dintre cele doua cuvinte, costul unui arc ntre nodurilewordA s, i wordB va fi:

Cost(wordA, wordB) = 1 + min(wordX ,wordY )

OddsRatio(wordX , wordY )OddsRatio(wordA, wordB)

Pentru doua cuvinte ce nu au aparit, ii consecutive n text nu va existamuchie ntre varfurile corespunzatoare acestora.

1http://www.collocations.de/AM/

2

3 Cerint, e

3.1 Cerint, a 1 : Construirea grafului de cuvinte

Se da un text n limba romana. Sa se extraga cuvintele s, i sa se constru-iasca graful de cuvinte, calculandu-se scorul muchiilor conform formulei dinsect, iunea 2.

Toate simbolurile ., % vor fi eliminate, iar cratima va fi considerat se-parator ntre cuvinte.

Testarea se va face prin verificarea costurilor pentru cateva muchii alesela ntamplare.

3.2 Cerint, a 2: Construirea unei fraze

Se dau doua cuvinte wordstart s, i wordend. Sa se construiasca o fraza cores-punzatoare drumului de cost minim ntre cele doua noduri.

Pentru rezolvarea acestei cerint,e se va implementa o coada de prioritat, i.

3.3 Bonus: Fraze de lungime fixa

Se da un cuvant wordend s, i un numar n. Sa se construiasca fraza de lungimen ce se ncheie cu wordend de cost minim. Atent, ie: acelas, i cuvant poateaparea de mai multe ori.

4 Trimiterea temei

Pentru trimiterea temei se va trimite o arhiva cu:

toate fis, ierele sursa, Makefile care produce executabilul words.Executabilul words va primi doua argumente: numele fis, ierului de intrare

(cu testele) s, i numele fis, ierului de ies, ire.

4.1 Fis, ierul de intrare

Fis, ierul de intrare va cont, ine pe prima linie numele fis, ierului cu textul pebaza caruia se va construi graful de cuvinte.

3

Pe linia a doua se va gasi un numar L. Pe urmatoarele L linii se vor gasicate doua cuvinte ce formeaza o sintagma. Pentru fiecare pereche de cuvintetrebuie scris n fis, ierul de ies, ire costul arcului dintre ele (cerint,a 1).

Pe linia 2 + L + 1 se va gasi un numar M . Pe urmatoarele M linii sevor gasi cate doua cuvinte. Pentru fiecare dintre acestea trebuie afis,ata frazacorespunzatoare drumului de cost minim dintre acestea (cerint,a 2).

Pe linia 2 +L+ 1 +M + 1 se va gasi un numar N . Pe urmatoarele N liniise vor gasi cate un numar n s, i un cuvant w. Pentru fiecare dintre acestea sevor scrie n fis, ierul de ies, ire propozit, iile de cost minim de dimensiune n ce setermina cu w.

Vezi exemplu n Sect, iunea5.2.

4.2 Fis, ierul de ies, ire

Fis, ierul de ies, ire va avea L linii pe care se va gasi cate o valoare reala cores-punzatoare costului arcului descris la linia 3 l 2 + L.

Urmatoarele M linii corespund frazelor construite pentru drumul de costminim ntre cuvintele date pe linia 2 +L+ 2 m 2 +L+ 1 +M n fis, ierulde intrare.

Pentru cerint,a de la bonus, se vor produce N grupuri de linii, fiecareavand urmatoarea component, a: o linie cu numarul soln de solut, ii, urmatede soln cu frazele respective.

Vezi exemplu n Sect, iunea5.3.

5 Exemplu

5.1 Graful de cuvinte

Fie fis, ierul text1:

Fisier de test...

...cu cinci linii de test,

...linii scurte,

...linii foarte scurte,

...linii SCURTE de test!

Cele 8 cuvinte din graf vor fi: fisier, de, test, cu, cinci, linii, foarte,scurte.

4

Sunt n total 16 bi-grame (sintagme formate din doua cuvinte). Pentru acalcula costul arcului linii scurte, calculam ntai matricea de contingent, apentru acea bigrama.

V = scurte V 6= scurteU = linii O11 = 2 O12 = 2U 6= linii O21 = 1 O22 = 11

Scorul OddRatio va fi:

OddsRatio(wordA, wordB) = log (O11 + 0.5) + log (O22 + 0.5)

log (O12 + 0.5) log (O21 + 0.5)= log (2.5) + log (11.5) log (2.5) log (1.5) = 2.06388

Pentru celelalte sintagme

Sintamga OddRatio

fisier de -2.78501de test 5.24175test linii 1.18958test cu 3.3673cu cinci 4.5326cinci linii 2.37158linii foarte 2.37158linii scurte 2.03688linii de 0.587787scurte de 1.01523scurte linii 2.03688foarte scurte 2.78501

Tabela 1: Masura OddRatio calculata pentru toate bigramele din text1

Cea mai mare valoare corespunde sintagmei detest s, i aceasta va fi folositapentru calculul costului arcelor:

Cost(linii, scurte) = 5.24175 2.03688 + 1 = 4.20487

5

scurte

sier

cinci

de

testfoarte

linii cu

3.456

5.22652

5.65396

5.052162.87445

1

4.204874.20487

3.45674

3.456

3.870171.70915

Figura 1: Graful corespunzator fis, ierului text1

5.2 Fis, ierul de intrare

data/text1

6

fisier de

linii scurte

foarte scurte

test linii

de test

scurte de

2

fisier scurte

scurte test

1

5 test

5.3 Fis, ierul de ies, ire

3.45674

4.20487

3.45674

5.05216

6

15.22652

fisier de test linii scurte

scurte de test

1

cu cinci linii de test

7

Pe scurt...Graful de cuvinteCerinteCerinta 1 : Construirea grafului de cuvinteCerinta 2: Construirea unei frazeBonus: Fraze de lungime fixa

Trimiterea temeiFisierul de intrareFisierul de iesire

ExempluGraful de cuvinteFisierul de intrareFisierul de iesire