Алгоритм Раита - Википедия - Raita algorithm

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

Описание

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

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

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

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

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

#включают <limits.h>#включают <stddef.h>#define ALPHABET_SIZE (1 << CHAR_BITS) / * обычно 256 * // * Предварительная обработка: таблица плохого соответствия BMH. * /статический в соответствии пустота preBmBc(char *погладить, size_t lpat, ptrdiff_t bmBc[]) {  size_t я;  за (я = 0; я < ALPHABET_SIZE; ++я)    bmBc[я] = lpat;  за (я = 0; я < lpat - 1; ++я)    bmBc[погладить[я]] = lpat - я - 1;}пустота RAITA(char *погладить, size_t lpat, char *s, size_t п) {  ptrdiff_t bmBc[ALPHABET_SIZE];  / * Быстрые крайние случаи. * /  если (lpat == 0 || lpat > п)    возвращаться;  если (lpat == 1) {    char *match_ptr = s;    пока (match_ptr < s + п) {      match_ptr = мемхр(match_ptr, погладить[0], п - (match_ptr - s));      если (match_ptr != НОЛЬ) {        ВЫХОД(match_ptr - s);        match_ptr++;      } еще        возвращаться;    }  }  preBmBc(погладить, lpat, bmBc);  / * Предварительное окно. * /  char firstCh = погладить[0];  char middleCh = погладить[lpat / 2];  char lastCh = погладить[lpat - 1];  / * Поиск * /  ptrdiff_t j = 0;  пока (j <= п - м) {    char c = s[j + lpat - 1];    / * Это может повредить локальность данных в длинных шаблонах. Для них рассмотрите возможность сокращения     * количество предварительных тестов или использование более кластерных индексов. * /    если (lastCh == c && middleCh == s[j + lpat / 2] && firstCh == s[j] &&        memcmp(&погладить[1], &s[j+1], lpat - 2) == 0)      ВЫХОД(j);    j += bmBc[c];  }}

Пример

Узор: abddb

Текст: abbaabaabddbabadbb

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

  а б г 4 3 1
 Попытка 1: abbaabaabddbabadbb .... b Сдвиг на 4 (bmBc [a])

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

 Попытка 2: abbaabaabddbabadbb A.d.B Сдвиг на 3 (bmBc [b])

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

 Попытка 3: abbaabaabddbabadbb ABDDB Сдвиг на 3 (bmBc [b])

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

 Попытка 4: abbaabaABDDBabadbb .... b Сдвиг на 4 (bmBc [a])

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

Сложность

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

Смотрите также

Рекомендации

  1. ^ а б RAITA T., 1992, Настройка алгоритма поиска строк Бойера – Мура – ​​Хорспула, Программное обеспечение - Практика и опыт, 22 (10): 879-884 [1]
  2. ^ «⚙ D27068 Улучшить строку :: найти». Обзор кода LLVM.

внешняя ссылка