Galil-Giancarlo algoritem/Implementacija (Java)

Iz MaFiRaWiki

 
public class GalilGiancarlo
{
	private char[] niz;   //niz iz katerega luščimo vzorce
	private char[] x;     //vzorec katerega iščemo v nizu
	private int[] h;      //pozicije trenutno primerjanega elementa
	private int[] shift;  //število elementov, ki jih lahko preskočim v nizu
	private int[] next;   //število elemntov, ki jih lahko preskočim v vzorcu
	private int n;        //velikost vzorca   
	private int m;        //velikost niza 
 
    //konstruktor
	public GalilGiancarlo(char[] iskalniNiz, int m, char[] vzorec, int n)
	{
		this.niz = new char[m];
   		this.niz = iskalniNiz;
   		this.x = new char[n+1];
   		
   		for(int i = 0; i < n; i++)
   		  x[i] = vzorec[i];
   	    x[n] = ' ';
   		     
   		this.n = n;
   		this.m = m;
   		this.h = new int[n+1];
		this.shift = new int[n+1];
		this.next = new int[n+1];
	}
	//metoda, ki dobi potrebne podatke iz vzorca za hitrejše primerjanje z nizom
	public int preGalilGiancarlo()
	{
	   int[] hmax = new int[n+1];
	   int[] kmin = new int[n+1];	
       int[] rmin = new int[n+1];
       int[] nhd0 = new int[n+1];
	   int i = 1;
	   int k = 1;
	   int q = 0;
	   int m = n;
	   int r = 0;
	   int s = -1;
	   
       //preračunamo indekse elementov, ki niso luknje
	   do
	   {	 
	     //dokler se dela niza ujemata nadaljuj
	   	 while(x[i] == x[i - k])
	       i++;
	   	   //indeks elementa, ki ni luknja
	 	   hmax[k] = i;
	   	   q = k + 1;
	   	   //dodamo vmesne elemente, ki zaradi ujemnja podnizov v nizu zgoraj odpadejo
	       while(hmax[q - k] + k < i)
	  	   {
	   	     hmax[q] = hmax[q - k] + k;
	   	     q++;
	   	   }
	   	   k = q;
	   	   //če se niz ni ujemal
	   	   if(k == i + 1)
	   	     i = k;
	   }while(k <= m);//delamo dokler ne dosežemo velikosti vzorva + 1
	  
      //določimo preskoke, ki jih naredimo, ko pride do neujemnja pri elementih,
      //ki niso luknje    
	  for(i = m; i >= 1; i--)
	    if(hmax[i] < m)
	      //indeksu v hmax-u priredimo vrednost i
	      kmin[hmax[i]] = i;
 
      //določimo preskoke, ki jih naredimo, ko pride do neujemnja pri elementih,
      //ki so luknje    
	  for(i = m - 1; i >= 0; --i)
	  {
	  	//v primeru, ko se vzorec od i-tega elementa naprej ujema z vzorcem od 0 
	  	//elementa naprej
	  	if(hmax[i + 1] == m)
	  	  r = i + 1;
	  	//če je luknja  
	  	if(kmin[i] == 0)
	  	  rmin[i] = r;
	  	else
	  	  rmin[i] = 0;
	  }
 
	  //določimo tabelo indeksov, po kateri bomo primerjali vzorec z tekstom 
	  r = m;
	  for(i = 0; i < m; i++)
	  {
	  	if(kmin[i] == 0)
	  	  h[--r] = i;//luknje dodajamo iz desne proti levi
	  	else
	  	  h[++s] = i;//elemente, ki niso luknje pa od leve proti desni
	  }
 
	  //število elementov ki niso lukje
	  int nd = s;
 
      //shift nam pove koliko elementov lahko v naslednjem poizkusu preskočimo
	  for(i = 0; i <= nd; i++)
	    shift[i] = kmin[h[i]];//za elemete, ki so luknje
	  for(i = nd + 1; i < m; ++i)
	    shift[i] = rmin[h[i]];//za elemete, ki niso luknje
	  shift[m] = rmin[0];//če se celoten niz ujema
	  
	  //nhd0 nam pove koliko lukenj imamo do tega elementa v vzorcu
	  s = 0;
	  for(i = 0; i < m; ++i)
	  {
	  	nhd0[i] = s;//dodamo vrednost na i-tem mestu
	  	if(kmin[i] > 0)
	  	  ++s;
	  }
 
	  //next nam pove koliko elemntov na začetku nam ni treba ponovno primerjati
	  //ker se že ujemajo 
	  for(i = 0; i <= nd; ++i)
	    //število elementov, ki niso luknje med indeks tekočega elementa - vrednostjo preskoka
	    next[i] = nhd0[h[i] - kmin[h[i]]];
	  for(i = nd + 1; i < m; ++i)
	    //število elementov, ki so luknje med velikostji vzorca - vrednostjo preskoka 
	    next[i] = nhd0[m - rmin[h[i]]];
	  next[m] = nhd0[m - rmin[h[m - 1]]]; 
	  
	  return nd;//vrnemo število elementov, ki niso luknje
	}
	
    //metoda vrne stevilo ponovitev vzorca v niz-u
	public int GalilGiancarlo()
	{	
	  int i;  //kje v vzorcu stojimo
	  int j;  //kje v tekstu stojim
	  int k; //število elemntov ki se ujema pri kateri se prepona ujema z pripona
	  int ell; //število enakih elementov, ki se na začetku ponovi
	  int last; //do kje v tekstu se trenutno vzorec ujema
	  int nd; //število nelukenj
	  int ponovitve; //vračamo število ujemanj
      boolean heavy; //pomaga pri določanju, ko se ujemajo vse neluknje 
      
      ponovitve = 0;
      
      //pogledamo število enakih znakov v vzorcu na začetku
      for(ell = 0; x[ell] == x[ell+1]; ell++);
      //če imamo samo enake znake delamo malo drugače
      if(ell == n-1)
      {
      	//gremo skozi celoten niz
      	for(j = ell = 0; j < n; ++j)
        {
          //če se znak ujema 	
      	  if(x[0] == niz[j])
      	  {
      	  	//povečamo število trenutno ujemajočih znakov
      	  	++ell;
      	  	//če je to večje ali enako velikosti vzorca povečamo
      	  	//število najdenih zadetkov
      	  	if(ell >= n)
      	  	  ponovitve++;
      	  }
      	  //če znak ni isti potem je število zadetkov enako nič
      	  else
      	    ell = 0;
        }	
      }
      //če nimamo enakih znakov potem
      else
      {
      	//najprej preračunamo potrebne podatke za hitro iskanje
      	nd = preGalilGiancarlo();
      	//postavimo začetne vrednosti
      	i = j = 0;
      	heavy = false;
      	last = -1;
      	//delamo dokler vzorec še v celoti pade v primerjani niz 
      	while(j <= m - n)
      	{
          //če so se ujemali vsi elementi, ki niso luknje		
      	  if(heavy && i == 0)
      	  {
      	  	k = last - j + 1;//določimo koliko elementov se že ujema
      	  	while(x[0] == niz[j + k])//dokler so elementi isti, kot prvi element nadaljuj
      	  	  k++;
      	  	//če se prvi različni element od prvega elementa vzorca razlikujeta ter se ujema kvečjemu 
      	  	//število enakih elementov na začetku, lahko gremo za k + 1 koraov naprej 
      	  	if(k <= ell || x[ell + 1] !=  niz[j + k])
      	  	{
      	  	  i = 0;
      	  	  j += (k + 1);
      	  	  last = j - 1;
      	  	}
      	  	//drugače pa na j + k - ell - 1 mesto
      	  	else
      	  	{
      	  	  i = 1;
      	  	  last = j + k;
      	  	  j = last - (ell + 1);	
      	  	}
        	heavy = false;
       	  }
       	  else
       	  {
       	  	//primerjamo dokler se znaki ujemajo ali pa ne pridemo do konca niza
       	  	while(i < n && last < j + h[i] && x[h[i]] == niz[j + h[i]])
       	  	  i++;
       	  	//če se celoten niz ujema potem povečamo število ponovitev
       	  	if(i >= n || last >= j + h[i])
       	  	{
       	  	  ponovitve++;
       	  	  i = n;	
       	  	}  
       	  	//če je število ujemanj znakov večje kot število lukenj
       	  	if(i > nd)
       	  	  last = j + n - 1;
       	  	//gremo za preskok naprej  
       	  	j += shift[i];
       	  	//koliko vrednosti se že ujema s tekstom
       	  	i = next[i]; 
       	  }
       	  //ali je potrebno posebno preverjanje
       	  heavy = (j > last ? false : true);
      	}
      }
      
      return ponovitve;//vračamo število ponovitev
  }
}
Osebna orodja