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.
Cześć! W Pythonie 3.13 dodano JITa! JIT, czyli just-in-time compiler to optymalizacja na która Python naprawdę długo czekał. Na nasze… Read More
Cześć! Zapraszam na podsumowanie roku 2024. Książki W sumie rok 2024 był pod względem ilości książek nieco podobny do roku… Read More
Podtrzymując tradycję, prawie regularnych podsumowań, zapraszam na wpis! Nie mogło obyć się bez Karkonoszy We wrześniu odwiedziłem z kolegą Karkonosze,… Read More
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