Galil-Giancarlo algoritem/Prva faza(Giancarlo)

Iz MaFiRaWiki

V prvi fazi Galil-Giancarlo algoritma analiziramo vzorec ter si zapolnimo podatke, ki nam v drugi fazi pomagajo pri iskanju vzorca v tekstu. Pri tej analizi določimo tri tabele, ki jih v drugi fazi uporabimo:

  1. tabelo, v kateri si po vrsti sledijo indeksi elementa, ki ga primerjamo na tekočem koraku
  2. tabelo, v kateri si po indeksih sledijo elementi, ki jih lahko v tekstu preskočimo, ko pride do neujemanja
  3. tabelo, v kateri si po indeksih sledijo elementi s številom začetnih elementov v vzorcu, ki nam jih ni potrebno primerjati, če pride do neujemanja.

Seveda, da učinkovito pridemo do teh tabel si moramo pomagati s pomožnimi tabelami, in sicer:

  • Najprej izračunajmo tabelo hmax, ki je definirana kot je razvidno spodaj
  1. X[k..hmax[k]-1] = X[0..hmax[k]-k-1]
  2. X[hmax[k]] ≠ X[hmax[k]-k].


Iz definicije je razvidno, da so vrednosti, ki jih iščemo ravno indeksi elementov v vzorcu, ki niso luknje.

Primer:

G C G G C A G G  
0 1 2 3 4 5 6 7 indeks
0 1 3 5 4 5 7 8 hmax

Prvi znak je poseben, ker se po njem določa elemnte, ki so in niso luknje zato je vedno enak nič.

  1. Vzemimo indeks 1: Izbrati moramo tak hmax[k], da se bodo znaki od indeksa naprej ujemali z znaki z začetka vzorca. Torej iščemo tako vrednost pri hamx[1] da bomo imeli čim daljše ujemanje X[1..hmax[1]-1] = X[0..hmax[1]-1-1]. Vzeti moramo tak največji hmax[1] do bo zgornji pogoj izpolnjen. To pa je v primeru, ko vzamemo hmax[1] = 1 in dobimo X[1..0] = X[0..-1] ter X[1] ≠ X[0].
  2. Vzemimo indeks 2: X[2..hmax[2]-1] = X[0..hmax[2]-2-1] vidimo da je X[2..2] = X[0..0] zato je hmax[2] = 2+1 = 3
  3. Vzemino indeks 3: X[3..hmax[3]-1] = X[0..hmax[3]-3-1] vidimo da je X[3..4] = X[0..1] zato je hmax[3] = 4+1 = 5
  4. Vzemino indeks 4: X[4..hmax[4]-1] = X[0..hmax[4]-4-1] vidimo da je X[4..3] = X[0..-1] zato je hmax[4] = 3+1 = 4
  5. Vzemino indeks 5: X[5..hmax[5]-1] = X[0..hmax[5]-5-1] vidimo da je X[5..4] = X[0..-1] zato je hmax[5] = 4+1 = 5
  6. Vzemino indeks 6: X[6..hmax[6]-1] = X[0..hmax[6]-6-1] vidimo da je X[6..6] = X[0..0] zato je hmax[6] = 6+1 = 7
  7. Vzemino indeks 7: X[7..hmax[7]-1] = X[0..hmax[7]-7-1] vidimo da je X[7..7] = X[0..0] zato je hmax[7] = 7+1 = 8

Kot vidimo iz primera smo res dobili samo znake, ki niso luknje. To se zgodi , ker se v primeru, ko se pojavi luknja vsaj en znak ujema z znakom iz začetka vzorca tako, da indeks kjer je luknja ravno preskočimo.


  • Ko imamo enkrat indekse elementov, ki niso luknje s pomočjo tega lahko dobimo število znakov, ki jih v primeru, ko pride do neujemanja s tekstom lahko preskočimo. Te elemente shranimo v tabelo kmin. To storimo na sledeč način

Primer:

G C G G C A G G  
0 1 3 5 4 5 7 8 hmax
0 1 0 2 4 3 0 6 kmin

