УП_САОД_2003

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

Приблизительно в 1970 г. Д. Кнут, Д. Морис и В. Пратт изобрели алгоритм (КМП-алгоритм), фактически требующий только O(N) сравнений даже в самом плохом случае. Новый алгоритм основывается на том соображении, что после частичного совпадения начальной части слова с соответствующими символами текста фактически известна пройденная часть текста и можно «вычислить» некоторые сведения (на основе самого слова), с помощью которых потом можно быстро продвинуться по тексту.

Основным отличием КМП-алгоритма от алгоритма прямого поиска является осуществления сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.

Если j определяет позицию в слове, содержащую первый несовпадающий символ (как в алгоритме прямого поиска), то величина сдвига Shift определяется как j-LenSuff-1. Значение LenSuff определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова. LenSuff зависит только от слова и не зависит от текста. Для каждого j будет своя величина Shift, которую обозначим Shift_j.

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

Приведенный пример поиска слова ABCABD показывает принцип работы такого алгоритма. Символы, подвергшиеся сравнению, здесь подчеркнуты. Обратите внимание: при каждом несовпадении пары символов слово сдвигается на переменную величину, и меньшие сдвиги не могут привести к полному совпадению.

Так как величины Shift_j зависят только от слова, то перед началом фактического поиска можно вычислить вспомогательную таблицу Shift; эти вычисления сводятся к некоторой предтрансляции слова. Соответствующие усилия будут оправданными, если размер текста значительно превышает размер слова (M<<N). Если нужно искать многие вхождения одного и того же слова, то можно пользоваться одной и той же Shift. Приведенные примеры объясняют назначение Shift.

Рисунок 37. Частичное совпадение со словом и вычисление Shift_j

Следующая функция на языке Паскаль демонстрирует КМП-алгоритм.

function KMPTxtSearch(var Wrd: TWrd;

var Txt: TTxt;

var Position: integer): boolean;

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

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

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

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

var

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

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

k, {Индекс текущ.символа суффикса слова}

LenSuff: integer; {Длина суффикса}

Equal: boolean; {Признак совпадения суффикса с началом}

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

begin

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

Shift[1] := 1; Shift[2] := 1; {Для первых двух смещение 1}

{Вычисляем смещение для остальных M-2 символов слова}

for j := 3 to M do begin

Shift[j] := 1; {Предопределенное значение}

{Перебираем все возможные длины суффиксов}

for LenSuff := 1 to j-2 do begin

Equal:=true;

{Сравниваем посимвольно суффикс с началом слова}

for k := 1 to LenSuff do begin

if Wrd[k] <>

Wrd[j-LenSuff+k-1]

then Equal:=false;

end;

{Если суффикс совпал, то Shift - это смещение

от начала слова до начала суффикса}

if Equal then

Shift[j] := j - LenSuff - 1;

end;

{Поиск слова Wrd в тексте Txt, аналогичный прямому,

только смещение не на 1, а на переменный шаг Shift}

i := 0; j := 1; {Начальные значения}

repeat

{Смещение слова}

i := i + Shift[j];

j := 1;

{Посимвольное сравнение}

while (j <= M) and

(Txt[i+j-1] = Wrd[j]) do

j := j+1;

until (j = M+1) or (i >= N-M+1);

{Оценка результатов поиска}

if j = M+1 then begin

KMPTxtSearch := true;

Position := i;

end else begin

KMPTxtSearch := false;

end;

Точный анализ КМП-алгоритма весьма сложен. Его изобретатели доказывают, что требуется порядка O(M+N) сравнений символов, что значительно лучше, чем O((N-M)*M) сравнений при прямом поиске.

Содержание