Raita algoritam

U informatici, Raita algoritam je algoritam za pretragu niski i predstavlja unapređenje Bojer-Mur-Horspolov algoritma. Algoritam vrši pretprocesiranje uzorka koji se traži u tekstu, slično Bojer-Mur algoritmu za pretragu niski. Algoritam je predstavio Tim Raita 1991. godine.

Opis

Raita algoritam vrši pretragu uzorka "P" u datom tekstu "T". Vrši se poređenje karaktera uzorka "P" i karaktera datog teksta "T". Tekst "T" se deli na više celina, a dužina svake te celine odgovara dužini uzoraka "P". Za svaku celinu radimo sledeće:

1. Prvo, poslednji karakter iz uzorka poredimo sa poslednjim karakterom u celini.

2. Ukoliko dođe do poklapanja, porede se prvi karakter iz uzorka i prvi karakter u celini.

3. Ukoliko opet dođe do poklapanja, porede se središnji karakteri.

Ako su sva tri koraka uspešna, vrši se poređenje karaktera od drugog po redu pa do pretposlednjeg. Ukoliko negde dođe do nepoklapanja, vrši se pomeranje karaktera udesno za onoliko mesta koliko je sračunato u funkciji koja se poziva u pretprocesiranju.

C kod za Raita algoritam

#include <stdio.h>
#include <string.h>
#define ASIZE 1000

void preBmBc(char *x, int m, int bmBc[]) 
{
	int i;
	
	for (i = 0; i < ASIZE; ++i)
		bmBc[i] = m;
	for (i = 0; i < m - 1; ++i)
		bmBc[x[i]] = m - i - 1;
}

int RAITA(char *x, int m, char *y, int n) 
{
	int j, bmBc[ASIZE];
	char c, firstCh, *secondCh, middleCh, lastCh;
	int found = 0;

	/* Pretprocesiranje */
	preBmBc(x, m, bmBc);
	firstCh = x[0];
	secondCh = x + 1;
	middleCh = x[m/2];
	lastCh = x[m - 1];

	/* Pretraga */
	j = 0;
	while (j <= n - m) 
	{
		c = y[j + m - 1];
		/* memcmp(const void *str1, const void *str2, size_t n) */
		/* poredi prvih n karaktera niski str1 i str2 */
		if (lastCh == c && 
            middleCh == y[j + m/2] &&
			firstCh == y[j] &&
			memcmp(secondCh, y + j + 1, m - 2) == 0)
		{
			printf("Uzorak pronadjen na poziciji: %d\n", j);
			found=1;
		}
		j += bmBc[c];
	}
	return found;
}

int main()
{
	int n, m, found;
	char tekst[ASIZE];
	char uzorak[ASIZE];
	
	printf ("Unesite tekst koji se pretrazuje:\n");
	scanf ("%s", tekst);
	n=strlen(tekst);
	
	printf ("Unesite uzorak koji se trazi u tekstu:\n");
	scanf ("%s", uzorak);
	m=strlen(uzorak);
	
	found=RAITA(uzorak, m, tekst, n);
	if(found==0)
		printf("Uzorak nije pronadjen u tekstu.\n");
	
	scanf("%d", &found);
	return 0;
}

Primer

Uzorak: abddb Tekst: abbaabaabddbabadbb

U pretprocesiranju dobijamo sledeće vrednosti:

   a b d
   4 3 1

U prvom prolazu kroz petlju nema poklapanja već u prvom uslovu:

   abbaabaabddbabadbb
   ....b
   j=0; c=a;
   Vršimo pomeranje udesno za 4 mesta (c=a).

U drugom prolazu kroz petlju nema poklapanja prilikom poređenja središnjih karaktera:

   abbaabaabddbabadbb
       a.d.b
   j=4; c=b;
   Vršimo pomeranje udesno za 3 mesta.

U trećem prolazu kroz petlju dolazi do poklapanja svih karaktera:

   abbaabaabddbabadbb
          abddb
   j=7; c=b;
   

I kada dođe do poklapanja algoritam nastavlja izvršavanje sve dok ne pretraži ceo tekst. Pa tako vršimo pomeranje udesno ponovo za 3 mesta.

U četvrtom prolazu kroz petlju nema poklapanja već u prvom uslovu:

   abbaabaabddbabadbb
             ....b
   j=10; c=a;

Sada treba izvršiti pomeranje udesno za 4 mesta. Međutim kako nema dovoljno karaktera u tesktu da bi se pomeranje izvršilo, algoritam se završava.

Složenost

1. Pretprocesiranje je složenosti O(m), gde je m dužina uzorka „P“

2. Pretraga je složenosti O(mn), gde je n dužina teksta „T“ u kojem se traži uzorak „P“

S obzirom da složenost zavisi od dužina niske i uzorka ovaj algoritam je naročito pogodan za pretragu kratkih uzoraka.

Vidi još

• Bojer-Mur algoritam za pretragu niski
• Bojer-Mur-Horspolov algoritam

Dodatna literatura

• „Tuning the Boyer-Moore-Horspool String Searching Algorithm”. CiteSeerX 10.1.1.14.7176 . 

Spoljašnje veze

• Applet animation and Description for Raita Algorithm