Jest to minimalna ilość prostych operacji, jakie należy wykonać, aby przeprowadzić jeden ciąg znaków w drugi. Proste operacje to:
Влад́имир И́осифович Левеншт́ейн (ur. 1935) - rosyjski naukowiec, matematyk i informatyk, zajmujący się m. in. teorią informacji, kodami korekcji błędów oraz kombinatoryką. W 1958 roku ukończył Wydział Matematyki i Mechaniki na Uniwersytecie Moskiewskim i od tamtego czasu pracuje w Instytucie Matematyki Stosowanej im. M. W. Keldysha. Członek Towarzystwa Teorii Informacji IEEE. W 2006 roku został wyróżniony Medalem Hamminga za wkład w rozwój teorii kodów korekcji błędów, teorię informacji, włącznie z odległością Levenshteina.
Odległość Levenshteina ma szerokie spektrum zastosowań. Można jej użyć wszędzie tam, gdzie konieczne jest porównanie danych możliwych do przedstawienia za pomocą ciągów znaków. Przykładowe zastosowania:
Algorytm obliczania odległości Levenshteina w postaci matematycznej zapisywany jest następująco:
Warto zauważyć, że wartości funkcji minimum odpowiadają (w kolejności) operacjom usunięcia, wstawienia, i zamiany, jeśli znaki są różne.
Zapisując ten algorytm w języku programowania, najlepiej użyć programowania dynamicznago.
Przykład implementacji w języku C:
int levenshtein(char *a, char *b)
{
int cost;
int m = strlen(a);
int n = strlen(b);
char **r = (char**)malloc((m+1)*sizeof(char*));
for(int c = 0; c < n+1; c++) r[0][c] = c;
for(int i = 1; i < m+1; i++)
{
r[i] = (char*)malloc(n);
r[i][0] = i;
for(int j = 1; j < n+1; j++)
{
cost = (a[i-1] == b[j-1]) ? 0 : 1;
r[i][j] = minimal(r[i-1][j]+1, r[i][j-1]+1, r[i-1][j-1]+cost);
}
}
return r[m][n];
}
int minimal(int x, int y, int z)
{
if(x < y && x < z) return x;
if(y < x && y < z) return y;
return z;
}
Autorem tej strony jest
Grzegorz Kowalski klasa 3ib Technikum Łączności nr 14 w KrakowieStrona wykonana została za pomocą systemu GNU/Linux 3.7 (ArchLinux) z edytorem GNU Nano.