Uporedjivanje nizova

Edit distance problem 

Formirati algoritam koji za dve reči dužine n (prva reč), m (druga reč) nad azbukom slova i cifara 
pronalazi niz operacija editovanja najmanje cene kojim se prva reč transformiše u drugu reč. 
Dozvoljene su tri vrste operacija editovanja i svaka ima cenu jedan:
insert = umetanje jednog karaktera
delete = brisanje 1 karaktera
replace = zamena jednog karaktera drugim karakterom

Primer za A=maak, B=amaa
A(1)=amaak /*insert slovo a u reč A*/ 
A(2)=amaa /*delete slovo k iz reči A*/ 
CENA: 1+1=2
 
A(1)=aak /*delete slovo m iz reči A*/ 
A(2)=amak /*insert slovo m u reči A*/ 
A(3)=amaa /*replace slovo k slovom a u reči A */ 
CENA: 1+1+1=3

Operacija editovanja najmanje cene zapravo predstavlja Levenshtein ili edit rastojanje dve niske. 
Nazvana je po ruskom naučniku (Vladimir Levenshtein) koji se 1965. bavio ovim rastojanjem.

Koristi se u aplikacijama u kojima je potrebno znati koliko su slične dve niske, na primer:
1. spell checker-i (provera pravopisa)
Spell checkeri porede reč sa ulaza sa jedinicom rečnika. Ako reč nije pronađena u rečniku, 
smatra se da nije korektno uneta i izlistavaju se moguće reči iz rečnika, počev od onih sa 
najmanjom Levenshtein udaljenosti od ulazne reči.
2. aplikacije molekularne biologije (DNK analiza; što je veći stepen sličnosti dve sekvence, 
bilo DNK, RNK ili amino-kiselina, to im je sličnija i funkcija ili struktura, 
npr. kod multiplskleroze koja to bakterijska ili virusna sekvenca iz ranije infekcije je slična sekvenci 
proteinske mijelinske ovojnice )
3. detekcija plagijata
4. prepoznavanje govora

Što je Levenštajnovo rastojanje dve niske veće, to se one više razlikuju među sobom!!!

Procena sličnosti dve niske može se utvrditi na osnovu Levenštajnovog rastojanja ili LCS algoritmom koji 
pronalazi najdužu zajedničku podsekvencu (podsekvenca se dobija iz niske brisanjem 0 ili više karaktera). 
Oba algoritma će biti navedena kao ilustracija tehnike dinamičkog programiranja.

Inače, današnje softverske alatke koriste više metrika, a često i njihovu kombinaciju. 
Neke metrike su pogodnije za oblast molekularne biologije, neke za oblast text mining-a.

Neka su A = a₁a₂...aₙ i B = b₁b₂...bₘ dva data stringa. Cilj je transformisati string A u string B, znak po znak, pri čemu postoje tri dozvoljene elementarne transformacije (tzv. edit operacije) cene 1:

Zadatak je za date stringove A i B odrediti niz edit operacija najmanje cene koji tranformiše string A u string B. Za početak dovoljno je odrediti samo broj operacija.

Problem rešavamo na sledeći način:

Sa A(i) oznčavamo prefiks stringa A dužine i, slično za string B. Zadatak je odrediti rastojanje d(A(n), B(m)).

Početni uslovi:

Za računanje rastojanja d(A(i), B(k)) gledamo koja edit operacija može biti poslednja u nizu operacija koje A(i) prevode u B(k):

Najmanji broj edit operacija jednak je onda:

    d(A(i), B(k)) = min {
        d(A(i − 1), B(k − 1)) + c(i, k),
        d(A(i), B(k − 1)) + 1,
        d(A(i − 1), B(k)) + 1
    }

pri čemu je:

              ⎧  0,  za aᵢ = bₖ
    c(i, k) = ⎨
              ⎩  1,  za aᵢ ≠ bₖ

Označavamo element matrice C[i, k] = d(A(i), B(k)) i onda svaki element matrice izračunavamo preko 3 već izračunata elementa matrice: elementa iznad, elementa levo i elementa gore-levo.

Do kompletnog niza edit operacija dolazi se prolazeći elemente matrice "unazad".

