Određivanje sličnosti između dva teksta

[Ilija Studen]

Evo ga interesantan problem. Treba da napravim RSS agreagator koji će pored klasičnog sakupljačkog zadatka imati i zadatak da uz vest koju trenutno gledamo prikaže i "srodne" vesti.

Da li je neko radio nešto slično ili ima ideju kako bi ovo moglo da bude urađeno, a da pruža zadovoljavajuće rezultate?

[kaizen]

Evo ga interesantan problem. Treba da napravim RSS agreagator koji će pored klasičnog sakupljačkog zadatka imati i zadatak da uz vest koju trenutno gledamo prikaže i "srodne" vesti.

Da li je neko radio nešto slično ili ima ideju kako bi ovo moglo da bude urađeno, a da pruža zadovoljavajuće rezultate?

Tagovi?

[Ilija Studen]

Tagovi? Ne bi radilo posao. Pre nešto:

print compare_this($text1, $text2);

I da ispiše neku vrednost, procenat, neka konstanta, whatever. Onda bi za srodne uzimao one tekstove koji imaju najvišu sličnost, a pri tom su veći od unapred definisanog faktora (npr. 5% ili šta već).

[robi-bobi]

http://bg2.php.net/manual/en/function.similar-text.php
:D

edit: long live PHP :)

[Dragi Tata]

Određivanje sličnosti između dva teksta

Za sličnost dva stringa (kao u diff komandi, npr) se obično koristi LCS algoritam ( http://www.ics.uci.edu/~eppstein/161/960229.html ), ali mi se čini da ti tražiš maltene IR: http://www.dcs.gla.ac.uk/~iain/keith/ a to je mnogo kompleksnija oblast.

[kaizen]

Tagovi? Ne bi radilo posao. Pre nešto:

print compare_this($text1, $text2);

I da ispiše neku vrednost, procenat, neka konstanta, whatever. Onda bi za srodne uzimao one tekstove koji imaju najvišu sličnost, a pri tom su veći od unapred definisanog faktora (npr. 5% ili šta već).

"Srodnu vest" nećeš pronaći poređenjem sličnosti teksta.

edit: ne bi bilo loše da definišeš "Srodnu vest", pošto su za mene srodne vesti :
1 - Zvezda ispala iz Kupa UEFA,
2 - Partizan ide dalje

[dinke]

Za slicnost izmedju dve reci ja sam ranije koristio levenshtein (http://www.php.net/manual/en/function.levenshtein.php) f-ju.

Medjutim, obzirom da i sam imam slican zadatak na svom rss projektu, a rss feedove cu cuvati u bazi, najverovatnije cu koristiti mogucnosti full text indexa. Nisam 100% siguran, ali mislim da su na es-u tako odradili "flashback linkove" (srodne teme).

[Ilija Studen]

najverovatnije cu koristiti mogucnosti full text indexa

Može više detalja o ovom pristupu?

[dinke]

I ja tek trebam da ga proucim. U principu koristi se takozvani 'query expansion' search. Pogledaj ovu stranu (http://dev.mysql.com/doc/refman/5.0/en/fulltext-query-expansion.html) manuala za neke osnovne informacije.

A mozes da probas i da googlas. Kljucne reci mysql fulltext related post :)

E sad, znam da su istu tehniku koristili na es-u, pa ako je flajko (Aleksandar.Ilic) upucen u detalje moze da nam tacno kaze, ako ne kopacemo dalje :)

[ivanhoe]

ja bih napravio tabelu reci (keyworda) za svaki text, i onda matchovao preko toga, 2 texta sa puno slicnih reci su verovatno i slicne tematike.

Naravno da bi ovo imalo smisla treba eliminisati reci koje se pojavljuju samo jednom (nisu bitne) ili opet suvise cesto u textu, zatim one koje se pojavljuju u vise od npr. 50% textova (tako to radi i fulltext search u mysql-u), kao i napraviti neku listu reci koje se zanemaruju i onih kojima se daje veca vaznost (npr. ajax je bitna kategorija za slicnost, a reci kao interface ili button nisu toliko).

U svakom slucaju nije bas lak posao...

[jablan]

Ja koliko kontam, nevezano za konkretne xxSQL funkcionalnosti, generalni princip je sledeći:
Dva teksta su slična ako imaju što više međusobno istih, a u isto vreme "retkih" reči, gde su retke reči one koje se pojavljuju u malom procentu svih tekstova.

Dakle, imaš negde indeks svih reči sa brojem pojavljivanja u svim tekstovima. Što je taj broj veći, reč je manje relevantna za uparivanje pri određivanju sličnosti.

Kad imaš takav indeks, određivanje "razdaljine" dva teksta svodi se na sabiranje i množenje.

E sad, da li sam ti pomogao ili ne, ne znam... :)

//edit: vidim da me Ivanhoe pretekao sa sličnim predlogom

[zira]

Osnovno pitanje je sta ti je izvor tih podataka koje poredis po slicnosti. Ukoliko je nesto sto ti mozes da kontrolises, onda radis ovako kako je ivanhoe rekao ili rucno tagujes.

No, ako nemas pojma sta ce da bude u tom tekstu, kao sto je slucaj sa tim RSS-ovima, onda bolje da koristis MySQL full text search, i da ga fino podesis, posebno se igrajuci sa "score" parametrom koji on vrati kao rezultat. U vecini slucajeva ovo daje dobar rezultat, ali naravno, to nije vjestacka inteligencija i imaces false positives. Ali vecinom, to radi kako treba, pogotovo ako su ti tekstovi duzi. I da, ovo radi samo na MyISAM tabelama.

http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html

(Tip: pogledaj i Fine Tuning i Stopwords)

[marinowski]

Ovaj zadatak nije nimalo lagan. Ko pocne da se zabavlja sa ovom temom, nakon nekog vremena stigne do semantike i do Information Retrievala, kao sto rece Dragi Tata. A ove oblasti dosta zavise od toga koliko se stiglo u istrazivanju u pojedinom jeziku. Ako je predlozen problem za engleski jezik, sto pretpostavljam da jeste, onda OK, jer se u engleskom stiglo najdalje.

FullText search u MySQL-u izgleda interesantno. Da li ga je neko koristio u produkciji? Pitanje je sta da se postavi kao search string u ovom konkretnom slucaju? Samo naslov, ili citav tekst? Koliko search string moze biti dugacak, i koliko se gubi na performansama kada se stavi poduzi tekst, a tekstovi u RSS-u znaju da budu dugacki.

Ukoliko je nekome hendikep sto fulltext radi samo na MyISAM tabelama, moze da se napravi sledece: napravi se replikacija baze, iako je original tabela u InnoDB formatu, kopija moze biti u MyISAM i onda se fulltext search radi na replikaciji baze.

[ivanhoe]

u sustini je "prepoznavanja slicnosti" neka vrsta implementacije neuralnih mreza, pa bi mozda vredelo malo procitati i o tome.

[Petar Marić]

Ako sam naučio jednu stvar o neuronskim mrežama to je da se ne oslanjaš puno samo na njih - jedan pogrešan podatak u skupu za učenje i ode aproksimacija dođavola.