2015-04-12
3583
Этот алгоритм тоже состоит в сдвигах образца S после неудачного сравнения на максимально возможное число позиций вдоль A с таким расчетом, чтобы не пропустить возможность удачного сравнения. Однако расчет величины сдвига базируется на совершенно других соображениях. В алгоритме проверяется, какая буква алфавита в A сопоставлялась с последней буквой S, и при сдвиге пропускаются все те положения S, которые заведомо вызовут несравнение этой же буквы A с сопоставленной ей буквой в S.
Работа начинается с расчета вспомогательного числового массива R. Каждый элемент этого массива соответствует одной из букв используемого алфавита. На практике, если используется однобайтовая кодировка символов, удобно использовать массив длиной 256 элементов, однако можно не заполнять элементы, соответствующие «непечатным» кодам.
Значения элементов массива R зависят от строки-образца S и рассчитываются по следующим правилам:
· Если bk (буква алфавита с кодом k) не содержится в строке S или же содержится только в последней позиции S, то rk = m.
· В противном случае rk равно расстоянию от самого правого вхождения bk до последней позиции S; при этом не учитывается возможное вхождение bk в последней позиции 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, кроме последней, значение rk, где k – код буквы sj, устанавливается равным m – j, т.е. расстоянию от позиции j до последней позиции m. Если одна и та же буква входит в S несколько раз, то будет запомнено ее наименьшее ненулевое расстояние до m.
А теперь можно начинать поиск. Подстрока-образец S, как и в предыдущих алгоритмах, подписывается под началом строки поиска A. Однако сравнение букв выполняется справа налево, пока не будет найдена пара несовпадающих букв. В этом случае для алгоритма оказывается важным только одно: под какой буквой строки A была подписана последняя буква подстроки S? Перед новым циклом сравнения следует выполнить сдвиг подстроки S на значение rk для этой буквы из 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), что совпадает с оценкой для алгоритма КМП. При внимательном рассмотрении можно сделать вывод, что алгоритм КМП работает быстрее, если имеется много частичных совпадений начальной части образца с отрезками строки поиска. Напротив, алгоритм БМ более эффективен, если совпадений мало. Для реальных текстов это более вероятная ситуация.
Предпринимались попытки объединить оба алгоритма в единый комплекс, однако выигрыш от этого оказался сомнителен.
