Levenštajnovo rastojanje

U računarstvu, Levenštajnovo rastojanje je metrika za niske, koja je jedan od načina da se odredi rastojanje uređivanja (engl. edit distance) dve niske. Levenštajnovo rastojanje dve niske je određeno minimalnim brojem operacija neophodnim da se jedna niska transformiše u drugu, a operacije su umetanje, brisanje ili zamena jednog karaktera drugim. Dobilo je ime po Vladimiru Levenštajnu, koji ga je razvio 1965. Levenštajnovo rastojanje je korisno u određivanju sličnosti dve niske, na primer u softveru za pronalaženje grešaka u kucanju.

Na primer, Levenštajnovo rastojanje reči "kitten" i "sitting" je 3, jer su potrebne najmanje tri operacije izmene da se jedna reč transformiše u drugu:

1. kitten → sitten (zamena 's' sa 'k')
2. sitten → sittin (zamena 'i' sa 'e')
3. sittin → sitting (umetanje 'g' na kraj)

Ovo rastojanje se može posmatrati kao uopštenje Hamingovog rastojanja, koje se koristi da niske iste dužine, i koje podrazumeva isključivo zamene karaktera. Postoje i dalje generalizacije Levenštajnovog rastojanja, na primer Damerau-Levenštajnovo rastojanje koje dozvoljava operaciju promene mesta karakteru (koje se kod Levenštajnovog rastojanja posmatra kao dve operacije - brisanje i potom umetanje).

Definicija

Matematički, Levenštajnovo rastojanje između dva stringa $a,b$ je dato $\operatorname {lev} _{a,b}(|a|,|b|):<math>\qquad \operatorname {lev} _{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if}}\min(i,j)=0,\\\min {\begin{cases}\operatorname {lev} _{a,b}(i-1,j)+1\\\operatorname {lev} _{a,b}(i,j-1)+1\\\operatorname {lev} _{a,b}(i-1,j-1)+[a_{i}\neq b_{j}]\end{cases}}&{\text{ otherwise.}}\end{cases}}$

Imajte na umu da prvi element odgovara brisanju (iz <$a$ do $b$), drugi odgovara umetanju a treći se podudara.

Primena

U približnom podudaranju niski, cilj je da se pronađe pogodak za kraće niske u velikim tekstovima, u situacijama kada se očekuje mali broj razlika. Kraća niska može doći iz rečnika na primer. Ovde je jedna niska tipično kraća, dok je druga duža. Ovo ima širok spektar primena, npr. provera pravopisa (eng. Spell-checker), sistemi korekcije za optičko prepoznavanje karaktera i za softver koji asistira u prevođenju. Levenštajnovo rastojanje se može izračunati i između dva duže niske, ali cena tog izračunavanja koje je grubo rečeno proporcionalna proizvodu dužine ta dve niske dovodi do nepraktičnosti ovog algoritma.

Algoritam

Rekurzivno

Rekurzivna implementacija LevenshteinDistance funkcije uzima dve niske, „s“ i „t“ i vraća Levenštajnovo rastojanje između njih:

