|
Sličnost rečenica
Treba da se upoređuje string proizvoljne veličine, obično oko 100-ak karaktera, sa drugim stringovima u bazi da se nađu slične vesti. Fulltext search iz mysql daje solidne rezultate ali je greška bar 15-20%, PHP manual: similar_text daje mnogo lošije rezultate, probali smo čak i sa PHP manual: levenshtein + još neko dodatno žongliranje, zatim smo probali sa nekim varijacijama na fuzzy search... svako ima delove u kojima je bolji od drugih ali ni jedno rešenje ne daje potpuno zadovoljavajuće rešanje.
Zatim je jedna od ideja da se proba od oba stringa dobiti niz reči i onda uraditi presek niza, naći koliko se reči pojavljuje u oba stringa i za neki treshold, recimo 50% proglasiti kao slično. Tu je problem što to može da se radi samo u PHP, ne može da se odradi query (može jedino da se pokupe svi naslovi pa kroz petlju petljati...) i nije previše elegantno. Najlakše je reći "neka paze šta i kako upisuju" ali je upis van kontrole i ne može da se utiče na način unosa. Recimo Gđa. Backham je nekada Victoria, nekada Posh, nekada Spice Girl... Paris Hilton je nekada samo Paris, nekada Princess a nekada samo "star" (prilično generički... znači jako nepovoljno) Problem je kada se recimo upiše neka vest, na osnovi naslova vesti pronaći u bazi sve vesti koje su vezane na bilo koji način sa ovom trenutnom. Stvar je u tome što sve radi polovično ili malo bolje od polovično, ni jedno rešenje ne može da se ostavi da radi automatski. Da li postoji neki poznati algoritam? |
A da koristite tagove ? :)
|
A ko ce da tagira? Sve mora automatski da radi.
|
Tesko je to automatski, a da bude skoro sigurno pouzdano. Moze poluautomatski, da npr. sistem u pocetku ucite sinonime i povezane pojmove tagujuci, a vremenom ce sistem nauciti dovoljno da to radi skoro automatski. Valjda :)
|
Koliko se sećam već smo nešto pričali na tu temu i Dinke nam je pomenuo PHP funkciju http://us.php.net/levenshtein
Ja sam implementirao ovaj algoritam u C++u i mogu reći da lepo vrši posao. |
Ah, tek sad videh da si probao levenshtein.
Ako ti ni to ne odgovara, jedno od rešenja bi bilo n-grams fuzzy search. Ne znam da li postoji gotova PHP biblioteka za nešto tako. (BTW, šta je sa ovom quick reply opcijom?) |
ako ne mozes vec da nadjes zadovoljavajuci algoritam, onda ostaje ovo sto zira kaze, da istreniras neki postojeci. Mogu to i sami korisnici, a da toga nisi ni svesni (postavis mali checkbox "do you find this results good y/n" ili tako nesto) . Naravno ako projekt to dozvoljava.
Edit: ako je tekst na engleskom, mozda ovo pomogne http://dev.mysql.com/doc/refman/5.0/...functions.html http://en.wikipedia.org/wiki/Soundex (sad izgooglao, nisam koristio) |
Evo implementacije varijante fuzzy search-a u dva koraka, mozes da probas, mozda ti da bolje rezultate.
http://elonen.iki.fi/code/misc-notes/appr-search-php/ Off Topic: Automatika u ovome slucaju ce uvijek grijesiti, nekad manje nekad vise, ali greske ce se uvijek pojavljivati. |
Mislim da čoveku ne treba fuzzy search, već automatsko izvlačenje tagova (ključnih reči). Verovatno ima dosta materijala o tome po netu (recimo Amazon to radi sa knjigama)... Koliko se meni čini, poenta je da se na nekoj ogromnoj bazi tekstova izvlače reči sa velikom frekvencijom unutar jednog teksta, a malom frekvencijom unutar skupa.
U svakom slučaju biće neophodno neko ručno čišćenje na kraju, i s obzorim na flektivnu prirodu srpskog jezika, verovatno bi bilo korisno implementirati neku logiku koja bi bila "padež-proof" (BTW, mislim da je Lucene ima). |
Koliko sam ja razumeo bluesmana, ovo se ne radi za srpsko tržište ...
|
Evo jedan laički algoritam:
Znači zadatak je da za svaki tekst izvučeš desetak tagova čijim upoređivanjem kasnije možeš da nađeš srodne tekstove. Izvučeš tabelu svih reči. Iz nje izbaciš reči koje se pojavljuju često na celom uzorku tekstova (tu su veznici, brojevi, prilozi, većina glagola itd), to jest "procediš". Onda za svaku preostalu reč uradiš jedan fulltext search i zapamtiš ID-jeve tekstova u kojima se pojavljuju i odgovarajući rank. Kad odradiš sve to za sve reči, za svaki tekst uzmeš deset reči sa najvišim rankom i to su tagovi. Isto možeš posle da ponoviš i za fraze od dve, tri itd. reči, s tim što računaš samo fraze čije se sve reči pojavljuju u "proceđenoj" tabeli. Tako bih ja radio i prilično sam ubeđen da bi šljakalo. |
A kako spojiti 'Posh' sa 'Victoria', 'Spice Girls' itd?
|
Citat:
|
Citat:
Random primer (izvinjavam se čitaocima sa slabijim stomakom ;)): http://www.kurir-info.co.yu/Arhiva/2...16122005.shtml |
Posh i Spajs se pominju samo jednom u tekstu, postoji velika verovatnoca da ne bi imali odgovarajucu tezinu za povezivanje sa Viktorijom Bekam, odnosno srodnim clancima.
|
Pa cenim da bi Poš i Spajs upali u prvih 10-20 tagova za ovaj tekst, pogotovu ako se poveća težina reči sa velikim slovom (što je logično za tagove ovakvog tipa). Na kraju krajeva, dovoljno je da imaš ključne reči "Viktorija" i "Bekam" da bi je povezao sa srodnim člancima. Ja bih svakako probao ovaj algoritam pre nego ga otpišem.
|
Mislim da jedino bluesman moze da nam odgovori valja li algoritam :)
|
Jablene, u opstem slucaju hoce, ali u nekom procentu nece, pa to "verovatno" ce mu opet praviti false-positives kao i da radi obicni fulltext search, samo treba vidjeti sa kojim procentom greske.
Ne znam koliko je ta funkcionalnost vazna za Bluzmenov projekat, ako nije pretjerano, neki od ovdje navedenih algoritama ce ti zavristi posao. Ako jeste vazna/osnovna funkcionalnost, onda tu ima dosta posla... Jer nije samo pitanje da se izbace vijesti koje nisu dovoljno slicne, vec (ako je to bitna funkcionalnost) i ne preskoce vijesti koje su bitne i vrlo povezane, ali zbog upotrebe sinonima ili slicno nisu pogodjene obicnim poredjenjem sadrzaja teksta, koji je u ovome slucaju prilicno kratak (100 znakova). Mungos je upravo na ovome problemu zaustavio rad na Momentu, zato sto nije dobijao dovoljno kvalitetne srodne vijesti. |
Da, prevideo sam možda, 100 karaktera je stvarno malo. Kakve su to vesti uopšte?
|
Procenat greske se moze smanjiti ako se analiziraju i clanci sa proverenih izvora (primer: http://www.articlesbase.com, ima vise od 134 hiljade clanaka), pa se kreira neki sistem vezanih keyworda, a baza sinonima bi olaksala posao.
Svejedno, ima tu dosta posla, ako je kvalitet jako bitan, onda jedino rucno dodeljivanje tagova dolazi u obzir. Evo znam neke Indijce koji bi to radili za saku dolara :) |
ta vasa ideja zvuci kao nesto gde bi se mogao uklopiti Bayesov filtar, kao za spam sto se koristi. Nadju se verovatnoce da se neka rec nalazi na odredjenoj poziciji u recenici i verovatnoca da bude u istoj recenici sa drugim recima, pa onda preko toga mogu da se nadju slicne recenice...
e a kad to neko isprogramira da actually radi, onda sjebemo google, postignemo svetsku dominaciju na trzistu SE i otkupimo donesi.com za 2 milijarde dolara... :D |
Pre obradjivanja recenica dobro je recenicu (ako je na engleskom) provuci kroz Porter Stemming algoritam, koji reci 'oslobadja' nastavaka i mnozine.
Odredjivanje semantike reci koje se koriste je vrlo tezak problem, nesto se moze postici koristeci WordNet, ali pitanje koliko. Mislim da je najpametnije da pustite da 'raja' radi za vas, tagovanje je popularno, iz nekog razloga svi vole da taguju. |
| Vreme je GMT +2. Trenutno vreme je 20:51. |
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.