Najprej opazimo, da moramo vrednosti 8 in 0 izločiti, ker je vrednost 0 indeks prvega elementa, ki je vedno luknja medtem, ko vrednost 8 že presega velikost vzorca. Do tega pride v primeru, ko se konec vzorca ujema z začetkom vzorca. Ker so vrednosti, ki so shranjene v hmax ravno vrednosti indeksa elementa, do katerega se predpona tekočega znaka ujema z pripona vzorca (primer: GCA se ujema z začetkom do črke A zato vrednost 5) vidimo, do so indeksi tabele hmax ravno vrednosti preskočenih elementov znaka, ki je na indeksu shranjenem v hmax. Iz tega sledi, da je kmin[hmax[i]] = i, kjer je i indeks s katerim se sprehajamo skozi hmax. Opazimo še, da se moramo po indeksih i sprehajati od največjega do najmanšega, ker bi v nasprotnem primeru dobili za znak A, da lahko preskoči 5 znakov kar pa nebi bilo pravilno.


  • Sedaj želimo izračunati še število znakov, ki jih lahko preskočimo v primeru, ko nastopi znak, ki je luknja. Te vrednosti shranimo v tabelo rmin. Glede na to da smo do tega trenutka že pregledali vse elementa, ki niso luknje je jasno, da lahko v primeru, ko pride do neujemanja gremo naprej za celoten vzorec. Razen v primeru, ko se vzorec od luknje naprej ujema z začetkom vzorca. V tem primeru se lahko premaknemo le do luknje, ki sledi luknji, ki se ne ujema, kajti konec vzorca se od tu naprej ujema z začetkom vzorca. Iz prej vemo tudi, da so luknje ravno tam kjer je kmin[i] = 0 in da se primerjave delajo iz desne proti levi.

Primer:

G C G C G C G C  
0 1 8 3 8 5 8 7 hmax
0 1 0 3 0 5 0 7 kmin
2 0 4 0 6 0 8 0 rmin

Iz primera vidimo, da se lahko res premaknemo samo do naslednje luknje, kajti v tem primeru se konec vzorca ujema z začetkom vzorca.


  • Če želimo elemente primerjati s tekstom tako kot narekuje Galil-Giancarlo algoritem. Za učinkovito delo potrebujemo tabelo, v kateri imamo po vrsti shranjene indekse elementov, katere bomo v tekočem koraku primerjali. Te elemente shranimo v tabelo h. Ker vemo od prej, da imamo v tabeli kmin shranjene vrednosti preskočenih znakov, ko pride do neujemanja na tekočem koraku, če so elementi, ki niso luknje (drugače kmin = 0) in v rmin vrednosti preskočenih znakov, ko pride do neujemanja na tekočem koraku na elementih, ki so luknje (drugače rmin = 0). Iz tega sledi, da so indeksi, ki jih primerjamo v tekočem koraku sledijo tako, da najprej zapišemo indekse elementov tabele kmin ≠ 0 od leve proti desni in nato še indekse elementov tabele rmin ≠ 0 od desne proti levi.

Primer:

G C G C G C G C  
0 1 8 3 8 5 8 7 hmax
0 1 0 3 0 5 0 7 kmin
2 0 4 0 6 0 8 0 rmin
1 3 5 7 6 4 2 0 h


  • Ko imamo enkrat zgornje tabele lahko hitro dobimo tabelo shift, ki nam povedo število preskočenin znakov na tekočem koraku, ko pride do neujemnja. Z razmislekom ugotovimo, da s pomočjo tabel kmin, rmin, h dobimo vrednosti tabele shift na sledeč način. Vemo, da je prvih nd elementov v tabeli h elementov, ki niso luknje ter ostalih od nd + 1 elementov naprej, elementov, ki so luknje. Tako vidimo, da je prvih nd elementov v tabeli shift, če gre i od 0 do nd enakih shift[i] = kmin[h[i]]. Ostali elementi od nd + 1 naprej pa so enaki shift[i] = rmin[h[i]].

Primer:

G C G C G C G C  
0 1 8 3 8 5 8 7 hmax
0 1 0 3 0 5 0 7 kmin
2 0 4 0 6 0 8 0 rmin
1 3 5 7 6 4 2 0 h
1 3 5 7 8 6 4 2 shift

