Algorytm podobienstwa Opcje

[nospor]

Znacie jakieś w miare dobra algorytmy na znajdywanie podobienstwa dwóch nazwa składających się z wielu wyrazów?

Podobienstwo na zasadzie:
kapitaliki,
jedno slowo podobne
edna litera inna,
znaki interpunkcyjne inne

Najlepiej jakby dało się do zrobić na poziomie zapytania do bazy. Jak nie to obróbka w php.

[r4xz]

Może algorytm Levenshtein distance, nawet znajdzie się coś do tego w sql (nie sprawdzałem jak działa). Nigdy też tego nie implementowałem, a więc moja wiedza jest czysto teoretyczna (więc pewnie i znikoma) na temat tego algorytmu, ale spróbować zawsze warto.

[nospor]

No właśnie ta nazwa mi coś chodziła po głowie (IMG:style_emoticons/default/smile.gif)
Dzięki za linki, jak już coś mi się uda zrobić dam znać.

Jak zwykle jeśli ktoś ma coś do dodania to zapraszam (IMG:style_emoticons/default/smile.gif)

[redeemer]

http://php.net/manual/en/function.levenshtein.php

@nospor: piszesz ceneo2? :-)

[nospor]

Nie, nie piszę ceneo2 (IMG:style_emoticons/default/smile.gif) Widzę łączysz wątki (IMG:style_emoticons/default/wink.gif)

No dobra, ale sam levenshtein nie da rezultatow, jakie oczekuje.

Zalozmy ze porownuje slowa:
echo $lev = levenshtein('Blabla', 'Blabla sp zoo');
echo $lev = levenshtein('Blabla', 'Bleble');

To wg lev, blizsze mi bedzie Bleble, podczas gdy wg mnie bliższe ma byc Blabla sp zoo. Trzeba będzie albo wzbogacić algorytm o levenshteina i cos jeszcze lub moze jest coś jeszcze innego?

[redeemer]

Może jakoś zmixować to z https://en.wikipedia.org/wiki/Hunt%E2%80%93McIlroy_algorithm

[pyro]

Proponuję najpierw sprecyzować jakiego podobieństwa albo przynajmniej przybliżonego algorytmu jakiego oczekujesz oraz przykłady I/O jakich byś oczekiwał rezultatów, bo "chcę jakieś określanie podobieństwa, dostałem levenshtein, ale nie o takie podobieństwo mi chodziło" naprawdę nie mówi absolutnie nic (IMG:style_emoticons/default/wink.gif)

[nospor]

@pyro tak masz racje. Sam czekam jeszcze na konkretne przykłady. Chciałem jednak w miedzyczasie zasięgnąć już jakieś teorii (IMG:style_emoticons/default/smile.gif)

[sazian]

$p=0;
similar_text("Blabla","Blabla sp zoo",$p);
var_dump($p);
daje 63%

similar_text("Blabla","Blable",$p);
var_dump($p);
daje 83%

[nospor]

@sazian, tak, juz testowalem tez similar text. Jak dostane konkretne dane to bede testowal najlepsze rozwiązanie (IMG:style_emoticons/default/smile.gif)

edit: dobra, dzieki panowie. Mix levensteina z rozbijaniem na słowa działa niemalże idealnie. Na jakies 95% (IMG:style_emoticons/default/smile.gif)

[aniolekx]

to może pochwal się dokładnym rozwiązaniem ¬¬

[nospor]

Ok, postaram sie po weekendzie przygotowac paczke (IMG:style_emoticons/default/smile.gif)



edit:
https://github.com/nospor/similarity

[kilab]

Dzięki @nospor za paczkę, robi dobrą robotę (IMG:style_emoticons/default/smile.gif)

Ja akurat właśnie muszę zrobić odnajdywanie podobnych słów, ale na poziomie bazy i korzystając z okazji, że temat w offtopie, mam do was pytanie. Najwyżej zgarnę srogie baty (IMG:style_emoticons/default/biggrin.gif)

Otóż tak. Mam dwie identyczne bazy w MySQL i PostgreSQL na których badam wydajność żeby ostatecznie po tygodniach testów pozostać na MySQL lub przejść na PostgreSQL.
Do MySQL dodałem funkcję wykorzystującą algorytm levenshteina znalezioną tu: http://stackoverflow.com/questions/1390988...nction-in-mysql która działa, ale przy tabeli 40 tys. rekordów wykonanie najprostszego zapytania wykorzystującego tę funkcję trwa ok 15 s. Docelowo ma on działać na trochę większej tabeli, ok. 250 tys. rekordów więc rozwiązanie raczej marne. Na ogromny plus wychodzi w tej sytuacji PostgreSQL, w którym wykonanie zapytania wykorzystującego funkcję levenshteina z modułu fuzzystrmatch trwa zaledwie 0,5 s. na takiej samej liczbie rekordów (40 tys.).

No i to pytanie docelowe - czy to wydaje się być realne i normalne, że różnica czasu w wykonaniu bardzo podobnych do siebie zapytań na dwóch tych bazach jest taka duża?

[nospor]

Skoro w PostgreSQL korzystasz z gotowej wbudowanej biblioteki to tak, jest duża szansa że bedzie działać ona szybciej niż jakiś kod napisany przez kogos w necie.

