Galil-Giancarlo algoritem/Druga faza(Giancarlo)

Iz MaFiRaWiki

V drugi fazi Galil-Giancarlo algoritma pa pride na vrsto iskanje vzorca v nekem tekstu s pomočjo analize vzorca, ki smo jo naredili v prvi fazi. Iskanje vzorca se v primeru, ko so vsi elementi v vzorcu enaki primerja elemet po elementu in v primeru ko nastopi različen znak postavimo števec enakih elementov na nič drugače pa ga povečamo. V nasprotnem primeru pa iskanje poteka na sledeč način:

Recimo, da v nekem koraku primerjanja primerjamo Y[k..k+m-1] z X[0..m -1] ter pride do neujemanja pri nekem X[h[r]] in Y[k + h[r]] kjer je r 0 ≤ r < m. Potem se lahko v naslednjem koraku premaknemo za shift[r] naprej ter začnemo s primerjanjem pri elementu X[h[next[r]]]. Do izjeme pride v primeru, ko se vsi elementi, ki niso luknje ujemajo v tem primeru se del teksta po koraku še vedno ujema (Y[j..last] = x[0..j - last]). V tem primeru pri tem algoritmu iščemo X[0] ≠ Y[j + k] toliko časa, da pridemo do konca teksta ali pa pridemo do k-ja kjer sta različna. V tem primeru pa lahko pride do dveh različnih situacij

  1. X[l + 1] ≠ Y[j + k] ali pa je zaporednih znakov X[0] kvečjemu l (k ≤ l). V tem primeru se premaknemo za k + 1 polj naprej, in sicer na Y[k + 1..k + m]. Naprej nadaljujemo tako kot na začetku s primerjanjem prvega elementa, ki ni luknja.
  2. X[l + 1] = Y[j + k] ali pa je zaporednih znakov X[0] več kot l (k > l). V tem primeru pa se premaknemo za k - l - 1, in sicer Y[k - l - 1..m + k - l - 2]. Naprej nadaljujemo tako kot na začetku vendar z drugim elementom, ki ni luknja, ki je na poziciji X[l + 1] in ima predpono vzorca, ki se že ujema X[0..l + 1].

Primer:

Niz:

A C C G A G C C G C A G G G G C C G C A G G A G C A

Vzorec:

G C C G C A G G
  • Najperj naredimo analizo vzorca kot je to pokazano v prvi fazi in dobimo sledeče rezultate:
G C C G C A G G    
1 2 4 5 7 6 3 0 0 h
1 2 4 3 6 7 7 7 7 shift
0 0 0 1 0 0 0 0 0 next
  • Kot opazimo imamo dodan še dodatni stolpec kjer so vrednosti, ki jih uporabimo v primeru, ko se celoten vzorec ujema.
A C C G A G C C G C A G G G G C C G C A G G A G C A
G C C G C A G G                                    
  1 2   3                                          
  • Kot je razvidno smo primerjali elemente po indeksih, ki so po vrsti shranjeni v tabeli h. Ker je prišlo do neujemnja na tretjem koraku se sedaj lahko premaknemo za shift[2] naprej in začnemo pri indeksu h[next[2]]. Ker je prišlo do neujemanja na tretjem znaku moramo za preskok vzeti korak-1, kar je 3-1 = 2.

shift[2] = 4 in h[next[2]] = h[0]

A C C G A G C C G C A G G G G C C G C A G G A G C A
        G C C G C A G G                            
          1                                        

shift[0] = 1 in h[next[0]] = h[0]


A C C G A G C C G C A G G G G C C G C A G G A G C A
          G C C G C A G G                          
          8 1 2 7 3 4 6 5                          

V poizkusu, ko pa se vsi elemnti ujemajo pa vzamemo za preskok naprej kar korak, ker v tem primeru ni prišlo do neujemanja.
shift[8] = 7 in h[next[8]] = 0.

  • Ker pa se v tem primeru vsi elementi, ki so niso luknje ujemajo, pride do posebnega primera, ko pregledujemo elemente niza dokler ne naletimo na znak, ki ni enak našemu prvemu znaku v tem primeru znaku G.
A C C G A G C C G C A G G G G C C G C A G G A G C A
                          G G G                    
                          1 2 3                    
  • Ko naletimo na tak znak preverimo, če je ta znak enak prvemu znaku v vzorcu, ki je različen od prvega znaka. V našem primeru je to znak C. Ker se znak C ujema z prvim znakom, se moramo v vzorcu vrniti za število enakih znakov začetka vzorca plus ena zaradi elementa, ki se neujema nazaj. V našem primeru je to za 2 znaka, če bi pa imeli vzorec (GGGCAGAG) pa bi to pomenilo za 4 znake nazaj. Vendar pa nam prvi element, ki ni luknja ni treba ponovno preverjati, ker smo ga že preverjali.
Opomba: Kaj bi zgodilo če se v našem primeru recimo črka C nebi ujemala z črko v nizu recimo, da bi imeli namesto črke C v nizu črko A. V tem primeru pa bi lahko nadaljevali z primerjanjem na naslednjem elementu, ki bi bil za našo črko A v nizu.
A C C G A G C C G C A G G G G A C G C A G G A G C A
                                G C C G C A G G    
A C C G A G C C G C A G G G G C C G C A G G A G C A
                            G C C G C A G G        
                            7   1 6 2 3 5 4        
  • Tukaj bi se sedaj ponovno ponovila zgornja zgodba vendar ker celoten vzorec ne pade več v nadaljevanje niza tukaj prenehamo z iskanjem.
Osebna orodja