Raita algorithm

In computer science, the Raita algorithm is a string searching algorithm which improves the performance of the Boyer-Moore-Horspool algorithm. This algorithm preprocesses the string being searched for the pattern, which is similar to Boyer-Moore string search algorithm. The searching pattern of a particular sub-string in a given string is different from the Boyer-Moore-Horspool algorithm. This algorithm was published by Tim Raita in 1991.

Description

The Raita algorithm searches for a pattern "P" in a given text "T" by comparing each character of the pattern in the given text. Searching is done as follows. The window for a text "T" is defined as the length of "P".

1. First, the last character of the pattern is compared with the rightmost character of the window.
2. If there is a match, the first character of the pattern is compared with the leftmost character of the window.
3. If they match again, it compares the middle character of the pattern with the middle character of the window.

If everything in the pre-check is successful, then the original comparison starts from the second character to the last but one. If there is a mismatch at any stage in the algorithm, it performs the bad character shift function which was computed in the pre-processing phase. The bad character shift function is identical to the one proposed in the Boyer-Moore algorithm.

A modern formulation of a similar pre-check is found in std::string::find, a linear/quadratic string-matcher, in libc++ and libstdc++. Assuming a well-optimized version of memcmp, not skipping characters in the "original comparison" tends to be more efficient as the pattern is likely to be aligned.

C Code for Raita Algorithm

#include <limits.h>
#include <stddef.h>

#define ALPHABET_SIZE (1 << CHAR_BITS) /* typically 256 */

/* Preprocessing: the BMH bad-match table. */
static inline void preBmBc(char *pat, size_t lpat, ptrdiff_t bmBc[]) {
  size_t i;
  for (size_t = 0; i < ALPHABET_SIZE; ++i)
    bmBc[i] = lpat;
  for (i = 0; i < lpat - 1; ++i)
    bmBc[pat[i]] = lpat - i - 1;
}

void RAITA(char *pat, size_t lpat, char *s, size_t n) {
  ptrdiff_t bmBc[ALPHABET_SIZE];

  /* Quick edge cases. */
  if (lpat == 0 || lpat > n)
    return;

  if (lpat == 1) {
    char *match_ptr = s;
    while (match_ptr < s + n) {
      match_ptr = memchr(match_ptr, pat[0], n - (match_ptr - s));
      if (match_ptr != NULL) {
        OUTPUT(match_ptr - s);
        match_ptr++;
      } else
        return;
    }
  }

  preBmBc(pat, lpat, bmBc);

  /* The prematch-window. */
  char firstCh = pat[0];
  char middleCh = pat[lpat / 2];
  char lastCh = pat[lpat - 1];

  /* Searching */
  ptrdiff_t j = 0;
  while (j <= n - m) {
    char c = s[j + lpat - 1];
    /* This could harm data locality on long patterns. For these consider reducing
     * the number of pre-tests, or using more clustered indices. */
    if (lastCh == c && middleCh == s[j + lpat / 2] && firstCh == s[j] &&
        memcmp(&pat[1], &s[j+1], lpat - 2) == 0)
      OUTPUT(j);
    j += bmBc[c];
  }
}

Example

Pattern: abddb

Text:abbaabaabddbabadbb

Pre-processing stage:

  a b d
  4 3 1

 Attempt 1:
 abbaabaabddbabadbb
 ....b
 Shift by 4 (bmBc[a])

Comparison of the last character of the pattern to the rightmost character in the window. It's a mismatch and is shifted by 4 according to the value in the pre-processing stage.

 Attempt 2:
 abbaabaabddbabadbb
     A.d.B
 Shift by 3 (bmBc[b])

Here, the last and first characters of the pattern match, but the middle character is a mismatch. So, the pattern is shifted according to the pre-processing stage.

 Attempt 3:
 abbaabaabddbabadbb
        ABDDB
 Shift by 3 (bmBc[b])

We found an exact match here, but the algorithm continues until it can't move further.

 Attempt 4:
 abbaabaABDDBabadbb
           ....b
 Shift by 4 (bmBc[a])

At this stage, we need to shift by 4, but we can't move the pattern by 4. So the algorithm terminates. Letters in capital letters are an exact match of the pattern in the text.

Complexity

1. The pre-processing stage takes O(m) time, where "m" is the length of pattern "P".
2. The searching stage takes O(mn) time complexity, where "n" is the length of text "T".

See also

• Boyer–Moore string search algorithm
• Boyer–Moore–Horspool algorithm

External links

• Applet animation and Description for Raita Algorithm

This article "Raita algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Raita algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

This page exists already on Wikipedia.

---