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

 

Этот алгоритм был разработан Дональдом Кнутом, Воганом Праттом и, независимо от них, Джеймсом Моррисом в 1977 году [46]. Он был получен благодаря глубокому анализу алгоритма Морриса-Пратта, заключающемуся в поиске возможностей увеличения размера сдвига при несовпадении сравниваемых символов. В нем, как и у наивного алгоритма осуществляется сравнение сначала, где needle смещается по haystack слева направо, и сравнение этих строк друг с другом также производится слева направо. Но в отличие от наивного алгоритма обладает неоспоримым преимуществом, так как индекс i, нумерующий символы текста y, не уменьшается. Это достигается тем, что в случае провала сопоставления образец сдвигается относительно текста на величину, зависящую от его структуры и от номера символа, на котором это произошло. Величина сдвига задается таблицей protr, имеющей ту же длину что и x.

Рассмотрим сравнение на позиции i, где образец x [ 0, m-1 ] сопоставляется с частью текста y [ i, i+m-1 ]. Предположим, что первое несовпадение произошло между y [ i+j ] и x [ j ], где 1 < j < m. Тогда y [ i, i+j-1 ] = x [ 0, j-1 ] = u и a = y [ i+j ] ≠ x [ j ] = b.

При сдвиге вполне можно ожидать, что префикс u образца x сойдется с каким-нибудь суффиксом v подслова текста y. Более того, если мы хотим избежать выявления другого несовпадения (то есть не тратить на это операцию сравнения), буква, находящаяся за префиксом v в образце должна отличаться от b. Наиболее длинный такой префикс v называется границей u (он встречается по обоим сторонам u).

Это приводит к следующему алгоритму, пусть protr[ j-1 ] - длина длиннейшей границы x [ 0, j-1 ], за которой следует символ c, отличающийся от x [ j ]. Тогда после сдвига мы можем возобновить сравнения между символами с места y [ i+j ] и x [protr[ j-1 ] ] (что равносильно сдвигу образца на j-protr[ j-1 ] символов вправо относительно текста) без возможной потери местонахождения образца. Таблица protr может быть перед началом поиска.

Значения элементов этой таблицы можно получить, основываясь на следующих соображениях. Если отвергающими оказались символы x[ j ] и y [ i+j ], то мы знаем, что x [ 0, j-1] совпадает с y[ i, i+j-1 ]. Предположим теперь, что у подстроки x[ 0, m-1] имеются равные друг другу префикс v и суффикс u, длины, скажем, k. Легко видеть, что в этом случае перед продолжением поиска образец x можно сдвинуть так, чтобы префикс занял место, прежде занимаемое суффиксом. Таким образом, на следующем шаге с текущим символом текста будет сравниваться символ x[ k ] образца, расположенный сразу же за префиксом. Поскольку мы заинтересованы в возможно больших сдвигах, нужно выбирать префикс максимально возможной длины. На случай несовпадения в первом символе образца, protr[ 0 ] содержит значение 0, указывающее, что весь образец следует продвинуть «за» символ y[ i ].

Итак, protr[ j-1 ]равняется максимальному из целых k, которые обладают следующими двумя свойствами: k < m, и префикс и суффикс образца длины k равны другу, т.е. x[ 0, k-1 ] = x[m-k+1, m-1]. Если таких префикса и суффикса нет, то k берется равным 0. Значение k можно получить следующим образом. Будем сравнивать строку x[ 0, m-1 ] саму с собой, продвигая одну ее копию над другой слева направо. Начнем с положения, когда первое сравнение проводится между x[ 0 ] и x[ 1 ], и остановимся, либо когда перекрывающиеся отрезки равны друг другу, либо когда не останется символов для сравнения.

Как было описано ранее, в процедуре поиска, сразу же после приращения, j равно максимальному целому числу, которое не превосходит i, и для которого выполнено x[ 0, j-1 ] = y[ i, i+j-1 ]. Если в этом выражении y заменить на x, оно полностью совпадет с описанным выше определением значений таблицы protr. Таким образом, метод генерации таблицы protr похож на саму процедуру поиска, с тем отличием, что в нем образец сопоставляется сам с собой (рис. 2.6.).

 

j

x[ j ]

A

T

G

C

A

A

T

G

C

A

T

G

C

A

protr[ j ]

 

Рисунок 2.6. Пример построения таблицы смещений для алгоритма Кнута-Морриса-Пратта

 

Данный алгоритм поиска, обладает интересным свойством. Так общее количество выполняемых присваиваний j = protr[ j-1 ] не превосходит количества присваиваний в операции приращения i. Таким образом образец сдвигается вправо не больше n раз, что дает время сопоставления O(n). Аналогично, можно показать, что следующий этап инициализации таблицы protr выполняется за время O(m). Поэтому данный алгоритм отличается отсутствием регрессии в худшем случае и не зависит от размера алфавита символов, что очень важно для «плохих» данных, то есть среднее время поиска у него равно худшему времени поиска и равно O(n + m).

Кроме того, было показано, что максимальное количество сравнений для одного символа текста равно log_Ф(m), где Ф - золотое сечение, равное (√5 + 1) / 2. Исходный код реализации этого алгоритма имеет следующий вид:

 

char* kmpstr(char *y, char *x, int m){

char* yy;

int i, j, n;

yy=y;

int *protr =(int*)malloc(m*sizeof(int));

protr[0]=0;

/*Построение таблицы смещений*/

for(i=1, j=0; i<m; i++){

while(j>0 && x[j]!=x[i])

j = protr[j-1];

if(x[j]==x[i])

j++;

protr[i]=j;

}

/*Поиск*/

i=0;

j=0;

while (y[i]!= '\0'){

while(j>0 && x[j]!=y[i])

j=protr[j-1];

if(x[j]==y[i])

j++;

if (j==m){

free (protr);

yy=y+i-j+1;

return yy;

}

i++;

}

free (protr);

return NULL;

}