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

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

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

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

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

Последний пример на рис. 2.2 показывает: так как pj равно A вместо F, то соответствующий символ текста не может быть символом A из-за того, что условие si<>pj заканчивает цикл. Следовательно, сдвиг на 5 не приведет к последующему совпадению, и поэтому можно увеличить размер сдвига до шести. Учитывая это, предопределяем вычисление dj как поиск самой длинной совпадающей последовательности с дополнительным ограничением pdj<>pj. Если никаких совпадений нет,

Рис. 2.2. Частичное совпадение со словом и вычисление d _j.

то считается dj=-1, что указывает на сдвиг «на целое» слово относительно его текущей позиции. Следующая программа демонстрирует КМП-алгоритм.

Program KMP;

const

Mmax = 100; Nmax = 10000;

var

i, j, k, M, N: integer;

p: array[0..Mmax-1] of char; {слово}

s: array[0..Mmax-1] of char; {текст}

d: array[0..Mmax-1] of integer;

begin

{Ввод текста s и слова p}

Write('N:'); Readln(N);

Write('s:'); Readln(s);

Write('M:'); Readln(M);

Write('p:'); Readln(p);

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

j:=0; k:=-1; d[0]:=-1;

while j<(M-1) do begin

while(k>=0) and (p[j]<>p[k]) do k:=d[k];

j:=j+1; k:=k+1;

if p[j]=p[k] then

d[j]:=d[k]

else

d[j]:=k;

end;

{Поиск слова p в тексте s}

i:=0; j:=0;

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

while (j>=0) and (s[i]<>p[j]) do j:=d[j]; {Сдвиг слова}

i:=i+1; j:=j+1;

end;

{Вывод результата поиска}

if j=M then Writeln('Yes') {найден }

else Writeln('No'); {не найден}

Readln;

end.

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

Поиск по сайту: