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:
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.
Oj daaawnoo mnie tu nie było. Ale wakacje to był czas dużej liczby intensywnych wyjazdów i tak naprawdę, dopiero jakoś… Read More
Cześć! Zapraszam na krótkie podsumowanie kwietnia. Wyjazd do Niemiec A dokładniej pod granicę z Francją. Chrześnica miała pierwszą komunię. Po… Read More
Ostatnio tygodnie były tak bardzo wypełnione, że nie udało mi się napisać nawet krótkiego podsumowanie. Więc dziś zbiorczo podsumuję luty… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W styczniu przeczytałem "Homo Deus: Historia jutra". Książka łudząco podoba do wcześniejszej książki tego… Read More
Cześć! Zapraszam na podsumowanie roku 2023. Książki Zacznijmy od książek. W tym roku cel 35 książek nie został osiągnięty. Niemniej… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W grudniu skończyłem czytać Mein Kampf. Nudna książka. Ciekawsze fragmenty można by było streścić… Read More