Просмотр кода страницы Алгоритм Бойера — Мура — Хорспула

'''Алгоритм Бойера — Мура — Хорспула''' — алгоритм [[поиск подстроки|поиска подстроки в строке]], упрощённый вариант [[алгоритм Бойера — Мура|алгоритма Бойера — Мура]]. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах, оценка в среднем от <math>\frac{1}{|\Sigma|}</math> до <math>\frac{2}{|\Sigma|+1}</math> на один символ текста<ref>{{Cite web |url=http://www-igm.univ-mlv.fr/~lecroq/string/node18.html |title=Horspool algorithm<!-- Заголовок добавлен ботом --> |access-date=2012-08-12 |archive-date=2012-08-29 |archive-url=https://web.archive.org/web/20120829203936/http://www-igm.univ-mlv.fr/~lecroq/string/node18.html |deadlink=no }}</ref>. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается.

Впрочем, оценка (''в худшем случае'' на непериодических шаблонах) у АБМХ составляет |''needle''|·|''haystack''| (вместо 3|''haystack''| у Бойера-Мура).

== Описание алгоритма ==
Алгоритм является модификацией [[Алгоритм Бойера — Мура|алгоритма Бойера — Мура]]. Идея алгоритма такова.

'''1. Сканирование слева направо, сравнение в режиме «чёрного ящика».''' Как и в примитивном алгоритме, совмещается начало текста и шаблона, проводится сравнение обычной процедурой «[[memcmp|сравнить участки памяти]]». Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо. Эти «несколько» выбираются в соответствии с такой эвристикой.

'''2. Изменённая эвристика стоп-символа.''' Берём символ текста, оказавшийся над '''последним''' символом шаблона (независимо от того, где случилось несовпадение!). На рисунке это «b».

                              ↓ стоп-символ
 Текст                a b a d b * * * *
 Шаблон               a b b a d
 Следующая проверка       a b b a d

Сдвигаем шаблон так, чтобы под стоп-символом оказалась буква «b» шаблона. Это реализуется с помощью таблицы смещений: для каждого символа алфавита храним максимально возможный сдвиг, не пропускающий стоп-символ. То есть (при нумерации строк с 1): {{nobr|1=''shift''(''c'') = {{!}}''needle''{{!}}−lastpos(''c'', ''needle''[1..{{!}}''needle''{{!}}−1])}}, где lastpos — последнее вхождение символа в строку, {{nobr|''needle''[''a''..''b'']}} — операция взятия подстроки.

Для шаблона «abbad» таблица имеет следующий вид.
{| class="wikitable"
|-
! Символ
| a
| b
| (все остальные)
|-
! Смещение
| 1
| 2
| 5
|}

Для символов, не вошедших в шаблон, величина смещения устанавливается равной длине шаблона — 5. Последний символ шаблона при вычислении таблицы смещений не рассматривается (чревато [[зацикливание]]м).

Таблицу удобнее рассчитывать, проходя по всем символам шаблона:
<source>
  for c=MIN_CHAR..MAX_CHAR
    shift[c] = |needle|
 
  for i=1..|needle|-1
    shift[needle[i]] = |needle|-i
</source>
== Пример работы алгоритма ==
Искомый шаблон — «abbad» (таблица для этого шаблона построена выше).
<pre>
abeccacbadbabbad
abbad</pre>
Накладываем образец на строку. Последний символ исходной строки «с» не содержится в образце. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «с»:
<pre>
abeccacbadbabbad
     abbad</pre>

Три символа образца совпали, а четвёртый — нет. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «d»:
<pre>
abeccacbadbabbad
          abbad</pre>

Последний символ строки «a» не совпадает с символом шаблона. Сдвигаем образец вправо на 1 в соответствии со значением смещения для «a» и получаем искомое вхождение образца:
<pre>
abeccacbadbabbad
           abbad</pre>

== Варианты ==

=== Алгоритм Санди ===
За стоп-символ берём символ, следующий за ''needle''.

=== Алгоритм Райты ===
[[Эмпирический алгоритм]], оптимизированный под [[английский язык|английские]] тексты. Сравнивает последний символ, потом первый, потом средний, потом все остальные; при несовпадении — сдвиг по Хорспулу.

== Достоинства ==
Очень быстр в среднем{{Уточнить}}. Прост в реализации. Использует стандартную функцию сравнения участков памяти, как правило, оптимизированную на ассемблерном уровне под конкретный процессор.

== Недостатки ==
Как и другие алгоритмы семейства Бойера-Мура, не модифицируется на приблизительный поиск, одновременный поиск нескольких строк.

Регрессия на «плохих» данных случается несколько чаще, чем в алгоритме Бойера — Мура. Чем разнообразнее символы в исходном тексте, тем лучше ведёт себя АБМХ.

== Литература ==
* ''Никлаус Вирт'' Алгоритмы и структуры данных. — М.: Невский Диалект, 2006. С. 352. ISBN 5-7940-0065-1

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://algolist.manual.ru/search/esearch/horspool.php Пример реализации алгоритма Хорспула]

{{Строки}}
{{rq|source|wikify}}
[[Категория:Поиск подстроки|Бойера — Мура — Хорспула]]