Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В информатике алгоритм Бойера — Мура — Хорспула, или алгоритм Хорспула, — это алгоритм поиска подстрок в строках. Он был опубликован Найлом Хорспулом в 1980 году под названием SBM. Это упрощение алгоритма поиска строк Бойера — Мура, который связан с алгоритмом Кнута — Морриса — Пратта. Алгоритм жертвует памятью ради скорости, чтобы достичь средней временной сложности O(n) для случайного текста, хотя в худшем случае его сложность составляет O(nm), где m — длина искомой подстроки, а n — длина строки, в которой производится поиск.
In computer science, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980 as SBM. It is a simplification of the Boyer–Moore string search algorithm which is related to the Knuth–Morris–Pratt algorithm. The algorithm trades space for time in order to obtain an average case complexity of O(n) on random text, although it has O(nm) in the worst case, where the length of the pattern is m and the length of the search string is n.
Выступление
Алгоритм показывает наилучшие результаты при работе с длинными образцами поиска, когда он последовательно обнаруживает несовпадающий символ в последнем байте текущей позиции в тексте или рядом с ним, и последний байт образца поиска не встречается больше нигде в самом образце. Например, образец поиска длиной 32 байта, заканчивающийся на "z", при поиске в тексте длиной 255 байт, не содержащем байта "z", потребует до 224 сравнений байтов. Лучший случай соответствует таковому для алгоритма поиска строк Бойера-Мура в нотации «O большое», хотя постоянные накладные расходы на инициализацию и каждый цикл меньше. Наихудшее поведение наблюдается, когда величина пропуска по несовпадающему символу постоянно мала (с нижним пределом смещения в 1 байт) и большая часть образца поиска совпадает с текстом. Пропуск по несовпадающему символу мал только при частичном совпадении, когда последний символ образца поиска также встречается в другом месте внутри самого образца, при этом смещение на 1 байт происходит, когда один и тот же байт находится в двух последних позициях. Канонический вырожденный случай, аналогичный описанному выше "лучшему" случаю, представляет собой образец поиска, состоящий из байта "a", за которым следуют 31 байт "z", в тексте, состоящем из 255 байт "z". Это потребует 31 успешного сравнения байтов, 1 неудачного сравнения байтов и последующего смещения на 1 байт. Этот процесс повторится еще 223 раза (255 − 32), что приведет к общему количеству сравнений байтов 7168 (32 × 224). (Другой цикл сравнения байтов будет вести себя иначе.) В худшем случае производительность значительно ниже, чем у алгоритма поиска строк Бойера-Мура, хотя, очевидно, добиться этого в обычных сценариях использования сложно. Стоит также отметить, что этот наихудший случай также является наихудшим случаем для наивного (но распространенного) алгоритма memcmp, хотя его реализация, как правило, значительно оптимизирована (и более эффективно использует кэш).
The algorithm performs best with long needle strings, when it consistently hits a non matching character at or near the final byte of the current position in the haystack and the final byte of the needle does not occur elsewhere within the needle. For instance a 32 byte needle ending in "z" searching through a 255 byte haystack which does not have a 'z' byte in it would take up to 224 byte comparisons. The best case is the same as for the Boyer–Moore string search algorithm in big O notation, although the constant overhead of initialization and for each loop is less. The worst case behavior happens when the bad character skip is consistently low (with the lower limit of 1 byte movement) and a large portion of the needle matches the haystack. The bad character skip is only low, on a partial match, when the final character of the needle also occurs elsewhere within the needle, with 1 byte movement happening when the same byte is in both of the last two positions. The canonical degenerate case similar to the above "best" case is a needle of an 'a' byte followed by 31 'z' bytes in a haystack consisting of 255 'z' bytes. This will do 31 successful byte comparisons, a 1 byte comparison that fails and then move forward 1 byte. This process will repeat 223 more times (255 − 32), bringing the total byte comparisons to 7,168 (32 × 224). (A different byte comparison loop will have a different behavior.) The worst case is significantly higher than for the Boyer–Moore string search algorithm, although obviously this is hard to achieve in normal use cases. It is also worth noting that this worst case is also the worst case for the naive (but usual) memcmp algorithm, although the implementation of that tends to be significantly optimized (and is more cache friendly).