Też chciałem robić to na poziomie bazy. Jednak szybko się okazało, że sam levenshtein jest niewystarczający, wiec musiałem się przerzucić na php.
Moge dodać, że sprawdzenie ponad 200tys tekstow trwa około 5 sekund

[com]

skoro w hydeparku to pozwolę sobie na mały offtop ta bółka przez ó to mnie razi (IMG:style_emoticons/default/tongue.gif) a tak generalnie możesz dorzucić na stopkę, może się komuś przydać (IMG:style_emoticons/default/biggrin.gif)

[nospor]

Z tą bółką to na tym polegał dowcip (IMG:style_emoticons/default/biggrin.gif)

[com]

hahaha ok (IMG:style_emoticons/default/biggrin.gif) znaczy się wiedziałem, że to dla jaj napisane ale rzuciło mi się strasznie w oczy (IMG:style_emoticons/default/wink.gif)

[Crozin]

Skoro będziesz tego potrzebował do jakiegoś wyszukiwania to dlaczego nie skorzystasz z narzędzi do wyszukiwania, np. SOLR/ElasticSearch (oba działają na Lucene)? Przygotowując odpowiednie indeksy, które będą działały na znormalizowanych wyrazach otrzymasz dużo lepsze wyniki.

Ten post edytował Crozin 17.02.2015, 13:33:32

[Pyton_000]

Ale Ty @com jesteś łatwowierny ;P @nospor zrobił byka i żeby się obronić napisał że niby celowe (IMG:style_emoticons/default/wink.gif) A że Mod to trzeba się zgadzać ;P I Banik ;D

[nospor]

@Crozin tam gdzie to wrzucam, nie miałem dostępu do Lucene
@Pyton prorok jak czy co.... (IMG:style_emoticons/default/biggrin.gif)

[com]

no dlatego przyznałem mu rację proroku (IMG:style_emoticons/default/tongue.gif) no a tak bardziej pasowało do tego co tam stworzył, wiec niech bd błąd wybaczony (IMG:style_emoticons/default/tongue.gif)

[nospor]

Oj bo pisałem szybko
spółka bółka
i tak fajnie do rymu wyszło (IMG:style_emoticons/default/biggrin.gif)

Dobra, "żart" usunięty, jest już poprawnie (IMG:style_emoticons/default/wink.gif)

[mls]

No ale funkcja clean mogłaby być napisana zdecydowanie prościej (IMG:style_emoticons/default/wink.gif) Pomijając już zamianę polskich literek (bo co, jeśli tam będą umlauty lub inne akcenty?) to te cztery preg_replace można było zastąpić maksymalnie dwoma...

Ogólnie, możnaby uprościć:

[PHP] pobierz, plaintext 
public function clean($text) {
		$text = iconv('utf8', 'ascii//translit//ignore', trim($text));
		$text = preg_replace('#[^a-z0-9]+#', ' ', strtolower($text));
		$text = preg_replace('#[\s]+#', ' ', $text);
		return trim($text);
	}
[PHP] pobierz, plaintext 

(IMG:style_emoticons/default/wink.gif)

Ten post edytował mls 17.02.2015, 14:58:32

[Pyton_000]

GitHub jest Twój (IMG:style_emoticons/default/wink.gif) Fork, pull request i jedziesz (IMG:style_emoticons/default/wink.gif)

[nospor]

@mls masz racje. Jesli moglbys zrobic to co mowi Pyton, to chetnie bym zobaczyl jak sie na githubie zarządza forkami (IMG:style_emoticons/default/smile.gif)

[mls]

@mls masz racje. Jesli moglbys zrobic to co mowi Pyton, to chetnie bym zobaczyl jak sie na githubie zarządza forkami (IMG:style_emoticons/default/smile.gif)

Proszzz:
https://github.com/mlask/similarity
+ pull request na oryginalnym repo (IMG:style_emoticons/default/wink.gif)

Ten post edytował mls 18.02.2015, 00:02:18

[nospor]

@mls a testowales to? Bo mi niestety Twoj kod:

[PHP] pobierz, plaintext 
$text = 'bbbąęśĄĘŚccccc';
echo iconv('utf8', 'ascii//translit//ignore', trim($text));
[PHP] pobierz, plaintext 

zwraca:
bbb?(IMG:style_emoticons/default/questionmark.gif) (IMG:style_emoticons/default/questionmark.gif) ?ccccc

edit: dopiero dodanie setlocale poprawia sprawe

[PHP] pobierz, plaintext 
$text = 'bbbąęśĄĘŚcccccWeiß, Goldmann, Göbel, Weiss, Göthe, Goethe und Götz';
setlocale(LC_CTYPE, 'pl_PL.utf-8');
echo iconv('utf-8', 'ascii//translit', $text);
[PHP] pobierz, plaintext 

[mls]

@mls a testowales to? Bo mi niestety Twoj kod:

Testowałem. Problemem jest w większości przypadków nie do końca prawidłowa biblioteka z której korzysta iconv. Na systemach linuksowych, np. na Ubuntu, używana jest biblioteka "glibc" zamiast poprawnej "libiconv". U mnie działa, bo "mam maka", bo tu standardowo jest libiconv. Ale faktycznie, zapomniałem, że z iconv mogą być problemy. A multibyte_string nie obsługuje transliteracji...

[nospor]

No właśnie...
No nic, dzieki za pull (IMG:style_emoticons/default/smile.gif)