Sličnost rečenica

[bluesman]

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?

[bags]

A da koristite tagove ?

[bluesman]

A ko ce da tagira? Sve mora automatski da radi.

[zira]

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

[Dragi Tata]

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.

[Dragi Tata]

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?)

[kodi]

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)

[zira]

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.

[jablan]

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).

[nixa]

Koliko sam ja razumeo bluesmana, ovo se ne radi za srpsko tržište ...