Алгоритм Бойера – Мура – ​​Хорспула - Boyer–Moore–Horspool algorithm

В Информатика, то Алгоритм Бойера – Мура – ​​Хорспула или же Алгоритм Хорспула является алгоритм для поиска подстроки в струны. Это было опубликовано Найджел Хорспул в 1980 году как SBM.[1]

Это упрощение Алгоритм поиска строки Бойера – Мура что связано с Алгоритм Кнута – Морриса – Пратта. Алгоритм обменивает пространство на время, чтобы получить средняя сложность из На) на случайном тексте, хотя он O (нм) в худший случай, где длина узора м а длина поисковой строки равна п.

Описание

Как и Бойер-Мур, Бойер-Мур-Хорспул предварительно обрабатывает шаблон для создания таблицы, содержащей для каждого символа в алфавит, количество символов, которые можно безопасно пропустить. Фаза предварительной обработки в псевдокоде выглядит следующим образом (для алфавита из 256 символов, т.е. байтов):

В отличие от оригинала, здесь используются индексы с отсчетом от нуля.функция препроцесс (шаблон) T ← новая таблица из 256 целых чисел за я из 0 к 256 эксклюзивный        T [i] ← длина (шаблон) за я из 0 к длина (выкройка) - 1 эксклюзивный        T [шаблон [i]] ← длина (шаблон) - 1 - i возвращаться Т

Поиск по шаблону происходит следующим образом. Процедура поиск сообщает индекс первого появления иголка в стог сена.

функция такой же (str1, str2, len) Сравнивает две строки до первых len символов.    i ← len - 1 пока str1 [i] = str2 [i] Примечание: это эквивалент! Memcmp (str1, str2, len).        если я = 0 Исходный алгоритм здесь пытается действовать умно: он проверяет            возвращаться истинный последний символ, а затем начинается с первого до предпоследнего.        я ← я - 1 возвращаться ложныйфункция поиск (иголка, стог сена) T ← препроцесс (игла) пропустить ← 0 пока длина (стог сена) - пропуск ≥ длины (игла) haystack [skip:] - подстрока, начинающаяся с "skip". & стог сена [пропустить] в C.        если такой же (стог сена [пропустить:], игла, длина (игла)) возвращаться пропустить пропустить ← пропустить + T [стог сена [пропустить + длина (игла) - 1]] возвращаться не найден

Спектакль

Алгоритм лучше всего работает с длинными строками игл, когда он последовательно встречает несоответствующий символ в конце или около последнего байта текущей позиции в стоге сена, и последний байт иглы не встречается где-либо еще в игле. Например, 32-байтовая игла, оканчивающаяся на «z», поиск в 255-байтовой стоге сена, в которой нет байта «z», потребует до 224-байтовых сравнений.

Наилучший случай такой же, как для алгоритма поиска строки Бойера – Мура в нотация большой O, хотя постоянные накладные расходы на инициализацию и для каждого цикла меньше.

Наихудший случай происходит, когда пропуск неверных символов постоянно невелик (с нижним пределом перемещения в 1 байт), а большая часть иглы соответствует стогу сена. Пропуск неверного символа является низким только при частичном совпадении, когда последний символ стрелки также встречается в другом месте внутри стрелки, при этом перемещение одного байта происходит, когда один и тот же байт находится в обеих из последних двух позиций.

Канонический вырожденный случай, аналогичный приведенному выше «лучшему» случаю, представляет собой иглу байта 'a', за которой следует 31 байт 'z' в стоге сена, состоящем из 255 байтов 'z'. Это выполнит 31 успешное сравнение байтов, 1 байтовое сравнение, которое завершится неудачно, а затем продвинется на 1 байт вперед. Этот процесс повторится еще 223 раза (255–32), в результате чего общее количество сравнений байтов составит 7168 (32 × 224). (Другой цикл сравнения байтов будет вести себя иначе.)

Наихудший случай значительно выше, чем для алгоритма поиска строки Бойера – Мура, хотя, очевидно, этого трудно достичь в обычных случаях использования. Также стоит отметить, что этот наихудший случай также является наихудшим для наивных (но обычных) memmem () алгоритм, хотя его реализация имеет тенденцию быть значительно оптимизированной (и более дружественной к кешу).

Настройка цикла сравнения

Исходный алгоритм имел более сложный цикл same (). Он использует дополнительную предварительную проверку, прежде чем двигаться в положительном направлении:[1]

функция same_orig (str1, str2, len) i ← 0 если str [len - 1] = str2 [len - 1] пока str1 [i] = str2 [i] если я = len - 2 возвращаться правда i ← i + 1 возвращаться ложный

Настроенная версия алгоритма BMH - это Алгоритм Раита. Он добавляет дополнительную предварительную проверку для среднего символа в порядке последний-первый-средний. Алгоритм входит в полный цикл только после прохождения проверки:[2]

функция same_raita (str1, str2, len) i ← 0 mid ← len / 2 Три предварительные проверки.    если len ≥ 3 если str [mid]! = str2 [mid] возвращаться ложный если len ≥ 1 если str [0]! = str2 [0] возвращаться ложный если len ≥ 2 если str [len - 1]! = str2 [len - 1] возвращаться ложный Любой старый цикл сравнения.    возвращаться len <3 или же ЖЕ (& str1 [1], & str2 [1], len - 2)

Неясно, сохраняет ли эта настройка 1992 года преимущество в производительности на современных машинах. Обоснование авторов состоит в том, что фактический текст обычно содержит некоторые шаблоны, которые могут быть эффективно предварительно отфильтрованы этими тремя символами. Похоже, что Раита не знает о старой предварительной проверке последнего символа (он считал, что одно и тоже является реализацией Horspool), поэтому читателям рекомендуется относиться к результатам с недоверием.[2]

На современных машинах библиотеки работают как memcmp имеет тенденцию обеспечивать лучшую пропускную способность, чем любой из рукописных циклов сравнения. Поведение цикла «SFC» (терминология Хорспула) как в libstdc ++, так и в libc ++, похоже, предполагает, что современная реализация Raita не должна включать какие-либо односимвольные сдвиги, поскольку они оказывают пагубное влияние на выравнивание данных.[3][4] Также см String-search_algorithm который имеет подробный анализ других алгоритмов поиска по строкам.

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

  1. ^ а б Р. Н. Хорспул (1980). «Практичный быстрый поиск по строкам». Программное обеспечение - практика и опыт. 10 (6): 501–506. CiteSeerX  10.1.1.63.3421. Дои:10.1002 / spe.4380100608.
  2. ^ а б RAITA T., 1992, Настройка алгоритма поиска строк Бойера-Мура-Хорспула, Программное обеспечение - Практика и опыт, 22 (10): 879-884 [1]
  3. ^ «⚙ D27068 Улучшить строку :: найти». Обзор кода LLVM.
  4. ^ "[PATCH] улучшить алгоритм поиска строк". GCC.

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