Раита алгоритам

У информатици, Раита алгоритам је алгоритам за претрагу ниски и представља унапређење Бојер-Мур-Хорсполов алгоритма. Алгоритам врши претпроцесирање узорка који се тражи у тексту, слично Бојер-Мур алгоритму за претрагу ниски. Алгоритам је представио Тим Раита 1991. године.

Опис

Раита алгоритам врши претрагу узорка "П" у датом тексту "Т". Врши се поређење карактера узорка "П" и карактера датог текста "Т". Текст "Т" се дели на више целина, а дужина сваке те целине одговара дужини узорака "П". За сваку целину радимо следеће:

1. Прво, последњи карактер из узорка поредимо са последњим карактером у целини.

2. Уколико дође до поклапања, пореде се први карактер из узорка и први карактер у целини.

3. Уколико опет дође до поклапања, пореде се средишњи карактери.

Ако су сва три корака успешна, врши се поређење карактера од другог по реду па до претпоследњег. Уколико негде дође до непоклапања, врши се померање карактера удесно за онолико места колико је срачунато у функцији која се позива у претпроцесирању.

C код за Раита алгоритам

#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;
}

Пример

Узорак: абддб Текст: аббаабаабддбабадбб

У претпроцесирању добијамо следеће вредности:

   a b d
   4 3 1

У првом пролазу кроз петљу нема поклапања већ у првом услову:

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

У другом пролазу кроз петљу нема поклапања приликом поређења средишњих карактера:

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

У трећем пролазу кроз петљу долази до поклапања свих карактера:

   abbaabaabddbabadbb
          abddb
   j=7; c=b;
   

I када дође до поклапања алгоритам наставља извршавање све док не претражи цео текст. Па тако вршимо померање удесно поново за 3 места.

У четвртом пролазу кроз петљу нема поклапања већ у првом услову:

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

Сада треба извршити померање удесно за 4 места. Међутим како нема довољно карактера у тескту да би се померање извршило, алгоритам се завршава.

Сложеност

1. Претпроцесирање је сложености О(м), где је м дужина узорка „П“

2. Претрага је сложености О(мн), где је н дужина текста „Т“ у којем се тражи узорак „П“

С обзиром да сложеност зависи од дужина ниске и узорка овај алгоритам је нарочито погодан за претрагу кратких узорака.

Види још

• Бојер-Мур алгоритам за претрагу ниски
• Бојер-Мур-Хорсполов алгоритам

Додатна литература

• „Тунинг тхе Боyер-Мооре-Хорспоол Стринг Сеарцхинг Алгоритхм”. ЦитеСеерX 10.1.1.14.7176 . 

Спољашње везе

• Апплет аниматион анд Десцриптион фор Раита Алгоритхм