Reverse Factor algorithmESMAJSmith algorithmContents
Next: Reverse Factor algorithm Up: ESMAJ Prev: Smith algorithm

Raita algorithm


Main features
Description

Raita designed an algorithm which at each attempt first compares the last character of the pattern with the rightmost text character of the window, then if they match it compares the first character of the pattern with the leftmost text character of the window, then if they match it compares the middle character of the pattern with the middle text character of the window. And finally if they match it actually compares the other characters from the second to the last but one, possibly comparing again the middle character.

Raita observed that its algorithm had a good behaviour in practice when searching patterns in English texts and attributed these performance to the existence of character dependencies.
Smith made some more experiments and concluded that this phenomenon may rather be due to compiler effects.

The preprocessing phase of the Raita algorithm consists in computing the bad-character shift function (see chapter Boyer-Moore). It can be done in O(m+sigma) time and O(sigma) space complexity.

The searching phase of the Raita algorithm has a quadratic worst case time complexity.

The C code

The function preBmBc is given chapter Boyer-Moore algorithm.

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

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

   /* Searching */
   j = 0;
   while (j <= n - m) {
      c = y[j + m - 1];
      if (lastCh == c && middleCh == y[j + m/2] &&
          firstCh == y[j] &&
          memcmp(secondCh, y + j + 1, m - 2) == 0)
         OUTPUT(j);
      j += bmBc[c];
   }
}

The example

Preprocessing phase

Horspool algorithm bmBc table
bmBc table used by Raita algorithm.

Searching phase


References


Reverse Factor algorithmESMAJSmith algorithmContents
Next: Reverse Factor algorithm Up: ESMAJ Prev: Smith algorithm

e-mails: {Christian.Charras, Thierry.Lecroq }@laposte.net
Tue Jan 14 15:03:31 MET 1997
Tue Jan 14 15:03:31 MET 1997