Damerau–Levenštajnovo rastojanje

U teoriji informacija i informatike, Damerau-Levenshtein rastojanje (nazvano po Fredrich J. Damerau i Vladimir I. Levenshteinu) je "rastojanje" između dva stringa, odnosno konačna sekvenca simbola, dobijena računajući minimalan broj operacija potrebnih da se jedan string transformiše u drugi što se definiše kao operacija ubacivanja, brisanja ili zamena jednog karaktera drugim, ili transpozicija dva susedna karaktera. U svom ključnom radu^[1], Damerau ne samo da razlikuje ove četiri operacije, već je i izjavio da su one odgovorne za 80% pravopisnih grešaka. Damerauova studija uzima u obzir samo greške koje su mogle biti ispravljene sa samo jednom operacijom. Odgovarajuća izmena rastojanja, na primer deljenje sa višestrukim operacijama uređivanja, poznata kao Levenshtein rastojanje, predstavljena od Levenshteina,^[2] ali ne uključuje transpozicije u skupu osnovnih operacija. Ime Damerau-Levenshtein distance se koristi za uređivanje udaljenosti koja omogućava uređivanej više operacija, uključujući transpozicije, iako nije jasno da li se termin Damerau-Lavenshtein distance ponekad koristi u nekim izvorima tako što uzima u obzir nesusedne transpozicije ili ne.

Dok je originalni motiv bio da se izmeri rastojanje između ljudskih pravopisnih gresaka u poboljšanju aplikacije poput pravopisnih kontrolora, Damerau – Levenshtein distance takođe koristi i u biologiji za merenje varijacije između DNK.

Algoritam[уреди | уреди извор]

Dodavanje transpozicije zvuči jednostavno, ali ustvarnosti postoji ozbiljna komplikacija. Predstavljana su dva algoritma: prvi^[3] , jednostavniji, izračunava ono što je poznato kao optimal string alignment^{[тражи се извор]}, a drugi^[4] izračunava Damerau-Levenshtein distance sa susednim transpozicijama. Razlika između ova dva algoritma sastoji se u tome da optimal string alignment algorithm izračunava broj edit operacija potrebnih da bi stringovi bili jednaki pod uslovom da podstring ne sme da se edituje vise puta, dok kod drugog ovaj uslov ne postoji.

Uzmimo primer da se promeni rastojanje izmedju CA i ABC. Damerau-Levenshtein distance LD(CA, ABC) =2 jer CA -> AC ->ABC, ali optimal string alignment distance OSA(SA,ABC)=3 jer ako se operacija CA ->AC koristi, nije moguće koristiti AC -> ABC, jer bi to značilo da se podstring menja više puta, što nije dozvoljeno u OSA, a samim tim najkraći redosled operacija je CA -> A -> AB -> ABC. Zapazite da u OSA ne važi nejednakost trougla: OSA(CA,AC) + OSA(AC,ABC) < OSA(CA,ABC), pa to nije tacno.

Dole ispod je pseudokod za funkciju OptimalStringAlignmentDistance koja uzima 2 stringa, str1 dužine lenStr1, i str2 dužine lenStr2, i izračunava optimal string alignment rastojanje između njih (Komentari su na engleskom):

int OptimalStringAlignmentDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is a table with lenStr1+1 rows and lenStr2+1 columns
   declare int d[0..lenStr1, 0..lenStr2]
   // i and j are used to iterate over str1 and str2
   declare int i, j, cost
   //for loop is inclusive, need table 1 row/column larger than string length.
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 1 to lenStr2
       d[0, j] := j
   //Pseudo-code assumes string indices start at 1, not 0.
   //If implemented, make sure to start comparing at 1st letter of strings.
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // deletion
                                d[i  , j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
           if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + cost   // transposition
                             )
                                
 
   return d[lenStr1, lenStr2]

U suštini ovo je algoritam za izračunavanje Levenshtein distance:

           if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + cost   // transposition
                             )

Ovo je drugi algoritam koji računa pravo Damerau–Levenshtein distance sa susednom transpozicijom (ActionScript 3.0); ova funkcija zahteva jedan dodatni parametar- veličinu pisma (C), tako da svi ulazi za niz su u 0..(C−1):

static public function damerauLevenshteinDistance(a:Array, b:Array, C:uint):uint
{
    var INF:uint = a.length + b.length;
    var H:matrix = new matrix(a.length+2,b.length+2);    
    H[0][0] = INF;
    for(var i:uint = 0; i<=a.length; ++i) {H[i+1][1] = i; H[i+1][0] = INF;}
    for(var j:uint = 0; j<=b.length; ++j) {H[1][j+1] = j; H[0][j+1] = INF;}            
    var DA:Array = new Array(C);
    for(var d:uint = 0; d<C; ++d) DA[d]=0;
    for(var i:uint = 1; i<=a.length; ++i)
    {
        var DB:uint = 0;
        for(var j:uint = 1; j<=b.length; ++j)
        {
            var i1:uint = DA[b[j-1]];
            var j1:uint = DB;
            var d:uint = ((a[i-1]==b[j-1])?0:1);
            if(d==0) DB = j;
            H[i+1][j+1] = Math.min(H[i][j]+d, H[i+1][j] + 1, H[i][j+1]+1, 
                            H[i1][j1] + (i-i1-1) + 1 + (j-j1-1));
        }
        DA[a[i-1]] = i;
    }
    return H[a.length+1][b.length+1];
}

