Kursuse kodulehekülg Viimati muudetud: 9.4.2003

Loeng 3 - sõnede sarnasus ja teisenduskaugus

  1. Sõnede sarnasus
  2. Teisenduskaugus
  3. Teisenduskauguse arvutamine
  4. Teisenduskauguse parima lahenduse raporteerimine
  5. Teisenduskauguse arvutamine diagonaali meetodiga
  6. Üldistusi
  7. Pikim ühine alamjada (Longest Common Subsequence)
  8. Aja painutamine
  9. Bioloogilisi kauguste mõõte

Definition: Edit distance - the smallest number of insertions, deletions, and substitutions required to change one string or tree into another.
Also known as Levenshtein distance.

The greater the Levenshtein distance, the more different the strings are.

Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965. If you can't spell or pronounce Levenshtein, the metric is also sometimes called edit distance.

The Levenshtein distance algorithm has been used in:

Teisi raendusi sarnasuse otsimisele:

Lisamaterjale


Tagasi

Sõnede sarnasus

Mitmetes rakendustes on vaja otsida tekstidest mitte täpselt vaid lubades väikseid erinevusi võrreldes otsitavaga.

Näiteks color => colour, kartuleid -> kartulaid, jne.

Selleks et otsida ligikaudseid esinemisi tuleb defineerida mida mõeldakse ligikaudse all.

Üks ligikaudsuse mõõte on teisenduskaugus

Tagasi

Teisenduskaugus

Definitsioon: Stringide A ja B vaheline teisenduskaugus D(A,B) on minimaalne arv teisendusi mis tuleks teha stringile A et saada B. Teisendused on ühe tähe kustutamine, ühe tähe lisamine, või ühe tähe asendamine teisega.

Olgu sõned A= a1 a2 ... am ja B= b1 b2 ... bm.

Tegelikult on võimalik lubada ka teisi teisendusi Saab näidata et D(A,B) on meetrika, st.
  1. D(A,B) ≥ 0, D(A,B)=0 iff A=B
  2. D(A,B) = D(B,A)
  3. D(A,C) ≤ D(A,B) + D(A,C)
Näide
A=ABBA      B=BBB

ABBA                   ABBA
|  || 3 teisendust     |  |   2 teisendust  
 BB B                  BBB

D(A,B) = 2 

Veel näiteid: eelmise loengu lõpus (regulaaravaldistega otsimine) rääkisime:

ABC -> ABBC saadakse ühe B lisamisega,

ABC -> AC saadakse B eemaldamisega

ABC -> ABB saadakse C asendamisega B-ga.

Kõik stringid mis on genereeritavad näiteks ABC-st ühe teisendusoperatsiooniga võiks üles lugeda ning nendest moodustada lõpliku automaadi:

ABC =>
AB, AC, BC,
AB[AB], A[AC]C, [BC]BC,
AABC, ABAC, ABCA, BABC, ABBC, ABCB, CABC, ACBC, ABCC

Kuidas näidata teisendusi?

  1. Jälitus (?) (ing.k. trace)

  2. Joondamine (alignment)
    
    indust-r-y- 
    in---terest
    
    
  3. Operatsioonide loend:
    
     industry    d → ε
     inustry     u → ε
     instry      s → ε
     intry       ε → e
     intery      ε → e
     interey     y → s
     interes     ε → t
     interest
    
    
    Operatsioonide loetelust saab tekitada teised esitused.

Tagasi

Teisenduskauguse arvutamine

Teisenduskaugus on võimalik arvutada nn. dünaamilise programmeerimise põhimõttel (dynamic programming).

Märgime dij = D( a1a2...ai, b1b2...bj ), 0≤i≤m , 0≤ j ≤n.

Teoreem

Olgu d0,0=0 , di,0=i kui 1≤i≤m, ja d0,j=j kui 1≤ j ≤n.

Teisenduskauguse dij ja dmn=D(A,B) saab arvutada rekurrentsist

dij = min di-1, j-1 + ( if ai = bj then 0 else 1 )
di-1, j + 1
di, j-1 + 1
{viimase tähe ekvivalents või teisendus}

{tähe lisamine lõppu}

{tähe kustutamine lõpust}