Svaki element matrice se izračunava preko 3 prethodna, tj u konstantnom vremenu, pa je vremenska složenost: O(mn). Prostorna složenost je isto O(mn), ali može biti i O(m) jer se naredna vrsta računa samo na osnovu prethodne – ali u ovom slučaju ne bismo mogli da rekonstruišemo niz edit operacija.

    editRastojanje(A, n, B, m) {
        for (i ∈ 1 .. n) {
            C[i, 0] = i;
        }

        for (k ∈ 1 .. m) {
            C[0, k] = k;
        }

        for (i ∈ 1 .. n) {
            for (k ∈ 1 .. m) {
                x = C[i - 1, k] + 1;
                y = C[i, k - 1] + 1;
                z = (A[i] == B[k])
                        ? C[i - 1, k - 1]
                        : C[i - 1, k - 1] + 1;

                C[i, k] = min { x, y, z }
            }
        }
    }

Primer

Primer formiranja matrice cena za niske "SAMBA" i "SIMBAD".

Koraci 1, 2

 

 

S

A

M

B

A

 

0

1

2

3

4

5

S

1

 

 

 

 

 

I

2

 

 

 

 

 

M

3

 

 

 

 

 

B

4

 

 

 

 

 

A

5

 

 

 

 

 

D

6

 

 

 

 

 

Koraci od 3 do 6 kada i = 1

 

 

S

A

M

B

A

 

0

1

2

3

4

5

S

1

0

 

 

 

 

I

2

1

 

 

 

 

M

3

2

 

 

 

 

B

4

3

 

 

 

 

A

5

4

 

 

 

 

D

6

5

 

 

 

 

Koraci od 3 do 6 kada i = 2

 

 

S

A

M

B

A

 

0

1

2

3

4

5

S

1

0

1

 

 

 

I

2

1

1

 

 

 

M

3

2

2

 

 

 

B

4

3

3

 

 

 

A

5

4

3

 

 

 

D

6

5

4

 

 

 

Koraci od 3 do 6 kada i = 3

 

 

S

A

M

B

A

 

0

1

2

3

4

5

S

1

0

1

2

 

 

I

2

1

1

2

 

 

M

3

2

2

1

 

 

B

4

3

3

2

 

 

A

5

4

3

3

 

 

D

6

5

4

4

 

 

Koraci od 3 do 6 kada i = 4

 

 

S

A

M

B

A

 

0

1

2

3

4

5

S

1

0

1

2

3

 

I

2

1

1

2

3

 

M

3

2

2

1

2

 

B

4

3

3

2

1

 

A

5

4

3

3

2

 

D

6

5

4

4

3

 

Koraci od 3 do 6 kada i = 5

 

 

S

A

M

B

A

 

0

1

2

3

4

5

S

1

0

1

2

3

4

I

2

1

1

2

3

4

M

3

2

2

1

2

3

B

4

3

3

2

1

2

A

5

4

3

3

2

1

D

6

5

4

4

3

2

Rastojanje je u donjoj desnoj ćeliji, tj. 2, što odgovara i inuitivnoj realizaciji da se niska "SAMBA" može transformisati u nisku "SIMBAD" zamenom slova "A" slovom "I" i dodavanjem slova "D" (1 zamena i 1 umetanje = 2 operacije ).

   

Zadaci

Zadatak 1

Odrediti edit rastojanje stringova A = bccd i B = cbcc.

Rešenje:

    | A/B |  0  | 1 c | 2 b | 3 c | 4 c |
    |  0  | [0] | [1] |  2  |  3  |  4  |
    | 1 b |  1  |  1  | [1] |  2  |  3  |
    | 2 c |  2  |  1  |  2  | [1] |  2  |
    | 3 c |  3  |  2  |  2  |  2  | [1] |
    | 4 d |  4  |  3  |  3  |  3  | [2] |

Niz operacija: umetanje, zamena po istom karakteru tri puta, brisanje.

Rekonstrukcija transformacija iz A u B:

  1. ukloni d iz A
  2. umetni c na pocetak A

Zadatak 2

Uopštiti algoritam za nalaženje edit rastojanja na slučaj kada se umetanja znakova na početku ili na kraju jednog od nizova ne računaju. Drugim rečima, ako se A uklapa u B, onda ne računamo umetanja potrebna za povećanje A, računamo samo edit rastojanje niza A i podniza B u koji se uklapa.