int LevenshteinDistance(string s, string t)
{
  int len_s = length(s);
  int len_t = length(t);
 
  /* test for degenerate cases of empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1]) cost = 0;
  else                          cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,
                 LevenshteinDistance(s, t[0..len_t-1]) + 1,
                 LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)
}

Rekurzivna implementacija je dosta neefikasna zbog toga što računa Levenštajnovo rastojanje podniske mnogo puta. Bolji metod ne bi ponavljao izračunavanja. Na primer, Levenštajnovo rastojanje svih mogućih prefiksa može biti smešteno u niz d[][] gde je d[i][j] rastojanje između prvog i karaktera niske s i prvog j karaktera niske t. Tabela je jednostavna za konstrukciju počevši od reda 0. Kada je cela tabela izrađena, željena distanca je d[len_s][len_t].. Iako je ova tehnika značajno brža zahtevaće len_s * len_t više memorije nego rekurzivna implementacija.

Iterativno sa celom matricom

Izračunavanje Levenštajnovog rastojanja je bazirano na zapažanju da ako rezervišemo matricu za čuvanje rastojanja između svih prefiksa prve niske i svih prefiksa druge, onda možemo da izračunamo vrednosti u matrici pomoću dinamičkog programiranja i tako nađemo rastojanje između dva pune niske. Ovaj algoritam je primer „odozdo nagore“ dinamičkog programiranja, kao što je diskutovano, sa varijacima, 1974. godine u The String-to-string correction problem od Robert A. Wagner and Michael J. Fischer. Implementacija funkcije Levanštajnovog rastojanja koja uzima dve niske, „s“ dužine “m“ i nisku „t“ dužine „n“ i vraća Levenštajnovo rastojanje između ta dve niske.

int LevenshteinDistance(char s[1..m], char t[1..n])
{
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t;
  // note that d has (m+1)*(n+1) values
  declare int d[0..m, 0..n]

  clear all elements in d // set each element to zero

  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m
    {
      d[i, 0] := i
    }

  // target prefixes can be reached from empty source prefix
  // by inserting every characters
  for j from 1 to n
    {
      d[0, j] := j
    }

  for j from 1 to n
    {
      for i from 1 to m
        {
          if s[i] = t[j] then  //going on the assumption that string indexes are 1-based in your chosen language<!-- not: s[i-1] = t[j-1] -->
                               //else you will have to use s[i-1] = t[j-1] Not doing this might throw an IndexOutOfBound error
            d[i, j] := d[i-1, j-1]       // no operation required
          else
            d[i, j] := minimum
                    (
                      d[i-1, j] + 1,  // a deletion
                      d[i, j-1] + 1,  // an insertion
                      d[i-1, j-1] + 1 // a substitution
                    )
        }
    }

  return d[m,n]
}

Zapazite da ova implementacija ne odgovara definiciji precizno: uvek preferiše pogotke, čak ako umetanje ili brisanje pruža bolji rezultat. Ovo je ekvivalent; može se pokazati da za svako optimalno poravnanje (koje uključuje Levenštajnovo rastojanje) postoji drugo optimalno poravnanje. Dva primera rezultujuće matrice(prelazak miša preko broja otkriva koja je operacija izvršena da bi se dobio taj broj)

k i t t e n 0 1 2 3 4 5 6 s 1 substitution of 'k' for 's' 2 3 4 5 6 i 2 2 'i' equals 'i' 2 3 4 5 t 3 3 2 't' equals 't' 2 3 4 t 4 4 3 2 't' equals 't' 2 3 i 5 5 4 3 2 substitution of 'e' for 'i' 3 n 6 6 5 4 3 3 'n' equals 'n' g 7 7 6 5 4 4 insert 'g'

S a t u r d a y 0 1 2 3 4 5 6 7 8 S 1 'S' equals 'S' delete 'a' delete 't' 3 4 5 6 7 u 2 1 1 2 'u' equals 'u' 3 4 5 6 n 3 2 2 2 3 substitution of 'r' for 'n' 4 5 6 d 4 3 3 3 3 4 'd' equals 'd' 4 5 a 5 4 3 4 4 4 4 'a' equals 'a' 4 y 6 5 4 4 5 5 5 4 'y' equals 'y'

Invarijanta je održana kroz algoritam i možemo transformisati početni segment s[1..i] u t[1..j] koristeći minimum d[i,j] operacija. Na kraju, donji desni element niza sadrži odgovor.

Iterativno sa dva reda matrice

Ispada da samo dva reda tabele su potrebna za konstrukciju: prethodni red i trenutni red(onaj koji se računa). Levenštajnovo rastojanje može se računati iterativno koristeći sledeći algoritam: : :

static int LevenshteinDistance(string s, string t)
{
    // degenerate cases
    if (s == t) return 0;
    if (s.Length == 0) return t.Length;
    if (t.Length == 0) return s.Length;

    // create two work vectors of integer distances
    int[] v0 = new int[t.Length + 1];
    int[] v1 = new int[t.Length + 1];

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for (int i = 0; i < v0.Length; i++)
        v0[i] = i;

    for (int i = 0; i < s.Length; i++)
    {
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i+1][0]
        //   edit distance is delete (i+1) chars from s to match empty t
        v1[0] = i + 1;

        // use formula to fill in the rest of the row
        for (int j = 0; j < t.Length; j++)
        {
            var cost = (s[i] == t[j]) ? 0 : 1;
            v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
        }

        // copy v1 (current row) to v0 (previous row) for next interation
        for (int j = 0; j < v0.Length; j++)
            v0[j] = v1[j];
    }

    return v1[t.Length];
}

Dokaz korektnosti

Kao što je prethodno pomenuto, invarijanta je da umemo da transformišemo početni segment s[1..i] u t[1..j] korišćenjem minimuma operacija, d[i,j]. Ova invarijanta važi jer:

• U početku je ovo tačno za vrstu i kolonu 0 jer se s[1..i] može transformisati u praznu nisku t[1..0] prostim brisanjem svih i karaktera. Slično, možemo da transformišemo s[1..0] u t[1..j] prostim dodavanjem svih j karaktera.
• Minimum se dobija od tri razdaljine, od koje je svaka izvodljiva:
  • Ako umemo da transformišemo s[1..i] u t[1..j-1] sa k operacija, onda prosto možemo da dodamo t[j] nakon toga, i da dobijemo t[1..j] sa k+1 operacija.
  • Ako umemo da transformišemo s[1..i-1] u t[1..j] sa k operacija, onda možemo da sprovedemo iste operacije na s[1..i] a zatim da uklonimo s[i] sa kraja, i da dobijemo ukupan broj od k+1 operacija.
  • Ako umemo da transformišemo s[1..i-1] u t[1..j-1] sa k operacija, umemo da uradimo isto i sa s[1..i] a zatim da zamenimo t[j] sa s[i] na kraju, ukoliko je neophodno, što zahteva ukupno k+cost operacija.
• Broj operacija neophodnih da se transformiše s[1..n] u t[1..m] je broj operacija potrebnih da se svako s transformiše u svako t, pa tako d[n,m] važi za naš rezultat.

Ovaj dokaz ne dokazuje da je broj koji se nalazi u matrici, d[i,j] zaista minimalan; ovo je teže pokazati, i neophodno je koristiti svođenje na kontradikciju.

Moguća unapređenja i varijacije

Među mogućim unapređenjima algoritma su:

• Možemo da napravimo varijaciju algoritma da zahteva manje prostora, O(m) umesto O(mn), jer je neophodno da pamtimo samo prethodnu i trenutnu vrstu matrice u svakom trenutku.
• Možemo da uskladištimo broj umetanja, brisanja i zamena odvojeno, ili čak na pozicijama na kojima se javljaju, što je uvek j.
• Možemo da dajemo različite cene operacijama umetanja, brisanja i zamene.
• Inicijalizacija d[i,0] se može premestiti u glavnu spoljašnju petlju.
• Ovaj algoritam se loše paralelizuje, usled velike količine zavisnih podataka. Međutim, sve cost vrednosti se mogu izračunati paralelno.

Gornje i donje granice

Levenštajnovo rastojanje ima nekoliko jednostavnih gornjih i donjih granica koje su korisne u primenama koje računaju mnogo njih, i porede ih. Među njima su:

• Rastojanje nikad nije manje od razlike u dužinama dve niske.
• Rastojanje nije duže od dužine duže od niski.
• Rastojanje je jednako nuli ako i samo ako su niske identične.
• Ako su niske jednakih dužina, Hamingovo rastojanje je gornja granica Levenštajnovog rastojanja.
• Ako dve niske označimo sa s i t, broj karaktera (isključujući duplikate) koji se pojavljuju u s ali ne i u t je donja granica.

Vidi još

• Damerau-Levenštajnovo rastojanje
• Džaro-Vinkler rastojanje
• Hamingovo rastojanje
• Problem najdužeg zajedničkog podniza
• Metrički prostor
• Nidlmen-Vanšov algoritam
• Smit-Votermanov algoritam

Spoljašnje veze

• Java, C++ и VB implementacije algoritma
• NIST rečnik algoritama i baza podataka: Levenštajnovo rastojanje
• Vizualizacija Levenštajnovog rastojanja