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?

1. Ustala długość łańcuchów znaków (n – długość łańcucha pierwszego, m – długość łańcucha drugiego),
2. Tworzy macierz o rozmiarze (n+1) x (m+1),
3. Inicjalizuje pierwszy wiersz wartościami od 0 do n,
4. Inicjalizuje pierwszą kolumnę wartościami od 0 do m,
5. Sprawdza każdy znak z łańcucha pierwszego (indeks i od 1 do n),
6. Sprawdza każdy znak z łańcucha drugiego (indeksy j od 1 do m),
7. jeżeli znak na pozycji i równa się znakowi na pozycji j. to koszt jest równy zero,
8. jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1,
9. 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.
10. 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.