Uputstvo: Predloženi algoritam bi se, takodje, zasnivao na dinamičkom programiranju, odnosno računanju matrice svih edit rastojanja prefiksa A(i) i B(k), 0 ≤ i ≤ m, 0 ≤ k ≤ n, pri čemu se menja odgovarajuća rekurentna veza, kao i prva vrsta matrice:

    C(0, k) = 0, jer se umetanja na početak ne računaju

              ⎧  min { x, y + 1, z }  za 1 ≤ i < m
    C(i, k) = ⎨
              ⎩  min { x, y, z }      za i = m

    x = min { C[i - 1, k] + 1
    y = C[i, k - 1]
    z = C[i - 1, k - 1] + c(aᵢ, bₖ)

Zadatak 3

Primeniti prethodni algoritam na niske bc i abcd.

    | A/B |  0  | 1 a | 2 b | 3 c | 4 d |
    |  0  | [0] | [0] |  0  |  0  |  0  |
    | 1 b |  1  |  1  | [0] |  1  |  1  |
    | 2 c |  2  |  2  |  1  | [0] | [0] |

Zadatak 4

Najveći zajednički podniz (LCS) dva niza X i Y je najduži niz L koji je podniz oba niza X i Y. Kažemo da je niz x = (x₁, x₂, ..., xₖ) podniz niza y = (y₁, y₂, ..., yₘ) ako i samo ako postoji strogo rastući niz indeksa (iᵢ, i₂, ..., iₖ) takav da za svako j = 1, 2, ..., k važi: y(i(j)) = x(j). Na primer niz z = (A, N, A) je podniz niza y = (G, L, A, D, N, A).

Napisati algoritam koji za data dva niza X, Y pronalazi dužinu najdužeg zajedničkog podniza dva data niza.

ULAZ				
X:3 2 4 1 5 8 7 3 6 9
Y: 2 7 5 1 7 3 4 2 6
Napomena: Najduži zajednički podniz (LCS, longest common subsequence) je 2 1 7 3 6  ili 2 5 7 3 6.

Šta je stanje u ovom DP problemu? 
Stanje DP[x][y] definišemo kao duzinu LCS u prvih x+1 elemenata prvog niza X i prvih y+1 elemenata niza Y.

Šta je relacija u ovom DP problemu? 
Jednostavno dizajniramo DP algoritama koristeci induktivni pristup, 
tj. pretpostavimo da smo rešili potproblem za prefiks niza X dužine x-1 i prefiks niza Y dužine y-1:

     Ako X[x]!=Y[y], onda: DP[x][y]=max{DP[x][y-1],   DP[x-1][y] }
        Novo stanje mozemo izracunati prosirujuci pre izracunato stanje po x ili po y.


   Ako X[x]=Y[y], onda: DP[x][y]=max{DP[x][y-1],   DP[x-1][y],    DP[x-1][y-1]+1 }
     Ako su elementi X[x], Y[y] jednaki, mozemo prosiriti stanje DP[x-1][y-1] i dodati 1, 
	 jer LCS ce biti produzen za jos jedan clan tj. X[x] (ili Y[x]).



    LCS(X, n, Y, m) {

        for (i ∈ 0 .. n) {
            C[i, 0] = 0;
        }
        for (j ∈ 0 .. m) {
            C[0, j] = 0;
        }

        for (i ∈ 1 .. n) {
            for (j ∈ 1 .. m) {
                x = C[i - 1, j];
                y = C[i, j - 1];
                z = X[i] == Y[j]
                        ? C[i - 1, j - 1] + 1
                        : C[i - 1, j - 1];

                C[i, j] = max { x, y, z };
            }
        }
    }


Zadatak 5


Primeniti algoritam na niske X = (B, A, N, A, N, A) i Y = (B, R, A, N, A).


    | X/Y |  0  | 1 B | 2 R | 3 A | 4 N | 5 A |
    |  0  | [0] |  0  |  0  |  0  |  0  |  0  |
    | 1 B |  0  | [1] | [1] |  1  |  1  |  1  |
    | 2 A |  0  |  1  |  1  | [2] |  2  |  2  |
    | 3 N |  0  |  1  |  1  |  2  | [3] |  3  |
    | 4 A |  0  |  1  |  1  |  2  |  3  | [4] |
    | 5 N |  0  |  1  |  1  |  2  |  3  | [4] |
    | 6 A |  0  |  1  |  1  |  2  |  3  | [4] |