Vzemino indeks i = 0, ker vemo od prej, da so prvi štirje elementi, ki so luknje lahko vzamemo
shift[0] = kmin[h[0]] = kmin[1] = 1
Vzemino indeks i = 2
shift[2] = kmin[h[2]] = kmin[5] = 5
Vzemino indeks i = 6, ker vemo, da ta indeks že presega štiri elemente je potem
shift[6] = rmin[h[6]] = rmin[2] = 4
To je možno zato ker imamo v tabeli h podpisane indekse glede na tabeli kmin in rmin.


  • Za izračun tabele vrednosti znakov, ki jih lahko preskočimo v primeru, ko pride do neujemnja na tekočem koraku, pa potrebujemo še eno pomožno tabelo, in sicer tabelo, v kateri imamo število elemetov, ki niso luknje na tekočem koraku in jo poimenujemo z ndh0. Ker je prvi element vedno luknja, so vrednosti v tabeli ndh0 vedno manše kot pa tekoči indeks. Elemente tabele dobimo tako, da se zapeljemo čez vse indekse vzorca ter tabeli ndh0 priredimo vrednost trenutnega števila lukenj. Trenutno število lukenj pa povečamo v primeru, ko je kmin različen od nič. Kar je seveda pogoj za nastop elementa, ki ni luknja.

Primer:

G C G G C C C G  
1 3 4 5 6 7 2 0 h
0 1 0 2 4 3 6 0 kmin
0 0 1 1 2 3 4 5 ndh0

Kot vidimo iz primera večamo vrednosti ndh0 ravno v primerih, ko je kmin ≠ 0.


  • Zadnji korak analize vzorca je izračun števila znakov, ki niso luknje in nam jih ni treba ponovno preverjati, če pride do neujemanja na tekočem koraku. Te vrednosti shranimo v tabelo next. Do vrednosti pridemo z naslednjim razmislekom, in sicer glede na spodnji primer 1.1. Recimo, da pride do neujemanja na zadnjem znaku, ki je luknja, potem se lahko premaknemo za dva znaka naprej, ker pa se naslednjih 6 znakov naprej ujema (smo jih že primerjali) lahko elemente, ki niso luknje tukaj preskočimo. To pa je ravno število lukenj, ki se pojavi v prvih 6 elementih. Iz tega sledi ndh0[vel - rmin[h[i]]] kjer je vel velikost vzorca. Števila preskočenih znakov, ko elemeti so luknje pa vzemimo spodnji primer 1.2. Recimo, da pride do neujemanja na 4 elementu. Kot se vidi v spodnjem primeru se lahko premaknemo za 3 polja naprej, vendar pa se vidi, da smo prvi element, ki je luknja že primerjali zato ga lahko preskočimo. To pa dobimo tako, da dobimo število elementov (ki niso luknje), ki se pojavijo med indeksom pri kateri pride do neujemanja ter števila znakov, ki jih lahko preskočimo in dobimo ndh0[h[i] - kmin[h[i]]].

Primer 1.1:

G C G C G C G C  
1 3 5 7 6 4 2 0 h
0 1 0 3 0 5 0 7 kmin
0 0 1 1 2 2 3 3 ndh0
0 0 0 0 0 1 2 3 next

next[6] = ndh0[8 - rmin[h[7]]] = ndh[8 - 4] = ndh0[4] = 2
next[7] = ndh0[8 - rmin[h[8]]] = ndh[8 - 2] = ndh0[6] = 3


Primer 1.2:

G C G G C C C G  
1 3 4 5 6 7 2 0 h
0 1 0 2 4 3 6 0 kmin
0 0 1 1 2 3 4 5 ndh0
0 0 0 1 0 0 0 0 next

next[3] = ndh0[h[3] - kmin[h[3]]] = ndh0[5 - 2] = ndh0[3] = 1
next[4] = ndh0[h[4] - kmin[h[4]]] = ndh0[6 - 6] = ndh0[0] = 0

Osebna orodja