Levenshteini kaugus

Levenhsteini kaugus on informatsiooniteoorias, keeleteaduses ja informaatikas algoritm, mida kasutatakse kahe sõne sarnasuse kirjeldamiseks. Levenshteini kaugus näitab, kui mitu korda tuleb ühes sõnes tähte lisada, eemaldada või vahetada selleks, et ühest sõnest saaks teine sõne. Algoritm sai endale nime Nõukogude Liidu matemaatiku Vladimir Levenshteini järgi, kes hakkas kasutama seda kauguse algoritmi 1965. aastal.^[1]

Definitsioon

Levenshteini kaugus kahe sõne a ja b vahel on võrdeline $\operatorname {lev} _{a,b}(|a|,|b|)$ , kus

\qquad \operatorname {lev} _{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ kui}}\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)+1_{(a_{i}\neq b_{j})}\end{cases}}&{\text{ teistel juhtudel.}}\end{cases}}

Näide

Näiteks Levenhsteini kaugus kahe sõne "maru" ja "karud" vahel on 2. Me saame sõnest "maru" sõne "karud" kahe muudatusega järgmisel viisil, millest lühemat viisi ei leidu:

maru -> karu (tähe "m" asendasime tähega "k")
karu -> karud (lisasime tähe "d")

Väärtuste piirangud

Levenshteini väärtustel esineb järgmiseid piiranguid ja tingimusi:

Tulemus ei saa olla kunagi väiksem kui kahe sõne pikkuste vahe.
Tulemus ei saa olla kunagi suurem kui pikema sõne pikkus.
Tulemus on 0 ainult siis, kui sõned on samad.
Kui sõned on võrdsete pikkustega, siis tulemus saadakse ainult tähtede muutmisel (Hammingu kaugus).

Kasutusalad

Levenshteini kaugust kasutatakse üldiselt lühemate sõnede võrdlemiseks. Pikkade tekstide korral on algoritm oma keerukuse pärast ebapraktilisem, kuid teatud kohtades leiab ta siiski kasutust. Levenshteini kagust kasutatakse põhiliselt õigekirja kontrollis, kõnetuvastuses, DNA analüüsis, plagiaadi tuvastamises^[2].

Levnshteini algoritmi arvutamise kood

Rekursiivselt

Siin on rekursiivne C-keele koodinäide:

// len_s ja len_t näitavad mitu tähte on vastavalt esimeses ja teises sõnes
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{ 
  int cost;

  /* baasjuhtum: tühjad sõned */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* Kontrollib, kas sõnede viimased tähed on samad */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* tagastab ühest sõnest tähe kustuamise või teisest sõnest tähe kustutamise või mõlemast kustutamise minimaalse väärtuse */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}

Selline kood on arvutamiseks väga ebaefektiivne. Selleks, et programm töötaks efektiivsemalt tuleb kasutada mälu. Kõik eelnevalt arvutatud kaugused tuleks hoida mälus ja sama arvutuse uuesti tekkimisel tuleks vastus võtta mälust, mitte seda uuesti arvutada.

Tsüklililine

Tsüklililiselt Levenshteini kauguse arvutamiseks luuakse arvuti mälus maatriks, kus x-telje suuna peal asuvad ühe sõne tähed ning y-telje suuna peal asuvad teise sõne tähed. Lõpptulemuseks on maatriks, kust on võimalik vaadata ükskõik milliseid võimalike sõnede alamkombinatsioonide tulemusi. Pseudokoodi näide:

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // d[i,j] hoiab meeles mitmendat maatriksi rida ja veergu me vaatame
  // i näitab mitmendat tähte me vaatame sõnest s
  // j näitab mitmendat tähte me vaatame sõnest t
  // tähele tuleb panna, et d võimalike positsioone on kokku (m + 1) * (n + 1)
  declare int d[0..m, 0..n]
 
  määra d kõik elementide väärtused alguses nulliks
 
  // esimese veeru kõik elemendid saadakse kustutamise arvelt
  for i from 1 to m:
      d[i, 0] := i
 
  // esimese rea kõik elemendid saadakse lisamise arvelt
  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]:
            substitutionCost := 0
          else:
            substitutionCost := 1
          d[i, j] := minimum(d[i-1, j] + 1,                   // kustutamine
                             d[i, j-1] + 1,                   // lisamine
                             d[i-1, j-1] + substitutionCost)  // vahetamine
 
  return d[m, n]

Viited

↑ Влади́мир И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов [Binary codes capable of correcting deletions, insertions, and reversals]. Доклады Академий Наук СCCP (vene). 163 (4): 845–8. Appeared in English as: Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions, and reversals". Soviet Physics Doklady. Bibcode:1966SPhD...10..707L.
↑ Michael Gilleland, http://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Fall2006/Assignments/editdistance/Levenshtein%20Distance.htm (19.03.2018)

[1] Влади́мир И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов [Binary codes capable of correcting deletions, insertions, and reversals]. Доклады Академий Наук СCCP (vene). 163 (4): 845–8. Appeared in English as: Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions, and reversals". Soviet Physics Doklady. Bibcode:1966SPhD...10..707L.

[2] Michael Gilleland, http://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Fall2006/Assignments/editdistance/Levenshtein%20Distance.htm (19.03.2018)

[1]

[2]