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

В информатике алгоритм Райта представляет собой алгоритм поиска строк , который повышает производительность алгоритма Бойера-Мура-Хорспула . Этот алгоритм предварительно обрабатывает искомую строку для поиска шаблона, что аналогично алгоритму поиска строки Бойера-Мура . Шаблон поиска конкретной подстроки в данной строке отличается от алгоритма Бойера – Мура – ​​Хорспула. Этот алгоритм был опубликован Тимо Райтой в 1991 году.

Описание

Алгоритм Райта ищет шаблон «P» в заданном тексте «T», сравнивая каждый символ шаблона в данном тексте. Поиск будет осуществляться следующим образом. Окно для текста «Т» определяется длиной «Р».

1. Сначала последний символ шаблона сравнивается с самым правым символом окна.
2. Если совпадение есть, первый символ шаблона сравнивается с самым левым символом окна.
3. Если они снова совпадают, средний символ шаблона сравнивается со средним символом окна.

Если все в предварительной проверке прошло успешно, то исходное сравнение начинается со второго до предпоследнего символа. Если на каком-либо этапе алгоритма возникает несоответствие, он выполняет функцию сдвига неправильных символов, которая была вычислена на этапе предварительной обработки. Функция сдвига плохого символа идентична предложенной в алгоритме Бойера-Мура-Хорспула.

Современную формулировку подобной предварительной проверки можно найти в std::string::find, линейное/квадратичное средство сопоставления строк в libc++ и libstdc++. Предполагая, что это хорошо оптимизированная версия memcmp, не пропускать символы в «исходном сравнении», как правило, более эффективно, поскольку шаблон, скорее всего, будет выровнен.

Код C для алгоритма Райта

#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 (i = 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];
  }
}

Пример

Узор: абддб

Текст: отец отец отец

Этап предварительной обработки:

  a b d
  4 3 1

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

Сравнение последнего символа шаблона с самым правым символом в окне. Это несоответствие, оно сдвинуто на 4 в соответствии со значением на этапе предварительной обработки.

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

Здесь последний и первый символы шаблона совпадают, но средний символ не совпадает. Таким образом, рисунок смещается в соответствии с этапом предварительной обработки.

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

Здесь мы нашли точное совпадение, но алгоритм продолжает работать до тех пор, пока не сможет двигаться дальше.

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

На этом этапе нам нужно сдвинуться на 4, и мы не можем сдвинуть шаблон на 4. Итак, алгоритм завершает работу. Буквы, набранные заглавными буквами, точно соответствуют образцу в тексте.

Сложность

1. Этап предварительной обработки занимает время O(m), где «m» — длина шаблона «P».
2. Этап поиска занимает временную сложность O(mn), где «n» — длина текста «T».

См. также

• Алгоритм поиска строк Бойера – Мура
• Алгоритм Бойера – Мура – ​​Хорспула

Внешние ссылки

• Анимация апплета и описание алгоритма Райта