Алгоритм Боуера и Мура

КМП-алгоритм дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае слово сдвигается более чем на единицу. К несчастью, это скорее исключение, чем правило: совпадения встречаются значительно реже, чем несовпадения. Поэтому выигрыш от использования КМП-алгоритма в большинстве случаев поиска в обычных текстах весьма незначителен. Метод же, предложенный Р. Боуером и Д. Муром в 1975 г. (БМ-алгоритм), не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях.

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

Рисунок 38. Пример работы БМ-алгоритма

Далее приводится функция на языке Паскаль с упрощенным БМ-алгоритмом, построенная так же, как и предыдущая программа с КМП-алгоритмом.

function BMTxtSearch(var Wrd: TWrd;

var Txt: TText;

var Position: integer): boolean;

{Функция поиска слова Wrd в тексте Txt,}

{если слово найдено, то возвращает значение true}

{и позицию Position начала первого слова Wrd,}

{иначе – false и Position не изменяется}

var

i, {Индекс начала слова в тексте}

j: integer; {Индекс текущ.символа слова}

ch: char;

Shift: array[' '..'я'] of integer; {Массив смещений}

begin

{Заполнение массива Shift}

for ch:=' ' to 'я' do Shift[ch] := M;

for j:=1 to M do Shift[Wrd[j]] := M-j;

{Поиск слова Wrd в тексте Txt}

i := 1; {Начало слова совпадает с началом текста}

repeat

j := M+1; {Сравнивать будем с последнего символа}

{Посимвольное сравнение слова, начиная с правого символа}

repeat

j := j-1;

until (j < 1) or (Wrd[j] <> Txt[i+j-1]);

if j >= 1 then

i := i + (j + Shift[Txt[i+j-1]] - M); {Сдвиг слова вправо}

until (j < 1) or (i > N-M+1); {Оценка результатов поиска}

if j < 1 then begin

BMTxtSearch := true;

Position := i;

end else begin

BMTxtSearch := false;

end;

end;

Почти всегда, кроме специально построенных примеров, данный алгоритм требует значительно меньше O(N) сравнений. В самых же благоприятных обстоятельствах, когда последний символ слова всегда попадает на несовпадающий символ текста, число сравнений пропорционально O(N/M).

Авторы алгоритма приводят и несколько соображений по поводу дальнейших усовершенствований алгоритма. Одно из них – объединить приведенную только что стратегию, обеспечивающую большие сдвиги в случае несовпадения, со стратегией Кнута, Морриса и Пратта, допускающей «ощутимые» сдвиги при обнаружении совпадения (частичного). Такой метод требует двух таблиц, получаемых при предтрансляции: Shift’ – только что упомянутая таблица, а Shift’’ – таблица, соответствующая КМП-алгоритму. Из двух сдвигов выбирается больший. Дальнейшее обсуждение этого предмета приводить не будем, поскольку дополнительное усложнение формирования таблиц и самого поиска, возможно, не оправдает видимого выигрыша в производительности. Фактические дополнительные расходы будут высокими и неизвестно, приведут ли все эти ухищрения к выигрышу или проигрышу.