3. Алгоритм Бойера – Мура

Этот алгоритм тоже состоит в сдвигах образца Sпосле неудачного сравнения на максимально возможное число позиций вдольAс таким расчетом, чтобы не пропустить возможность удачного сравнения. Однако расчет величины сдвига базируется на совершенно других соображениях. В алгоритме проверяется, какая буква алфавита вAсопоставлялась с последней буквойS, и при сдвиге пропускаются все те положенияS, которые заведомо вызовут несравнение этой же буквыAс сопоставленной ей буквой вS.

Работа начинается с расчета вспомогательного числового массива R. Каждый элемент этого массива соответствует одной из букв используемого алфавита. На практике, если используется однобайтовая кодировка символов, удобно использовать массив длиной 256 элементов, однако можно не заполнять элементы, соответствующие «непечатным» кодам.

Значения элементов массива Rзависят от строки-образцаSи рассчитываются по следующим правилам:

• Если b_k(буква алфавита с кодомk) не содержится в строкеSили же содержится только в последней позицииS, тоr_k = m.

• В противном случае r_kравно расстоянию от самого правого вхожденияb_kдо последней позицииS; при этом не учитывается возможное вхождениеb_kв последней позицииS.

Немножко запутанно? На самом деле, все очень просто. Для полной ясности приведем фрагмент программы, рассчитывающий элементы массива R.

...

for k := 0 to 255 do

r[k] := M;

for j := 1 to M - 1 do

r[Ord(S[j])] := M – j;

...

Сначала весь массив заполняется значением m, а затем для каждой позицииjстрокиS, кроме последней, значениеr_k, гдеk– код буквыs_j, устанавливается равнымm – j, т.е. расстоянию от позицииjдо последней позицииm. Если одна и та же буква входит вSнесколько раз, то будет запомнено ее наименьшее ненулевое расстояние доm.

А теперь можно начинать поиск. Подстрока-образец S, как и в предыдущих алгоритмах, подписывается под началом строки поискаA. Однако сравнение букв выполняется справа налево, пока не будет найдена пара несовпадающих букв. В этом случае для алгоритма оказывается важным только одно: под какой буквой строкиAбыла подписана последняя буква подстрокиS? Перед новым циклом сравнения следует выполнить сдвиг подстрокиSна значениеr_kдля этой буквы изA. Дело в том, что при меньшем сдвиге эта буква изAникак не сможет совпасть с подписанной под ней буквой изS.

Все становится понятным на примере. Рассмотрим пример на рис. 7.2, где в строкеA= ‘acabaababcaabababa’ ищется подстрокаS= ‘ababa’. Предварительно рассчитаем значенияr[‘a’] = 2,r[‘b’] = 1 иr[‘c’] = 5.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

A:

a

c

a

b

a

a

b

a

b

c

a

a

b

a

b

a

b

a

Шаг 1:

a

b

a

b

a

Шаг 2:

a

b

a

b

a

Шаг 3:

a

b

a

b

a

Шаг 4:

a

b

a

b

a

Шаг 5:

a

b

a

b

a

Шаг 6:

a

b

a

b

a

Рис. 7.2. Пример работы алгоритма Бойера-Мура

На шаге 1 подстрока Sподписана под началом строкиA(в позициях с 1 по 5). При сравнении букв справа налево несовпадение обнаруживается в позиции 2 (‘c’  ‘b’). При этом в позиции 5 строкиA(напротив последней буквыS) находилась буква ‘a’. Выполняя сдвиг направо подстрокиS, мы должны сделать так, чтобы в той позицииS, которая теперь будет стоять напротив позиции 5 строкиA, тоже была буква ‘a’ (иначе наверняка будет несовпадение). Тут-то и пригодится значениеr[‘a’] = 2, которое показывает, что ближайшая к концуSбуква ‘a’ находится за 2 позиции от конца. Значит сдвигSследует сделать на 2 позиции направо.

На шаге 2 подстрока Sподписана под позициями 3 – 7 строкиA. При сравнении справа налево не совпадает уже первая пара букв в позиции 7 (‘b’  ‘a’). Посколькуr[‘b’] = 1, сдвиг можно выполнить только на одну позицию, тогда под позицией 7 окажется требуемая буква ‘b’.

Шаг 3: позиции 4 – 8 строки A. При сравнении – несовпадение в позиции 5 (‘a’  ‘b’). Выполняется сдвиг на две позиции.

Шаг 4: позиции 6 – 10 строки A. При сравнении – несовпадение в позиции 10 (‘c’  ‘a’). Посколькуr[‘c’] = 5, выполняется сдвиг сразу на пять позиций. Действительно, буква ‘c’ вообще отсутствует вS, а потому надо сдвинутьSтак далеко, чтобы выйти за позицию буквы ‘c’.

Дальнейшее понятно.

Описанный алгоритм реализуется следующей функцией.

function BMSearch(A: StringN; S: StringM): Integer;

var

i, j: Integer;

r: array[0..255] of Integer;

begin

{Вычислениеr[k]}

for k := 0 to 255 do

r[k] := M;

for j := 1 to M - 1 do

r[Ord(S[j])] := M – j;

{Поиск}

i := M;

j := M;

while (j > 0) and (i <= N) do begin

j := M;

k := i;

while (j > 0) and (A[k] = S[j]) do begin

j := j – 1;

k := k – 1;

end

i := i + r[Ord(A[i])];

end;

if j <= 0 then

BMSearch := k + 1 {Успех}

else

BMSearch := 0; {Неудача}

end; {BMSearch}

Время работы алгоритма БМ оценивается как T_макс(n, m) = O(n+m), что совпадает с оценкой для алгоритма КМП. При внимательном рассмотрении можно сделать вывод, что алгоритм КМП работает быстрее, если имеется много частичных совпадений начальной части образца с отрезками строки поиска. Напротив, алгоритм БМ более эффективен, если совпадений мало. Для реальных текстов это более вероятная ситуация.

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