Tõestus Induktsioon.
  1. Algväärtustamine on korrektne.

    d0,0 = D( ε , ε) = 0,
    di,0 = D( a1a2...ai , ε) = i (kustuta ükshaaval iga A täht)
    d0,j = D( ε , b1b2...bj) = j (lisa ükshaaval järjest iga B täht A-sse)

  2. Induktsiooni samm.

    Oletame, et dkl on õige kui k+l < i+j.

    Vaatleme a1a2...ai ja b1b2...bj viimaste tähtede võimalikke teisndusi. Neid on kolm:

    1. ai → bj (muutus või ekvivalents): lühim võimalik teisenduste hulk on di-1, j-1 + ( if ai = bj then 0 else 1 )

    2. ai → ε (bj kas muudeti või oli ekvivalentne ai-1'ga). Lühim teisenduste arv on di-1, j + 1.

    3. ε → bj (ai kas oli ekvivalentne või muudetud bj-1). Lühim teisenduste arv on di, j-1 + 1.

    4. Olukorda kus korraga nii ai → ε kui ε → bj ei ole vaja vaadelda, sest selle pikkus on di-1, j-1 + 2 > di-1, j-1 + 1 (vrdl. 1.)

    Lühim teisenduste arv a1a2...ai → b1b2...bj on pikkuse poolest võimaluste 1, 2 ja 3 miinimum, nii et teoreemi rekkurents on korrektne. M.O.T.T.

Väärtused dij võib arvutada kasutades vaheväärtuste tabeldust ehk dünaamilist programmeerimist (DP).



Algoritm Teisenduskauguse D(A,B) arvutamine DP abil (baasversioon).
Sisend: A=a1a2...am, B=b1b2...bm
Väljund: Väärtus dmn maatriksis (dij), 0≤i≤m, 0≤j≤n.

1. for i=0 to m do di0=i
2. for j=0 to n do d0j=j

3. for j=1 to n do 
4.     for i=1 to m do 
5.         dij = min(
6.		di-1, j-1 + (if ai==bj then 0 else 1), 
7.		di-1, j + 1,
8.		di, j-1 + 1  )

Näide D( baacb , abacbc ).

D( baacb , abacbc ) = 3.

Ajaline keerukus on Θ(mn)

Baasversiooni mahuline keerukus on ka Θ(mn) ehk maatriksi (dmn) suurus.

Vaatame seda täpsemalt.


http://www.merriampark.com/ld.htm (Tee ise Excelis vastav...)

Tagasi

Teisenduskauguse parima lahenduse raporteerimine


Tagasi

Teisenduskauguse arvutamine diagonaali meetodiga

Maatriksi (fkp) arvutamine veerge pidi.

  • Diagonaali meetodi mahuline keerukus.

  • Rakendustes on sageli huvitavad vaid väikesed D(A,B). Algoritmi saab muuta nii et ette antakse parameeter t mida suuremad teisenduskaugused ei ole huvitavad. Selline algoritm töötab ajas O(tm) ehk seda kiiremini mida váiksem on t.

  • Mälumahtu saab vähendada hoides vaid eelmist veergu.

  • Kuidas leida lühim tee õige vastuseni? See on suhteliselt lihtne, algoritm töötab ajas O(s) ja väljastab ühe võimaliku tee.

    Tagasi

    Üldistusi

    Transpositsioon - tähtede järjekorra muutmine

    Üldistatud teisenduskaugus


    Tagasi

    Pikim ühine alamjada


    Tagasi

    Aja painutamine (Time warp)


    Tagasi

    Bioloogilisi kauguste mõõte


    Vaata eestikeelseid referaate:

    Smith-Waterman algoritmi kasutatakse andmebaasidest ligikaudsete vastete otsimiseks. Algoritm kasutab dynaamilist programmeerimist optimaalse joonduse leidmiseks. Lubatud teisendusteks on asendus, stringi lisamine ja kustutamine. Teisendustele saab anda suvalisi kaale, lisamise ja kustutamise v6ib teha s6ltuvaks lisatava/kustutava stringi pikkusest. Tavaliselt antakse tapsetele vastetele positiivsed kaalud ja teisendustele ka 0-kaalud v6i siis negatiivsed kaalud. Parimaks vasteks loetakse joondust, mille viimase operatsiooni kaal on suurim.

    Smith-Waterman algoritm sarnaneb Needleman-Wunsch algoritmiga, kuid erinevalt viimasest algoritmist (mis on globaalne, s.t. leitakse alati kogu otsitava stringi joondus), on antud algoritm lokaalne (joondus algab ja l6peb alati tapse vastega).

    Algorigm Smith-Waterman
    Sisend:  A, B, N = |A|, M=|B| (kus A, B on stringid, mida v6rreldakse)
             Wgap(k) funktsioon, mis annab "augule" pikkusega k negatiivse kaalu
             Wmatch(a, b) funktsioon, mis annab tahtede a ja b seotuse hinnangu
    Valjund: TRACE protseduuri kaudu valjastatakse "trace"
    
    best_i = 0
    best_j = 0
    
    for j=0 to N do H(0, j)=0
    for i=1 to M do
        H(i, 0)=0
        for j=1 to N do
            w=max(w, H(i-1,j-1)+(Wmatch(A[i-1], B[j-1])
            for k=i-1 to 1 do w=max(w, H(i-k, j-1) + Wgap(k))
            for l=j-1 to 1 do w=max(w, H(i-1, j-l) + Wgap(l))
            H(i, j)=max(w, 0)
            if H(i, j)>H(best_i, best_j) then best_i=i; best_j=j
    
    while H(best_i, best_j)>0 do
        TRACE(best_i, best_j)
        n=best_i--
        m=best_j--
        for i=1 to n-1 do
            if H(i, m)>H(best_i, best_j) then best_i=i; best_j=m
        for j=1 to m-1 do
            if H(n, j)>H(best_i, best_j) then best_i=n; best_j=j
    
    
    Funktsioonid Wmatch ja Wgap tuleks valida rakendusvaldkonna statistilistest 
    seadusparasustest lahtudes. K6ige lihtsam valik oleks
    
    Wmatch(a, b) = (a == b ? 1 : -1);
    Wgap(k)      = penalty0 + k*delta_penalty (penalty0 ja delta_penalty tuleks fikseerida)
    

    Smith-Watermani algoritm

    Smith-Watermani algoritm leiab kahe sõne osasõned, mis on omavahel parima vastavusega. Smith-Watermani algoritmi töö sarnaneb lihtsa dünaamilise programeerimise rakendamisega sõnede teisenduskauguse leidmiseks. Juurde tuleb faktor, mis arvestab vahe pikkust - sõltuvalt valitud kaaludest saame eelistada pikki või lühikesi vahesid.

    Tabelit täidetakse analoogiliselt teisenduskauguse tabeliga. Rekurrentne seos omandab aga natuke teise kuju.
    Maksimum võetakse:
    1) Osasõnede viimaste tähtede võrdlemisel saadud koefitsent + tähe võrra lühemate sõnede skoor
    2) Maksimum esimese osasõne iga prefiksi skoor + vahe pikkuse pealt arvutatud vahe skoor
    3) Maksimum teise osasõne iga prefiksi skoor + vahe pikkuse pealt arvutatud vahe skoor

    Kasutatavad konstandid on järgmised:
    GAP_PENALTY - kaal vahe alustamisel
    GAP_EXTENSION - kaal olemasoleva vahe jätkamisel
    MATCH_PENALTY - kaal tähtede klappimise korral
    MISMATCH_PENALTY - kaal tähtede erinevuse korral

    Algoritm

    SwTable(String A, String B):
    
    table[i][0] = 0, 0 <= j <= length(B)
    table[0][i] = 0, 0 <= i <= length(A)
    
    for(i = 1; i <= length(A); ++i)
        for(j = 1; j <= length(B); ++j)
            maxRow = -INFINITY;
    	maxColumn = -INFINITY;
    	
    	// leia parim vahe skoor tulbas
    	maxColumn = max(maxColumn, table[i - k][j] - gapScore(k)); 0 < k < i
    	// leia parim vahe skoor reas
    	maxRow = max(maxColumn, table[i][j - k] - gapScore(k)); 0 < k < j
    
            table[i][j] = max(         // uus väärtus on maksimum neljast 
    			table[i-1][j-1] + letterScore(Ai, Bj),
    			maxRow,
    			maxColumn,
    		        0          // negatiivseid väärtusi pole vaja lubada
    			);
    
    
    gapScore(k) = GAP_PENALTY + GAP_EXTENSION*k
    		    
    letterScore(c, d) = MATCH_PENALTY ,   if c =  d
                        MISMATCH_PENALTY, if c != d
    
    Leitud tabeli põhjal saab leida ka parima joondamise.

    Algoritm

    SwAlign:
    
    bestScore = -INFINITY;
    bestx = 0, besty = 0;
    alignPos = 0;
    String alignA, alignB;
    
    // leiame tabeli suurima väärtuse
    bestScore = max(table[i][j]);  1 <= i <= length(A) ; 1 <= j <= length(B)
    bestx = bestScore.x;
    besty = bestScore.y;
    
    alignA[alignPos] = A[besty - 1];  // salvestame parima joonduse viimased tähed
    alignB[alignPos] = B[bestx - 1];  
    alignPos = alignPos + 1;
    
    while(bestScore != 0) // kuni leiame parima vastavuse alguse
        /** leiame eelmise rea ja veeru suurima väärtuse osas, mis jääb 
            tabelis vasakule ja üles                                       */
        bestScore = max(table[i][bestx - 1]);  1 <= i < besty            
        bestScore = max(bestScore, table[besty - 1][j]);  1 <= j < bestx 
        newBestx = bestScore.x;
        newBesty = bestScore.y;
    
        /** kui tegu on asendusega, lisame mõlemast sõnest tähed joondusesse - 
            seda tehakse peale if lauseid                                  */
        if(newBestx == bestx - 1 && newBesty == besty - 1) 
            ;
        /** kui tegu on pikema vahega, sisestame vajalikul määral tühikuid */
        else if(newBestx == bestx - 1)
            while(besty - 1 > newBesty)
                alignA[alignPos] = A[besty - 1];
                alignB[alignPos] = '-';
                alignPos = alignPos + 1;
                besty = besty - 1;
        else // newBesty == besty - 1
            while(bestx - 1 > newBestx)
                alignA[alignPos] = '-';
                alignB[alignPos] = B[bestx - 1];
                alignPos = alignPos + 1;
                bestx = bestx - 1;
    
        /** Sõlutmata eelnevast tulevad parimasse joondusesse kõrvuti uue 
            parima skooriga tähed                                         */
        alignA[alignPos] = A[newBesty - 1];
        alignB[alignPos] = B[newBestx - 1]
        alignPos = alignPos + 1;
    
        bestx = newBestx;
        besty = newBesty;
    
    

    Teisenduste hinna tabelid