Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции)

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

Основная идея алгоритма следующая. Пусть S_k – подстрока строки S длины k. Пусть нам известно значение функции перехода h(S_k,W) (см. предыдущий параграф). Требуется вычислить значение функции h(S_k+1,W), т.е. найти максимальный префикс W, являющийся суффиксом S_k+1.

Если S[k]==W[h(S_k,W)], то h(S_k+1,W)= h(S_k,W)+1 (как уже отмечалось ранее – больше быть не может, а то, что в этой ситуации h(S_k+1,W)³ h(S_k,W)+1 – получается по определению). Пример:

char S[]=”ababab”,W[]=”abaa”; int k=4;

h(S,4,W)==2

S: abab ab

W: __ab

h(S,5,W)==3

S: ababa b

W: __aba

Пусть S[k]!=W[h(S_k,W)], то h(S_k+1,W)< h(S_k,W)+1. В приведенном примере:

char S[]=”ababab”,W[]=”abaa”; int k=5;

h(S,5,W)==3

S: ababab

W: __aba

h(S,6,W)==2

S: ababab

W: ____ab

Для вычисления h(S_k+1,W) при отсутствии функции перехода можно не перебирать все префиксы W. Действительно, h(S_k+1,W) == длине l максимального префикса W, для которого S[k]==W[l], плюс 1. Тогда, для вычисления h(S_k+1,W) следует перебрать все префиксы W, являющиеся суффиксами S_k, в порядке убывания их длины и найти первый из них, для которого S[k]==W[l], где l – длина префикса. Тогда h(S_k+1,W) ==l+1.

Итак, если бы мы могли быстро вычислять длины всех префиксов W, являющиеся суффиксами S_k, в порядке их убывания, то задача поиска подстроки выполнялась бы за время T₁=Q(N). Действительно, исходя из рассуждений, приведенных в предыдущих абзацах, T₁ пропорционально количеству изменений переменной l в процессе работы алгоритма. Но переменная l может увеличиваться на 1 не более N раз, поэтому и уменьшаться она может не более N раз. Что и требовалось доказать.

Осталось понять, как вычислять длины префиксов W, являющихся суффиксами S_k.

Легко заметить, что если мы знаем, что имеется префикс W, являющийся суффиксом S_k, длины l, то для вычисления максимального префикса W меньшей длины, являющегося суффиксом S_k, не надо ничего знать о S. Достаточно информации только о строке W. Действительно, т.к. W_l - суффикс S_k, то следует найти максимальный префикс W, длины меньше l, являющийся суффиксом W_l.

Введем функцию p: {1,…,N}®{1,…,N-1}, такую что p(l)=длина максимального префикса W_l, являющегося суффиксом W_l, длиной меньше l.

Теперь заметим, что W_p(l) является, одновременно, суффиксом W_l, поэтому следующий по длине (в порядке убывания) суффикс W_l, являющийся префиксом W_l, является суффиксом W_p(l). Осталось найти длину максимального суффикса W_p(l), с длиной меньше p(l), являющегося префиксом W_p(l). Данная величина, по определению, равна p(p(l))=_{по определению}=p²(l).

Т.о., по индукции, получаем, что последовательность длин суффиксов W_l, совпадающих с префиксами W_l и расположенных по убыванию длин, совпадает с последовательностью {l,p(l),p(p(l))…}={ p⁰(l), p¹(l), p²(l), …}. Т.о., если бы мы имели таблицу значений функции p(*), то задача вычисления длин префиксов W, являющихся суффиксами S_k, оказалась бы решенной, что, в свою очередь, решило бы задачу поиска подстроки в строке.

Займемся вычислением табличной функции p(*).

Префикс-функция p(*) вычисляется в точности по уже приведенному алгоритму.

Пусть требуется вычислить p[k+1], если p[i] для i£k уже известны.

Если W [k]==W[p[k]], то p[k+1]= p[k]+1.

Если W [k]!=W[p[k]], то, как и ранее, перебираем в порядке уменьшения длин l все префиксы W, совпадающие с суффиксами W_k, пока не выполнится

W[k]==W[l]

Каждое последующее l получается из предыдущего по формуле

l=p(l);

Положим в начале цикла l= p[k], то случай W [k]==W[p[k]] подпадет под вычисления внутри последнего цикла и его отдельное рассмотрение будет излишним.

Внутренний цикл следует продолжать пока k³0. Если окажется, что k<0, то p[k+1]=0. Иначе, в конце внутреннего цикла имеем: p[k+1]= l+1.

Отметим, что мы можем положить

p[0]=-1;

после чего случай k<0 перестанет быть выделенным (в этом случае l=-1;p[k+1]=l+1; из чего сразу получаем p[k+1]=0).

Итак, на языке С подготовка функции (массива) p может выглядеть следующим образом

void MakeP(int *p, char *W, int M)

{int k,l; p[0]=-1; p[1]=0; l=0;

for(k=1;k<M;k++)

{

l=p[k];

while(l>=0 && W[k]!=W[l])l=p[l];

p[k+1]=l+1;

}

}

Основная функция, ищущая первое вхождение строки W в строку S, может выглядеть следующим образом

char *Search(char *S,int N, char *W, int M, int *p)

{int l=0,k;

for(k=0;k<N;k++)

{

while(l>=0 && S[k]!=W[l])l=p[l];

l++;

if(l==M)return S+k-l+1;

}

Return NULL;

}

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

Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов)

Алгоритм напоминает элементарный алгоритм поиска подстроки в строке. Основное отличие – сравнение искомой строки W с соответствующей частью строки S осуществляется не слева направо, а справа налево. По результатам сравнения делается вывод – на сколько можно сместиться вправо для сравнения W со следующей подстрокой S (в элементарном алгоритме поиска сдвиг всегда происходит на одну позицию). При этом, есть два независимых алгоритма, позволяющих вычислять, на сколько можно смещаться вправо для сравнения со следующей подстрокой S. Выбирается максимальный из сдвигов, получаемых по этим алгоритмам. Рассмотрим эти два алгоритма.

Дата добавления: 2015-10-30