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.
Definitsioon.
Levenshteini kaugus kahe sõne a ja b vahel on võrdeline formula_1, kus
formula_2
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:
Väärtuste piirangud.
Levenshteini väärtustel esineb järgmiseid piiranguid ja tingimusi:
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.
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]