public class matrix extends Array
{
    public var rows:uint, cols:uint;
    public function matrix(nrows:int=0, ncols:int=-1)
    {
        super(nrows);
        if(ncols == -1) ncols = nrows;
        for(var i:uint = 0; i<nrows; ++i)
        {
            this[i] = new Array(ncols);
        }
        rows = nrows; cols = ncols;
    }
}

korišćenjem C# programskog jezika izračunavamo pravi Damerau–Levenshtein distance sa susednim transpozicijama.

public static int DamerauLevenshteinDistance(string source, string target)
{
    if (String.IsNullOrEmpty(source))
    {
        if (String.IsNullOrEmpty(target))
        {
            return 0;
        }
        else
        {
            return target.Length;
        }
    }
    else if (String.IsNullOrEmpty(target))
    {
        return source.Length;
    } 
 
    var score = new int[source.Length + 2, target.Length + 2];

    var INF = source.Length + target.Length;
    score[0, 0] = INF;
    for (var i = 0; i <= source.Length; i++) { score[i + 1, 1] = i; score[i + 1, 0] = INF; }
    for (var j = 0; j <= target.Length; j++) { score[1, j + 1] = j; score[0, j + 1] = INF; }
 
    var sd = new SortedDictionary<char, int>();
    foreach (var letter in (source + target))
    {
        if (!sd.ContainsKey(letter))
            sd.Add(letter, 0);
    }

    for (var i = 1; i <= source.Length; i++)
    {
        var DB = 0;
        for (var j = 1; j <= target.Length; j++)
        {
            var i1 = sd[target[j - 1]];
            var j1 = DB;

            if (source[i - 1] == target[j - 1])
            {
                score[i + 1, j + 1] = score[i, j];
                DB = j;
            }
            else
            {
                score[i + 1, j + 1] = Math.Min(score[i, j], Math.Min(score[i + 1, j], score[i, j + 1])) + 1;
            }

            score[i + 1, j + 1] = Math.Min(score[i + 1, j + 1], score[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
        }

        sd[source[i - 1]] = i;
    }

    return score[source.Length + 1, target.Length + 1];
}

(Zapažanja: algoritam dat u radu koristi pismo 1..C pre nego 0..C−1, i indeksira nizove drugačije: H[−1..|A|,−1..|B|] pre nego H[0..|A|+1,0..|B|+1], DA[1..C] pre nego DA[0..C−1]; u radu nedostaje neophodna linija H[−1,−1] = INF)

Da osmislimo odgovarajuci algoritam za izračunavanje Damerau–Levenshtein rastojanja zapažamo da uvek postoji optimalna sekvenca edit operacija , gde jednom-transpovana slova se nikada ne menjaju kasnije. Tako da nam je potrebno da razmotrimo 2 simetrična slučaja modifikovanja podstringa više puta: (1) transponovati slova i ubaciti proizvoljan broj znakova između njih, ili (2) obrisati sekvencu karaktera i transponovati slova koja postaju susedna posle brisanja. Direktna primena ove ideje daje algoritam kubne složenosti: $O\left(M\cdot N\cdot \max(M,N)\right)$ gde su M i N dužine stringova. Korišćenjem ideje Lowrance i Wagner,^[5] ovaj naivan algoritam može se poboljšati da bude $O\left(M\cdot N\right)$ u najgorem slučaju.

Zanimljivo je da bitap algorithm može biti modifikovan za proces transpozicije. Pogledaj odeljak pretraživanje informacija^[6] za primer takvog prilagođavanja.

Aplikacije[уреди | уреди извор]

Prvi agoritam izračunava samo uslovljenu izmenu rastojanja. Damerau-Levenshtein rastojanje igra važnu ulogu u obradi prirodnim jezicima. U prirodnim jezicima, žice su kratke i broj grešaka retko prelazi 2. U takvim okolnostima, ograničenja i realna izmena rastojanja su veoma retki. Zato ovo ograničenje nije veoma važno. Međutim, moramo imati na umu da uslovljena izmena rastojanja ne zadovoljava uvek nejednakost trougla, i samim tim, ne može da se koristi sa metričkim drvećem.

DNK[уреди | уреди извор]

Pošto DNK često prolazi umetanja, brisanja, zamene i transpozicije, i svaka od ovih operacija se javlja na približno istom vremenskom roku, Damerau-Levenshtein rastojanje je odgovarajuća metrika varijacija između dve niti DNK. Češće u DNK i proteinima se koriste blisko povezani algoritmi kao što su Needleman-Wunsch algoritam ili Smith-Waterman algoritam.

Detekcija prevare[уреди | уреди извор]

Ovaj algoritam može da se koristi sa bilo kojom reči, kao “prodavac” imena. Pošto je ulaz manuelan po prirodi postoji rizik od ulaska raznih prodavaca. Prevarant zaposleni može ući kao pravi prodavac kao što je “Rich Heir Estate Services” (bogati naslednik imanja usluga) protiv lažnog prodavca “Rich Hier State Services” (bogati naslednik države usluga). Prevarant bi onda stvorio lažni račun u banci i znao bi način na koji kompanije proveravaju prave i lažne prodavce (dobavljače). Damerau-Levenshtein algoritam će detektovati transponovano i padajuće pismo i skrenuti pažnju na istraživanje prevare.