Алгоритм Кнута, Морриса и Пратта

Рассмотрим сначала более простой случай. Пусть все символы строки-образца S различны. Начнем сравнивать символы S слева направо с первыми m символами строки A. Допустим, что несравнение символов произошло в позиции k £ m, т.е. первые k–1 букв A и S совпали. С какой позиции A следует начать новое сравнение с S? Поскольку символ a_k–1 = s_k–1, то a_k–1 не может совпасть с предыдущими символами S (потому что все символы S различны). Значит, перед продолжением сравнения строк можно сдвинуть S так, чтобы ее первый символ сравнивался сразу с k-м символом A (т.е. с той позицией A, где было обнаружено несовпадение).

Если в S есть совпадающие символы, рассчитать величину сдвига несколько сложнее.

Определим d_j как длину наибольшей подстроки из S, которая заканчивается в позиции j и совпадает с началом строки S во всех позициях, кроме последней. Это можно подробно расписать таким образом:

s[j – d_j + 1] = s[1],

s[j – d _j + 2] = s[2],

… , (7.1)

s[j – 1] = s[d_j – 1],

но при этом s[j] ¹ s[d_j]).

Если такой подстроки не существует, то положим d_j = 0. Тогда нетрудно показать, что, если первое несовпадение при сравнении символов из A и S произошло на паре символов a_i ¹ s_j, то перед продолжением сравнения следует заменить индекс j на d_j, а значение индекса i не изменять (т.е. надо сдвинуть строку S на j – d_j позиций вдоль строки A). Действительно, поскольку символы a[i – d_j + 1], a[i – d _j + 2], … ,
a[i – 1] успешно сравнились с символами s[j – d_j + 1], s[j – d _j + 2], … , s[j – 1], то они, согласно (7.1), должны сравниться и с символами s[1], s[2], … , s[d_j – 1], а потому сравнение можно продолжать с пары символов a[i] и s[d_j].

Если же значение j стало равно 0, то надо увеличить i и j на единицу, т.е. начать сопоставление символов заново с позиции i + 1 в строке A и с первой позиции в строке S.

Ниже приведены примеры значений d_j, рассчитанных для различных строк-образцов.

Рассмотрим работу алгоритма на примере, показанном на рис. 7.1. В строке A = ‘aabaabaaabaabc’ ищется подстрока S = ‘aabaabc’ (см. выше, пример 3).

Рис. 7.1. Пример работы алгоритма Кнута, Морриса и Пратта

На первом шаге обнаруживается несовпадение букв a_i и s_j при i = 7 и j = 7. Выполняется присваивание j := 4. Сравнение продолжается, пока при i = 9 и j = 6 не происходит очередное несовпадение. Делается присваивание j := 2. На сей раз сравнение проходит успешно.

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

Ниже приведен текст функции, реализующей алгоритм поиска КМП.

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

var

i, j, k: Integer;

d: Array[1..M] of Integer;

begin

{Вычисление d[j]}

j := 1;

k := 0;

d[1] := 0;

while j < M do begin

while (k > 0) and (S[j] <> S[k]) do

k := d[k];

j := j + 1;

k := k + 1;

if S[j] = S[k] then d[j] := d[k]

else d[j] := k;

end;

{Поиск}

i := 1;

j := 1;

while (j <= M) and (i <= N) do begin

while (j > 0) and (A[i] <> S[j]) do

j := d[j];

i := i + 1;

j := j + 1;

end;

if j > M then

KMPSearch := i – j + 1 {Успех}

else

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

end; {KMPSearch}

Можно доказать, что время работы алгоритма КМП T_макс(n, m) = O(n+m). Это значительно лучше, чем оценка O(n×m) для прямого поиска, особенно для длинных строк-образцов.

7.2.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.

Рис. 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), что совпадает с оценкой для алгоритма КМП. При внимательном рассмотрении можно сделать вывод, что алгоритм КМП работает быстрее, если имеется много частичных совпадений начальной части образца с отрезками строки поиска. Напротив, алгоритм БМ более эффективен, если совпадений мало. Для реальных текстов это более вероятная ситуация.

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

Вопросы и упражнения

1. Напишите процедуру поиска трех минимальных элементов массива за один проход.

2. Напишите процедуру поиска k-й порядковой статистики при помощи неполного алгоритма QuickSort.

3. Выполните поиск медианы в массиве A = (48, 72, 3, 14, 35, 65, 88, 89, 95, 6, 5, 65, 21, 24, 77), используя неполный алгоритм QuickSort. В качестве разделяющего использовать первый элемент массива.

4. Выполните поиск образца ‘abbabab’ в строке ‘abbabbabbababb’, используя алгоритм Кнута, Морриса и Пратта.

5. Выполните поиск образца ‘bacab’ в строке ‘aacabacaabacabc’, используя алгоритм Бойера и Мура.

Заключение

В данном пособии были рассмотрены наиболее важные алгоритмы решения задач сортировки и поиска, а также соответствующие структуры данных. Рассмотренные алгоритмы входят в «золотой фонд» программирования, хорошее знакомство с ними следует считать необходимой частью подготовки квалифицированного программиста.

Практическим итогом изучения пособия должно стать обогащение арсенала программиста рядом высокоэффективных средств, позволяющих значительно повысить качество разрабатываемых программ.

Но не менее важна и другая сторона дела. В ходе рассмотрения различных алгоритмов было показано, что выбор более сложного, но высокоэффективного алгоритма позволяет в сотни и тысячи раз ускорить решение задач по сравнению с простыми, «очевидными», но неэффективными алгоритмами. Из этого следует, что тщательный предварительный анализ задачи, оценка эффективности используемых алгоритмов, выбор алгоритма, оптимального в конкретной ситуации – это этапы, без которых невозможна разработка программ на профессиональном уровне. Если данное пособие поможет студенту осознать эту важную истину, задачу автора можно считать выполненной.