Wstęp

Czy zastanawialiście się kiedyś, skąd wyszukiwarki „wiedzą”, co użytkownik miał na myśli pomimo popełnionych literówek w wyszukiwanym haśle? Odpowiedzią są algorytmy obliczające miarę odmienności napisów. W tym artykule, postaram się omówić jeden z nich, jak również spróbować zoptymalizować go tak, aby był bardziej użyteczny dla rozwiązań informatycznych.

Odległość Levenshteina

Odległość Levenshteina – bo o tym algorytmie dzisiejszy wpis będzie – jest to prosty algorytm wyznaczający miarę odmienności napisów, czyli w uproszczeniu wyznacza ilość operacji prostych, które muszą zostać wykonane, aby słowo A stało się słowem B. Operacja prosta, w tym przypadku to:

• wstawienie nowego znaku
• usunięcie znaku
• podmienienie znaku

Dla zobrazowania, aby napis „kot” stał się napisem „mol” potrzebujemy wykonać 2 operacje proste – zamienić literkę „k” na „m” oraz „t” na „l”. Więc miara odmienności słowa „kot” i „mol” jest równa 2.

Algorytm

Jak więc nauczyć komputer, aby też potrafił rozpoznawać tę różnicę w słowach? Władimir Lewensztejn zaproponował poniższy algorytm:

1. Określamy długość badanych słów, długość słowa głównego A to `m`, a długość słowa porównywalnego B to `n`.

2. Tworzymy macierz(tablicę) `K` o wymiarach (m+1) x (n+1) .

3. Pierwszy wiersz macierzy wypełniamy wartościami od 0 do `n`

4. Pierwszą kolumnę macierzy wypełniamy wartościami od 0 do `m`

5. Dla każdego znaku słowa A wykonaj (od 1 do `m`, ozn. Indeksu `i`):

6. Dla każdego znaku słowa B wykonaj (od 1 do `n`, ozn. Indeksu `j`):

◦ jeżeli `A[i]` jest taki sam tak `A[j]` to koszt jest równy zero, w przeciwnym wypadku koszt jest równy 1
◦ przypisujemy wartość pola macierzy `K[i][j]` obliczając minimalną wartość z:
▪ `K[i – 1][j – 1]` + koszt
▪ `K[i – 1][j]` + 1
▪ `K[i][j – 1]` + 1

7. Miarą odmienności jest wartość wpisana w `K[m][n]`

Stosując powyższy algorytm, przeanalizujmy słowa „kot” i „pole”:

1. Długość słów m → 3, n → 4

2. 3. 4. Tworzymy macierz z wypełnionymi wartościami.

5. Obliczamy wartości macierzy.

Znak P różni się od K więc koszt jest równy 1. Obliczamy wartości:

• `K[2 – 1][2]` + 1 = 2

• `K[2][2 – 1]` + 1 = 2

• `K[2 – 1][2 – 1]` + 1(koszt) = 1

Najmniejsza wartość to 1, więc tyle wpisujemy w pole `K[2][2]`.

Podobnie uzupełniamy resztę wartości z wiersza.

W tym przypadku znaki się od siebie nie różnią, więc koszt jest równy 0. Więc:

• `K[3 – 1][3]` + 1 = 3

• `K[3][3 – 1]` + 1 = 3

• `K[3 – 1][3 – 1]` + 0 = 1

I wpisujemy w pole `K[3][3]` wartość 1.

Implementacja

Implementacja algorytmu jest wkompilowana w interpreter PHP od wersji 4.0.1. Na potrzeby testów i optymalizacji zaimplementowałem go i można znaleźć go w repozytorium: https://gitlab.com/dysan12/levenshtein_distance

Optymalizacja

Wykonując krokowo algorytm, możemy zauważyć pewną zależność, dzięki której nie musimy wykonać wszystkich obliczeń, aby szacować odmienności podanych napisów. Wystarczy, że przy graficznej interpretacji „poprowadzimy” ukośną linię z wynikowego narożnika macierzy.

W tym wypadku, już po uzupełnieniu pierwszego wiersza, wiemy że odmienność napisów, będzie wynosiła co najmniej 2.

Szacunek ten możemy przykładowo wykorzystać w sytuacji, gdy chcemy poznać wszystkie słowa z pewnego zbioru, których odmienność od badanego słowa nie będzie większa od zadanej.

Implementacja

Przyjmując kontynuację algorytmu krokowego oraz , że `max` to zadana maksymalna różnica słów:
Dodajemy do każdej iteracji kroku piątego warunki kończące wykonywanie

• jeśli porównywane słowa mają taką samą długość, to sprawdź czy wartość `K[i][j]` > `max`
• jeśli słowo porównywane B jest dłuższe niż słowo główne A, to sprawdź czy wartość `K[i][i + n – m]` > `max`
• jeśli słowo porównywane B jest krótsze niż słowo główne A, to sprawdź czy wartość `K[i][i – (n – m)]` > `max`

Jeśli algorytm przedwcześnie zakończył swoją pracę, tzn. że badane słowa zbyt różnią się od siebie.

Ilustracja 1: Optymalizacja zrealizowana w PHP

Wyniki

Testy zostały przeprowadzone na ponad 1000 elementowym zbiorze porównywanych słów z wyznaczoną maksymalną odległością od 0 do 10.

Aspekty:

• zoptymalizowany algorytm vs algorytm bez optymalizacji
• zoptymalizowany algorytm vs wbudowany w PHP(bez optymalizacji)

Gdzie:

• „Optimized algorithm time” to czas wykonania zoptymalizowanego algorytmu
• „Standard algorithm time” to czas wykonania algorytmu bez optymalizacji
• „Saved time” to zaoszczędzony czas
• „Percentage ratio” to stosunek czasów. Jeśli wartość jest mniejsza niż 100% to zoptymalizowany algorytm wykonywał się dłużej.

Zoptymalizowany algorytm vs algorytm bez optymalizacji

Z wyników widzimy, że optymalizacja, przy niskiej zadanej maksymalnej odległości, polepsza do 212% wydajność co daje ponad dwukrotnie skrócony czas obliczania.

Zoptymalizowany algorytm vs wbudowany w PHP(bez optymalizacji)

Wbudowana funkcja obliczania odległości levenshteina jest skompilowana w interpreter PHP, przez co wydajnościowo jest niejednokrotnie ponad 80 razy szybsza niż nieskompilowany algorytm – co nie było zaskoczeniem.

Wszystkie testy wraz z badanym zbiorem danych znajdują się w
https://gitlab.com/dysan12/levenshtein_distance/blob/master/test/LevenshteinTest.php

Podsumowanie optymalizacji

Z przeprowadzonych testów widzimy, że optymalizacja rzeczywiście skraca czas wykonania algorytmu, lecz aby z niej w praktyce skorzystać w języku interpretowanym, musielibyśmy wkompilować ją w interpreter.

Autorem tekstu jest Michał Gaj.