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

Простейший алгоритм

Суть метода, о котором пойдет речь ниже, заключается в следующем: мы проверяем, совпадают ли m символов текста (начиная с выбранного) с символами нашей строки, пытаясь примерить шаблон куда только возможно. Естественно, реализовать описанный алгоритм проще всего (код на языке Pascal):

Program SimpleSearch;

Var T : array[1..40000] of char; {выполняет роль текста}

S : array[1..10000] of char; {выполняет роль строки; как и текст, может быть достаточно велика}

i,j : longint;

m,n : longint;

Begin

{Ввод текста и образца}

…

for i:=1 to n-m+1 do

begin

j:=0;

while (j<m) and (S[j+1]=T[i+j]) do {По очереди сравниваем все символы начиная с i-ого}

j:=j+1;

if j=m then {если все символы совпадали}

writeln('Образец входит в текст начиная с ',i,'-ого символа'); {сообщение о нахождении строки в тексте}

end;

End.

Просто и элегантно, вроде так и надо. Действительно, это несложно в исполнении, но и не очень эффективно на практике. Давайте оценим скорость работы этой программки. В ней присутствуют два цикла (один вложенный), время работы внешнего большей степенью зависит от n, а внутренний в худшем случае делает m операций. Таким образом, время работы всего алгоритма есть O((n-m+1)m). Для маленьких строк поиск проработает быстро, но если в каком-то многомегабайтном файле вы будете искать последовательность длинной 100 Кб, то, боюсь, придется вам ждать ну очень долго. Впрочем, как я уже говорил, многим хватает и этого.

Как вы уже, наверное, поняли, основной недостаток вышеизложенного метода состоит в том, что приходится выполнять много лишней работы. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату. Следующий метод работает намного быстрее простейшего, но, к сожалению, накладывает некоторые ограничения на текст и искомую строку.

Алгоритм Рабина-Карпа

Идея, предложенная Рабином и Карпом, подразумевает поставить в соответствие каждой строке некоторое уникальное число, и вместо того чтобы сравнивать сами строки, сравнивать числа, что намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка Dm, где D - количество различных символов), и работать с ними будет так же неудобно. Ниже вы узнаете, как найти выход из этого положения, а пока смотрите реализацию для текста, состоящего только из цифр, и строки длиной до 8 символов.

Program RabinKarpSearch;

Var T : array[1..40000] of 0..9;

S : array[1..8] of 0..9;

i,j : longint;

n,m : longint;

v,w : longint; {v - число, характеризующее искомую строку, w характеризует строку длинны m в тексте}

k : longint;

const D : longint = 10; {количество разных символов (10 различных цифр)}

Begin

{Ввод текста и образца}

…

v:=0;

w:=0;

for i:=1 to m do

begin

v:=v*D+S[i]; {вычисление v, строка представляется как число}

w:=w*D+T[i]; {вычисление начального значения w}

end;

k:=1;

for i:=1 to m-1 do {k нужно для многократного вычисления w и имеет значение Dm-1}

k:=k*D;

for i:=m+1 to n+1 do

begin

if w=v then {если числа равны, то строки совпадают, а значит, образец найден в тексте}

writeln('Образец входит в текст начиная с ',i-m,'-ого символа');

if i<=n then

w:=d*(w-k*T[i-m])+T[i]; {вычисление нового значения w}

end;

End.

Этот алгоритм выполняет линейный проход по строке (m шагов) и линейный проход по всему тексту (n шагов), стало быть, общее время работы есть O(n+m). Это время линейно зависит от размера строки и текста, стало быть программа работает быстро. Но какой интерес работать только с короткими строками и цифрами? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы. Как вы заметили, мы ставили в соответствие строке ее числовое представление, но возникала проблема больших чисел. Ее можно избежать, если производить все арифметические действия по модулю какого-то простого числа (постоянно брать остаток от деления на это число). Таким образом, находится не само число, характеризующие строку, а его остаток от деления на некое простое число. Теперь мы ставим число в соответствие не одной строке, а целому классу, но так как классов будет довольно много (столько, сколько различных остатков от деления на это простое число), то дополнительную проверку придется производить редко.

