Odległość Levenshteina przy porównywaniu ciągów znaków
Zwykłe porównywanie stringów czy to w php czy asp, sprowadza się do porównywania napisów znak po znaku i wyniku w postaci true lub false. Czasami jednak potrzebujemy porównać napisy powołując się nie na ich bezpośrednią równość, ale na ich podobieństwo.
Jednym z prostszych algorytmów, który pozwoli nam na zbadanie podobieństwa dwóch ciągów znaków jest algorytm Levenshteina, określający tzw. odległość Levenshteina.
Algorytm w oparciu o zdefiniowane wcześniej operacje proste (np. wstawienie znaku, usunięcie znaku, zmiana znaku na inny) określa najmniejszą liczbę operacji, potrzebnych do transformacji pierwszego napisu w drugi. Łatwo sobie wyobrazić, że dla identycznych napisów odległość Levenshteina będzie równa 0, natomiast dla dwóch całkowicie różnych napisów, będzie równa liczbie znaków dłuższego z ciągów. Krótko mówiąc im mniejsza odległość, tym napisy są bardziej do siebie podobne.
Algorytm ten można modyfikować dodając np. nowe operacje, lub przypisując operacjom wagi.
Warto zauważyć, że PHP dostarcza nam własną implementację algorytmu Levenshteina, możemy jej użyć wywołując funkcję levenshtein.
int levenshtein ( string $str1, string $str2 [, int $cost_ins, int $cost_rep, int $cost_del] )
Natomiast w C# porównywaniem string’ów musimy się zająć sami. Przykładowa implementacja może wyglądać na przykład tak:
public static int LevenshteinDistance(String s1, String s2) { const int cost_ins = 1; const int cost_del = 1; const int cost_sub = 1; int n1 = s1.Length; int n2 = s2.Length; int[] p = new int[n2+1]; int[] q = new int[n2+1]; int[] r; p[0] = 0; for( int j = 1; j <= n2; ++j ) { p[j] = p[j-1] + cost_ins; } for( int i = 1; i <= n1; ++i ) { q[0] = p[0] + cost_del; for( int j = 1; j <= n2; ++j ) { int d_del = p[j] + cost_del; int d_ins = q[j - 1] + cost_ins; int d_sub = p[j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : cost_sub); q[j] = Math.Min( Math.Min( d_del, d_ins ), d_sub ); } r = p; p = q; q = r; } return p[n2]; }
Wynikiem funkcji Levenshteina jest liczba całkowita. Co jednak zrobić gdy na podstawie porównania ciągów znaków chcemy je klasyfikować? Liczba całkowita nie jest w tym wypadku zbyt wymowna. Lepszym pomysłem jest uzależnienie wyniku od maksymalnej długości ciągu.
Przykład:
public static float LevenshteinTextComparison(String s1, String s2) { if (s1.Equals(String.Empty) && s2.Equals(String.Empty)) { return 1; } return 1 - ((float)LevenshteinDistance(s1, s2) / (float)Math.Max(s1.Length, s2.Length)); }
Teraz zamiast mało mówiącej liczby całkowitej, otrzymujemy liczbę rzeczywistą z zakresu <0, 1> określającą podobieństwo napisów. Im bliżej jedynki tym ciągi są bardziej podobne i w drugą stronę, im bliżej zera, tym ciągi bardziej się od siebie różnią.
Przydatne linki:
http://pl.wikipedia.org/wiki/Odległość_Levenshteina
http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance