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.

[nixa]

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

[jablan]

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.