Algorytm Levenshteina w PHP (podobne wpisy w mysql)

Władimir Lewensztejn to twórca tzw. „odległości Levenstheina” – czyli miary tego, jak bardzo podobne są do siebie dwa ciągi. Algorytm Levenshteina oblicza własnie wartości odległości Levenshteina – czyli ilość operacji prostych (usunięcie, dodanie, podmiana znaku) potrzebnych do transformacji jednego ciągu w inny.

Stosuje się go chociażby do wyszukiwania plagiatów czy analizie DNA.

Najczęstszą metodą implementacji jest użycie programownia dynamicznego. Czyli dzielimy problem N na mniejsze problemy n. Zapamiętuje się rozwiązania podproblemów w tablicy co wyklucza ewentualność liczenia tego samego więcej niż raz.

Algorytm tworzy macierz o wymiarach długość1ciągu+1 x długość2ciągu+1 w wyniku czego, dla słow mama i rama mamy:

 0

1

2

3

4

1

1234

2

2123

3

2212

4

3221

z czego indeksy tablicy oznaczają kolejne litery tych dwóch ciagów.

Kolejne kroki:

  1. Sprawdzamy każdy znak z łańcucha pierwszego (indeks i od 1 do długość1ciągu).
  2. Sprawdzamy każdy znak z łańcucha drugiego (indeksy j od 1 do długość2ciągu).
  3. Jeżeli znak na pozycji i równa się znakowi na pozycji j to koszt jest równy zero czyli jeśli 1 litera 1 ciągu jest identyczna z 1 literą 2 ciągu to koszt jest równy 0,
  4. Jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1.
  5. ustawiamy wartość komórki i,j jako minimum:
  • komórka powyżej + 1,
  • komórka z lewej + 1,
  • komórka po skosie (góra, lewo) + koszt.

Algorytm powtarzamy dla wszystkich znaków, całkowity koszt (szukana odległość Levenshteina) otrzymamy w komórce o indeksie [długość1ciągu][ długość2ciągu].

Przejście algorytmu dało nam wynik 1.Co jest prawdą bo żeby przejść ze słowa mama do słowa rama wystarczy wykonać 1 operacje prostą – zmienić pierwszą literę, gdyż reszta się zgadza.

Ale popatrzmy na studium przypadku. Mamy bazę danych. W jednej tabeli mamy zebrane np nazwy hoteli turystycznych. Wiemy, że bazę danych uzupełniali różni ludzie w tym samym czasie, więc jest możliwość występowania duplikatów. Baza liczy powiedzmy 5000 wpisów – co dość znaczaco utrudnia zwykłe przeglądanie wpisów w PhpMyAdmin… No chyba że chcesz sobie zając troche czasu :) Załóżmy, że zmienna $e jest tablicą w której mamy pobrane dane z interesującej nasz tabeli bazy danych.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
foreach($e as $t){//lecimy po wszystkich wartosciach

foreach($e as $o){// bedziemy porownywac kazda z wartosci z kazda z wartosci tej samej tabeli.
if(levenshtein(ciach($t->tresc, 255), ciach($o->tresc,255))<4 and $t->tresc[1]==$o->tresc[1] and $o->id != $t->id )

{//jesli długosc levenshteina jest mniejsza 0d 4 (wpisy bardzo podobne), jesli nie sa równe, tzn bez porównywania

//samych ze sobą i dla mnie było wygodne sprawdzenie 1 litery, ale to jest opcjonalne.

echo '<a href="?us='.$t->id.'">'.$t->id.'</a> podobne jest do <a href="?us='.$o->id.'">'.$o->id.'</a><br>czyli:<span style="color:red;">'.$t->tresc.' <u style="color:green;">podobne</u> do '.$o->tresc.'</span><br>';

//wyswietlamy podobne wpisy. Tutaj sa one z linkiem, ktory umozliwie ich od razu usuniecie ich.
}
}
}

Warto żebym dodał – tutaj użyłem funkcji ciach(); która po prostu skraca tekst do 255 znaków, gdyż funkcja zaimplementowana na stałe w php levenshtein();  ogranicza nas do właśnie tych 255 znaków przy każdym z porównywanych ciągów znaków.

Złożność obliczeniowa tego algorytmu nie jest zbyt efektywna ze względu na pętle – O(długosć1ciągu * długość2ciągu). Ogólnie jest to dość kosztowny algorytm. Dla jasności, u mnie przy jakiś 10 000 wpisach skrypt wykonywał się około 100 sekund – procesor mam Intel Core2Duo 1,8GHz i 2 GB pamięci ram.

Dzięki za wizytę,
Mateusz Mazurek
Podziel się na:
    Facebook email PDF Wykop Twitter

Dodaj komentarz

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subskrybuj  
Powiadom o