Odległość Levenshteina
Dzisiejszy artykuł przyda się nie tylko programistom PHP. Myślę, że informacje w nim zawarte będą pomocne i dla pozostałych programistów :). Postanowiłem opisać algorytm Levenshteina.
Opis algorytmu
Algorytm Levenshteina, służy do liczenia odległości edycyjnej. Jest to najmniejsza liczba działań prostych, przeprowadzająca jeden napis w drugi.
Działania proste to:
- wstawienie nowego znaku
- usuniecie znaku
- zamiana na inny znak
Jak działa algorytm?
- Ustala długość łańcuchów znaków (n – długość łańcucha pierwszego, m – długość łańcucha drugiego),
- Tworzy macierz o rozmiarze (n+1) x (m+1),
- Inicjalizuje pierwszy wiersz wartościami od 0 do n,
- Inicjalizuje pierwszą kolumnę wartościami od 0 do m,
- Sprawdza każdy znak z łańcucha pierwszego (indeks i od 1 do n),
- Sprawdza każdy znak z łańcucha drugiego (indeksy j od 1 do m),
- jeżeli znak na pozycji i równa się znakowi na pozycji j. to koszt jest równy zero,
- jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1,
-
Ustala 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 otrzymamy w komórce o indeksie n, m.
Przykład
Sprawdźmy działanie algorytmu na przykładzie dwóch łańcuchów: "kod" i "dom". Poniżej utworzyłem macierz i obliczone zostały odpowiednie wartości komórek.
Odległość Levenshteina dla tego przykładu wynosi 2. Odczytuje się wartość z komórki o indeksie m i n.
Zastosowanie
W świecie webowych technologii widzę jedno bardzo przydatne zastosowanie tego algorytmu – w inteligentnej wyszukiwarce.
Dość często pisząc na klawiaturze robimy literówki. Wykorzystując ten algorytm możemy podpowiedzieć użytkownikowi o co mu chodziło.
Jest to szczególnie istotne w sklepie internetowym. Jeżeli potencjalny klient pomyli się przy wpisywaniu nazwy produktu i tego nie zauważy, pójdzie do konkurencji. Jeżeli system zauważy błąd i podpowie co należy wpisać, klient zostanie u nas :)
Implementacja
function levenshtein($string1,$string2) { $m = strlen($string1); $n = strlen($string2); $values=array(); for($i=0;$i<=$m;$i++) $values[$i][0] = $i; for($j=0;$j<=$n;$j++) $values[0][$j] = $j; for($i=1;$i<=$m;$i++) { for($j=1;$j<=$n;$j++) { $cost = ($string1[$i-1] == $string2[$j-1])?0:1; $values[$i][$j] = min($values[$i-1][$j]+1,$values[$i][$j-1]+1,$values[$i-1][$j-1]+$cost); } } return $values[$m][$n]; }
PHP posiada wbudowaną funkcję do obliczania odległości Levenshteina. Przeczytasz o niej w manualu.