Odległość Levenshteina

Odległość Levenshteina

Jest to minimalna ilość prostych operacji, jakie należy wykonać, aby przeprowadzić jeden ciąg znaków w drugi. Proste operacje to:

  • usunięcie znaku
  • wstawienie znaku
  • zamiana znaku na inny
Jest to jedna z odmian odległości edycyjnych, które różnią się między sobą zbiorem operacji uznawanych za proste. Na przykład odległość Levenshteina jest uogólnieniem odległości Hamminga, która za działanie proste uznaje tylko zamianę znaku, a sama również ma uogólnienia oparte na rozszerzaniu zbioru operacji prostych, tak jak odległość Damerau-Levenshteina, w której istnieje jeszcze zamiana miejscami dwóch sąsiednich znaków. Inne powszechne rozszerzenia to mozliwość wstawiania, usuwania i zastępowania nieprzerwanych bloków napisów. Formalnie, odległość Levenshteina jest metryką w przestrzeni ciągów znaków.

Vladimir Levenshtein

Влад́имир И́осифович Левеншт́ейн (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.

Zastosowanie

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:

  • korekcja błędów transmisji
  • rozpoznawanie mowy i pisma odręcznego
  • OCR
  • analiza ciągów DNA
  • sprawdzanie pisowni
  • rozpoznawanie plagiatów

Algorytm

Algorytm obliczania odległości Levenshteina w postaci matematycznej zapisywany jest następująco:

leva,b(i, j) = max(i, j) , min(i, j) = 0 min leva,b(i-1, j)+1 leva,b(i, j-1)+1 leva,b(i-1, j-1) + [ai ≠ bj] , w innym wypadku

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;
}

Policz odległość między dwoma ciągami znaków:
Słowo początkowe:
Słowo docelowe:

O stronie

Autorem tej strony jest

Grzegorz Kowalski
klasa 3ib
Technikum Łączności nr 14 w Krakowie
Strona wykonana została za pomocą systemu GNU/Linux 3.7 (ArchLinux) z edytorem GNU Nano.
Wykorzystane technologie to: HTML5, CSS3, Javascript oraz jQuery.
Strona w wersji online jest dostępna pod adresem http://2012-2013.szkola.daneos.com/zobaczyc-matematyke/.