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

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:

$\mathrm{lev_a,b(i,\; j)}=\left\{\begin{array}{cc}\mathrm{max(i,\; j)}& \mathrm{,\; min(i,\; j)\; =\; 0}\\ min\left\{\begin{array}{c}\mathrm{lev_a,b(i-1,\; j)+1}\\ \mathrm{lev_a,b(i,\; j-1)+1}\\ \mathrm{lev_a,b(i-1,\; j-1)\; +\; [a_i\; \ne \; b_j]}\end{array}\right.& \mathrm{,\; w\; innym\; wypadku}\end{array}\right.$

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:

Policz odległość

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/.