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

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

Сорт	Поиск подстроки
Структура данных	Нить
Худшая производительность	$O(nm)$
Средняя производительность	$\Theta (n)$

В информатике алгоритм Бойера -Мура-Хорспула или алгоритм Хорспула — это алгоритм поиска подстрок в строках . Он был опубликован Найджелом Хорспулом в 1980 году под названием SBM.

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

Описание

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

 // Unlike the original, we use zero-based indices here.
 function preprocess(pattern)
     T := new table of 256 integers
     for i from 0 to 256 exclusive
         T[i] := length(pattern)
     for i from 0 to length(pattern) - 1 exclusive
         T[pattern[i]] := length(pattern) - 1 - i
     return T

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

// Compares two strings, up to the first len characters.
// Note: this is equivalent to !memcmp(str1, str2, len).
function same(str1, str2, len)
    i := len - 1
    // The original algorithm tries to play smart here: it checks for the
    // last character, and then starts from the first to the second-last.
    while str1[i] == str2[i]
        if i == 0
            return true
        i := i - 1
    return false

function search(needle, haystack)
    T := preprocess(needle)
    skip := 0
    // haystack[skip:] means substring starting at index `skip`. Would be &haystack[skip] in C.
    while length(haystack) - skip >= length(needle)
        if same(haystack[skip:], needle, length(needle))
            return skip
        skip := skip + T[haystack[skip + length(needle) - 1]]
    return -1

Производительность

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

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

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

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

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

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

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

function same_orig(str1, str2, len)
    i ← 0
    if str1[len - 1] = str2[len - 1]
        while str1[i] = str2[i]
            if i = len - 2
                return true
            i ← i + 1
    return false

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

function same_raita(str1, str2, len)
    i ← 0
    mid ← len / 2
    
    Three prechecks.
    if len ≥ 3
        if str[mid] != str2[mid]
            return false
    if len ≥ 1
        if str[0] != str2[0]
            return false
    if len ≥ 2
        if str[len - 1] != str2[len - 1]
            return false

    Any old comparison loop.
    return len < 3 or SAME(&str1[1], &str2[1], len - 2)

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

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

Причины, по которым вам необходимо использовать алгоритм Хорспула

1. Эффективность алгоритма: количество сравнений между шаблоном и текстом сокращается, поскольку избегаются области текста, совпадение которых невозможно. Это дает алгоритму больше времени на более длинный текст.
2. Простота: алгоритм сохраняет эффективный сдвиг плохих символов в подходе Бойера-Мура, но улучшает сдвиг хорошего суффикса, что значительно упрощает реализацию без ущерба для производительности.

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

• Описание алгоритма
• Реализация JavaScript-движка V8, написанная на C++.