Изворни код странице Damerau–Levenštajnovo rastojanje

U teoriji [[informacija]] i [[informatika|informatike]], '''Damerau-Levenshtein rastojanje''' (nazvano po [[Fredrich J. Damerau]] i [[Vladimir I. Levenshteinu]]) je "rastojanje" između dva [[string]]a, 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{{ref|D64}}, 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 [[Levenshteinovo rastojanje|Levenshtein rastojanje]], predstavljena od Levenshteina,{{ref|L66}} 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{{ref|OO}} , jednostavniji, izračunava ono što je poznato kao [[optimal string alignment]]{{чињеница| date = 06. 2013.}}, a drugi{{ref|LW75}} 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 [[pseudocode|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):

<syntaxhighlight lang='actionscript3'>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;
    }
}
</syntaxhighlight>

korišćenjem C# programskog jezika izračunavamo pravi Damerau–Levenshtein distance sa susednim transpozicijama.
<syntaxhighlight lang='csharp'>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];
} 
</syntaxhighlight>

(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]&nbsp;=&nbsp;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: <math>O\left (M \cdot N \cdot \max(M, N) \right )</math> gde su ''M'' i ''N'' dužine stringova. Korišćenjem ideje Lowrance i Wagner,{{ref|LW75}} ovaj naivan algoritam može se poboljšati da bude <math>O\left (M \cdot N \right)</math> u najgorem slučaju.

Zanimljivo je da [[bitap algorithm]] može biti modifikovan za proces transpozicije. Pogledaj odeljak pretraživanje informacija{{ref|itman}} 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 [[metric trees|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.

== Takodje pogledajte ==
* [[Approximate string matching]]
* [[Levenshtein automata]]
* [[Typosquatting]]

== Reference ==
* {{note|D64}} [http://dl.acm.org/citation.cfm?id=363994 ''A technique for computer detection and correction of spelling errors'', Communications of the ACM, 1964.]
* {{note|L66}} [https://web.archive.org/web/20121124033129/http://profs.sci.univr.it/~liptak/ALBioinfo/files/levenshtein66.pdf Vladimir I. Levenshtein. ''Binary codes capable of correcting deletions, insertions, and reversals''. Soviet Physics Doklady, 1966.]
* {{note|OO}} {{cite paper | author1 = B. J. Oommen | author2 = R. K. S. Loke | title = Pattern recognition of strings with substitutions, insertions, deletions and generalized transpositions | id = {{citeseerx|10.1.1.50.1459}} }}
* {{note|LW75}} [http://dl.acm.org/citation.cfm?id=321879.321880 Roy Lowrance, Robert A. Wagner. {{cite journal|author= |title=An Extension of the String-to-String Correction Problem |journal=JACM|date= |volume=|issue=|pages=}} , 1975.]
* {{note|Nav01}} [http://www.ling.helsinki.fi/kit/2002s/ctl190net/materiaali/p31-navarro.pdf Gonzalo Navarro. ''A guided tour to approximate string matching''. ACM Computing Surveys (CSUR) archive, 33(1). стр. 31–88, 2001.] {{Wayback|url=http://www.ling.helsinki.fi/kit/2002s/ctl190net/materiaali/p31-navarro.pdf |date=20120417050853 }}

== Spoljašnje veze ==
{{Портал бар|Информатика}}
* {{cite web | url=http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance | title= Damerau–Levenshtein distance - Engleska Wikipedija}}
* [http://mwh.geek.nz/2009/04/26/python-damerau-levenshtein-distance/ Python implementation of optimal string alignment distance]
* [http://frej.sf.net FREJ – an open source java library which implements approximate substring search using Damerau–Levenshtein distance].
* [http://gist.github.com/182759 Ruby translation of above Python implementation.]
* [http://www.mathworks.com/matlabcentral/fileexchange/32449-edit-distances Matlab implementation] {{Wayback|url=http://www.mathworks.com/matlabcentral/fileexchange/32449-edit-distances |date=20130405013738 }}
* [https://metacpan.org/module/Text::Levenshtein::Damerau Perl implementation]
* [https://npmjs.org/package/levenshtein-damerau NodeJS / JavaScript implementation]
* [https://github.com/ugexe/Text--Levenshtein--Damerau--XS/blob/master/damerau-int.c C implementation]

{{normativna kontrola}}

{{СОРТИРАЊЕ:Дамерау-Левенштајново растојање}}
[[Категорија:Алгоритми на нискама]]
[[Категорија:Динамичко програмирање]]