Var T : array[1..40000] of char;

S : array[1..10000] of char;

i,j : longint;

n,m : longint;

v,w : longint;

k : longint;

const P : longint = 7919; {1000-е простое число}

D : longint = 256; {количество разных символов (количество всех возможных значений символьного типа char)}

Begin

{Ввод текста и образца}

…

v:=0;

w:=0;

for i:=1 to m do {вычисление v и w}

begin

v:=(v*D+ord(S[i])) mod P; {ord преобразует символ в число}

w:=(w*D+ord(T[i])) mod P;

end;

k:=1;

for i:=1 to m-1 do

k:=k*D mod P; {k имеет значение Dm-1 mod P}

for i:=m+1 to n+1 do

begin

if w=v then {если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они}

begin

j:=0;

while (j<m) and (S[j+1]=T[i-m+j]) do

j:=j+1;

if j=m then {окончательная проверка}

writeln('Образец входит в текст начиная с ',i-m,'-ого символа');

end;

if i<=n then

w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;

end;

End.

Итак, нам все-таки приходится производить сравнение строк посимвольно, но так как «холостых» срабатываний будет немного (в 1/P случаях), то ожидаемое время работы малое. Строго говоря, время работы есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа. Этот алгоритм значительно быстрее предыдущего и вполне подходит для работы с очень длинными строками.

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

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

Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки S[1..j] (j<i), присутствующей одновременно и в начале, и в конце подстроки (как префикс и как суффикс). Например, для подстроки abcHelloabc такой подстрокой является abc (одновременно и префиксом, и суффиксом). Смысл префикс-функции в том, что мы можем отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcHelloabc (следующий символ не совпал), то нам имеет смысл продолжать проверку продолжить поиск уже с четвертого символа (первые три и так совпадут). Вот как можно вычислить эту функцию для всех значений параметра от 1 до m:

…

var S : array[1..10000] of char;

P : array[1..10000] of word; {массив, в котором хранятся значения префикс-функции}

i,k : longint;

m : longint;

…

Procedure Prefix; {процедура, вычисляющая префикс-функцию}

Begin

P[1]:=0; {префикс строки из одного символа имеет нулевую длину}

k:=0;

for i:=2 to m do {вычисляется для префиксов строки длинной от 2 до m символов}

begin

while (k>0) and (S[k+1]<>S[i]) do

k:=P[k]; {значение функции может быть получено из ранее сделанных вычислений}

if S[k+1]=S[i] then

k:=k+1;

P[i]:=k; {присвоение префикс-функции}

end;

End;

…

Теперь разберемся, почему же данная процедура вычисляет префикс-функцию правильно. Используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k]<k), но не становится меньше 0, то уменьшаться она может не чаще, чем возрастать. Переменная k возрастает на 1 не более m раз. Значит, переменная k меняется всего не более 2m раз. Выходит, что время работы всей процедуры есть O(m). А сейчас мы переходим к самой программе, ищущей строку в тексте.

Program KnutMorrisPrattSearch;

…

{Описание процедуры Prefix и связанных с нею переменных}

…

var n : longint;

T : array[1..40000] of char;

Begin

{Ввод текста и образца}

…

Prefix; {Вычисление префикс-функции}

k:=0; {количество символов, совпавших на данный момент}

for i:=1 to n do

begin

while (k>0) and (S[k+1]<>T[i]) do

k:=P[k];

if S[k+1]=T[i] then

k:=k+1;

if k=m then {если совпали все символы}

begin

writeln('Образец входит в текст начиная с ',i-m+1,'-ого символа');

k:=P[k];

end;

End.

Доказать что эта программа работает за линейное время, можно точно так же, как и для процедуры Prefix. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.

Напоследок хочу заметить, что простейший алгоритм и алгоритм Кнута-Морриса-Пратта помимо нахождения самих строк считают, сколько символов совпало в процессе работы. И еще: алгоритм Кнута-Морриса-Пратта немногим более громоздок, чем простейший, зато работает намного быстрее. Так что делайте выводы.

P.S.Все программы проверены на работоспособность, достаточно вставить соответствующие сегменты кода вместо многоточий.