Дамерау–Левенштајново растојање

У теорији информација и информатике, Дамерау-Левенсхтеин растојање (названо по Фредрицх Ј. Дамерау и Владимир I. Левенсхтеину) је "растојање" између два стринга, односно коначна секвенца симбола, добијена рачунајући минималан број операција потребних да се један стринг трансформише у други што се дефинише као операција убацивања, брисања или замена једног карактера другим, или транспозиција два суседна карактера. У свом кључном раду^[1], Дамерау не само да разликује ове четири операције, већ је и изјавио да су оне одговорне за 80% правописних грешака. Дамерауова студија узима у обзир само грешке које су могле бити исправљене са само једном операцијом. Одговарајућа измена растојања, на пример дељење са вишеструким операцијама уређивања, позната као Левенсхтеин растојање, представљена од Левенсхтеина,^[2] али не укључује транспозиције у скупу основних операција. Име Дамерау-Левенсхтеин дистанце се користи за уређивање удаљености која омогућава уређиванеј више операција, укључујући транспозиције, иако није јасно да ли се термин Дамерау-Лавенсхтеин дистанце понекад користи у неким изворима тако што узима у обзир несуседне транспозиције или не.

Док је оригинални мотив био да се измери растојање између људских правописних гресака у побољшању апликације попут правописних контролора, Дамерау – Левенсхтеин дистанце такође користи и у биологији за мерење варијације између ДНК.

Алгоритам[уреди | уреди извор]

Додавање транспозиције звучи једноставно, али устварности постоји озбиљна компликација. Представљана су два алгоритма: први^[3] , једноставнији, израчунава оно што је познато као оптимал стринг алигнмент^{[тражи се извор]}, а други^[4] израчунава Дамерау-Левенсхтеин дистанце са суседним транспозицијама. Разлика између ова два алгоритма састоји се у томе да оптимал стринг алигнмент алгоритхм израчунава број едит операција потребних да би стрингови били једнаки под условом да подстринг не сме да се едитује висе пута, док код другог овај услов не постоји.

Узмимо пример да се промени растојање измедју ЦА и АБЦ. Дамерау-Левенсхтеин дистанце ЛД(ЦА, АБЦ) =2 јер ЦА -> АЦ ->АБЦ, али оптимал стринг алигнмент дистанце ОСА(СА,АБЦ)=3 јер ако се операција ЦА ->АЦ користи, није могуће користити АЦ -> АБЦ, јер би то значило да се подстринг мења више пута, што није дозвољено у ОСА, а самим тим најкраћи редослед операција је ЦА -> А -> АБ -> АБЦ. Запазите да у ОСА не важи неједнакост троугла: ОСА(ЦА,АЦ) + ОСА(АЦ,АБЦ) < ОСА(ЦА,АБЦ), па то није тацно.

Доле испод је псеудокод за функцију ОптималСтрингАлигнментДистанце која узима 2 стринга, стр1 дужине ленСтр1, и стр2 дужине ленСтр2, и израчунава оптимал стринг алигнмент растојање између њих (Коментари су на енглеском):

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]

У суштини ово је алгоритам за израчунавање Левенсхтеин дистанце:

           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
                             )

Ово је други алгоритам који рачуна право Дамерау–Левенсхтеин дистанце са суседном транспозицијом (АцтионСцрипт 3.0); ова функција захтева један додатни параметар- величину писма (C), тако да сви улази за низ су у 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;
    }
}

коришћењем C# програмског језика израчунавамо прави Дамерау–Левенсхтеин дистанце са суседним транспозицијама.

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];
}

(Запажања: алгоритам дат у раду користи писмо 1..C пре него 0..C−1, и индексира низове другачије: Х[−1..|А|,−1..|Б|] пре него Х[0..|А|+1,0..|Б|+1], ДА[1..C] пре него ДА[0..Ц−1]; у раду недостаје неопходна линија Х[−1,−1] = ИНФ)

Да осмислимо одговарајуци алгоритам за израчунавање Дамерау–Левенсхтеин растојања запажамо да увек постоји оптимална секвенца едит операција , где једном-транспована слова се никада не мењају касније. Тако да нам је потребно да размотримо 2 симетрична случаја модификовања подстринга више пута: (1) транспоновати слова и убацити произвољан број знакова између њих, или (2) обрисати секвенцу карактера и транспоновати слова која постају суседна после брисања. Директна примена ове идеје даје алгоритам кубне сложености: $O\left(M\cdot N\cdot \max(M,N)\right)$ где су M и Н дужине стрингова. Коришћењем идеје Лоwранце и Wагнер,^[5] овај наиван алгоритам може се побољшати да буде $O\left(M\cdot N\right)$ у најгорем случају.

Занимљиво је да битап алгоритхм може бити модификован за процес транспозиције. Погледај одељак претраживање информација^[6] за пример таквог прилагођавања.

Апликације[уреди | уреди извор]

Први агоритам израчунава само условљену измену растојања. Дамерау-Левенсхтеин растојање игра важну улогу у обради природним језицима. У природним језицима, жице су кратке и број грешака ретко прелази 2. У таквим околностима, ограничења и реална измена растојања су веома ретки. Зато ово ограничење није веома важно. Међутим, морамо имати на уму да условљена измена растојања не задовољава увек неједнакост троугла, и самим тим, не може да се користи са метричким дрвећем.

ДНК[уреди | уреди извор]

Пошто ДНК често пролази уметања, брисања, замене и транспозиције, и свака од ових операција се јавља на приближно истом временском року, Дамерау-Левенсхтеин растојање је одговарајућа метрика варијација између две нити ДНК. Чешће у ДНК и протеинима се користе блиско повезани алгоритми као што су Неедлеман-Wунсцх алгоритам или Смитх-Wатерман алгоритам.

Детекција преваре[уреди | уреди извор]

Овај алгоритам може да се користи са било којом речи, као “продавац” имена. Пошто је улаз мануелан по природи постоји ризик од уласка разних продаваца. Преварант запослени може ући као прави продавац као што је “Рицх Хеир Естате Сервицес” (богати наследник имања услуга) против лажног продавца “Рицх Хиер Стате Сервицес” (богати наследник државе услуга). Преварант би онда створио лажни рачун у банци и знао би начин на који компаније проверавају праве и лажне продавце (добављаче). Дамерау-Левенсхтеин алгоритам ће детектовати транспоновано и падајуће писмо и скренути пажњу на истраживање преваре.

Такодје погледајте[уреди | уреди извор]

Референце[уреди | уреди извор]

^ А тецхниqуе фор цомпутер детецтион анд цоррецтион оф спеллинг еррорс, Цоммуницатионс оф тхе АЦМ, 1964.
^ Владимир I. Левенсхтеин. Бинарy цодес цапабле оф цоррецтинг делетионс, инсертионс, анд реверсалс. Совиет Пхyсицс Докладy, 1966.
^ Б. Ј. Ооммен; Р. К. С. Локе. „Паттерн рецогнитион оф стрингс wитх субститутионс, инсертионс, делетионс анд генерализед транспоситионс”. ЦитеСеерX: 10.1.1.50.1459.
^ Роy Лоwранце, Роберт А. Wагнер. Ан Еxтенсион оф тхе Стринг-то-Стринг Цоррецтион Проблем, ЈАЦМ, 1975.
^ Гонзало Наварро. А гуидед тоур то аппроxимате стринг матцхинг. АЦМ Цомпутинг Сурвеyс (ЦСУР) арцхиве, 33(1). стр. 31–88, 2001. Архивирано на сајту Wayback Machine (17. април 2012)

Спољашње везе[уреди | уреди извор]

[1]

[2]

[3]

[4]

[6]