post_ico5

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.

Przykład algorytmu Levenshteina

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.

Co sądzisz o wpisie?
BeżnadziejnySłabyŚredniDobryBardzo dobry (1 głosów, średnia ocen: 5,00 z 5)
Loading...
  • Czy mógłbyć przedstawić najbardziej optymalny sposób przedstawienia użytkownikowi propozycji „Did you mean..” – gdy wpisze błędną nazwę produktu a katalog zawiera np 100000 produktów.
    Chodzi mi o algorytm postępowania, ew. cachowanie.

    • Wydaje mi się, że najlepiej pobrać wszystkie nazwy produktów i w pętli obliczać odległość. Potem wyświetlić użytkownikowi tylko produkty o odległości 1 lub 2.

      W celu optymalizacji najlepiej użyć cache do zapytania pobierającego wszystkie produkty. Sam algorytm nie jest zbyt złożony, raptem O(m*n).

      Jeżeli skrypt będzie „zamulać” można mechanizm usprawnić trzymając już gotowe wyniki dla najpopularniejszych haseł.

    • No Name

      W przypadku dużych projektów, które korzystaja z dużych zestawów danych (a szczególnie jeśli chcielibyśmy mieć też autocomplete) ja bym raczej pomyślał o zastosowaniu specjalnego serwera do przeszukiwania, np. Sphinxa (http://sphinxsearch.com/about/sphinx/).