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 |
1 | 2 | 3 | 4 |
|
2 |
2 | 1 | 2 | 3 |
|
3 |
2 | 2 | 1 | 2 |
|
4 |
3 | 2 | 2 | 1 |
z czego indeksy tablicy oznaczają kolejne litery tych dwóch ciagów.
Kolejne kroki:
- Sprawdzamy każdy znak z łańcucha pierwszego (indeks i od 1 do długość1ciągu).
- Sprawdzamy każdy znak z łańcucha drugiego (indeksy j od 1 do długość2ciągu).
- 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,
- Jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1.
- 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.
Mateusz Mazurek
