Поиск подстроки (образца) в строке (string-matching). Алгоритмы: Рабина-Карпа Кнута-Морриса-Пратта, Бойера-Мура

Поиск подстроки (образца) в строке (string-matching)

Алгоритмы: Рабина-Карпа Кнута-Морриса-Пратта, Бойера-Мура,

Алгоритм прямого перебора

Пусть S строка (набор символов из некоторого алфавита, называемый текстом), где нужно произвести поиск строки P (набор символов, называемый шаблоном или образцом). n - длина строки S, а m - длина строки P (m<=n). Сравниваем сначала первые m символов строки S с соответствующими символами строки P. Если все символы в парах окажутся равными, то на этом поиск заканчивается. В противном случае, начало поиска сдвигается на одну позицию вправо и осуществляется сравнение следующих m и так до тех пор пока, либо все символы не совпадут, либо после n-m сдвигов не будет достигнут конец строки S. Результатом является указатель на первый символ в строке S, с которого начинается искомая строка в случае удачи, либо NULL, если строка P не найдена. Этот алгоритм достаточно эффективен в том случае, когда несовпадение пар символов происходит после всего лишь нескольких сравнений.

Алгоритм прямого перебора

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

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

Фиксируем некоторую функцию, определенную на словах длины m. Если значения этой функции на слове длины m в строке S и на строке P различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. При сдвиге слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. По этим данным можно просто рассчитать, как меняется функция. Пример. Заменим все буквы в слове и образце их номерами (кодами), представляющими собой целые числа. Тогда удобной функцией является сумма цифр. При сдвиге нужно добавить новое число и вычесть пропавшее.

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

Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Идея: надо запасти много функций и в начале работы алгоритма выбирать из них случайную. Пример. Выберем некоторое число p (желательно простое). Каждое слово длины m будем рассматривать как коэффициенты многочлена степени m-1 и вычислим значение этого много члена по модулю p в точке x. Сдвиг на 1 соответствует вычитанию старшего члена, умножению на x и добавлению свободного члена.

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

Оценим время работы алгоритма. Значение функции на шаблоне вычисляется за время Θ(m), а n-m+1 значений функций – за время Θ(n-m+1). Фаза сравнения значений функций требует Θ(n-m+1) времени. Таким образом, на предварительную обработку затрачивается время Θ(m), а время сравнения в наихудшем случае равно Θ((n-m+1)m), т.е. не лучше, чем во время работы простейшего алгоритма. Однако, на практике в среднем он работает намного лучше.

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

Алгоритм Кнута-Морриса-Пратта (1970 г.) базируется на том, что после частичного совпадения начальной части строки P с соответствующими символами строки S и при несовпадении очередной пары символов сдвиг производится на пройденное расстояние, если в нем нет начального символа строки P, либо до позиции с начальным символом. Алгоритм КМП дает выигрыш только тогда, когда после очередного сдвига неудаче предшествует некоторое совпадение символов.

Пример.

//Поиск с строке по алгоритму Кнута-Морриса-Пратта  #include <stdio.h> #include <string.h> #include <conio.h> int KMP(char *S, char *P); void main() { char S[]="Иван Иванович Иваникин"; char P[]="Иваникин"; int r; clrscr(); r = KMP(S,P);

Пример.

if(r<0) printf("\n Подстрока  \"%s\" не найдена",P); else printf("\n Подстрока  \"%s\" найдена, позиция i=%d",P,r); getch(); } //Поиск подстроки по алгоритму Кнута-Морриса-Пратта int KMP(char *S, char *P) //S - исходная строка, //P - строка-образец { int i,j,k,M,N; int d[100]; M=strlen(P); N=strlen(S); d[0]=-1;j=0;k=-1;

Пример.

while(j<(M-1)) { while((k>=0)&&(P[j]!=P[k])) k=d[k]; j++; k++; if(P[j]==P[k]) d[j]=d[k]; else d[j]=k; } i=0;j=0;k=0; while((j<M)&&(i<N)) { while((j>=0)&&(S[i]!=P[j])) j=d[j]; i++; j++;} if(j==M) return i-M; //Найдена позиция i-M else return 0; }

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура (1975 г.) отличается от алгоритма КМП тем, что сравнение символов начинается с конца строки P и идет к его началу. Длина сдвига в случае неудачи может лежать в пределах от 1 до длины строки P. Для всех символов, входящих в строку P, кроме последнего, длина сдвига устанавливается так: для последнего символа она равна 1, для следующего от конца - 2, затем - 3 и т.д., для первого - (М-1), где М - длина строки P. Для всех остальных символов алфавита, используются для представления строк S и P, в том числе и для последнего символа, если он не повторяется в строке P, длина сдвига устанавливается равной длине строки P.

Алгоритм Бойера-Мура

При несовпадении любой пары символов, осуществляется сдвиг на величину, установленную для первого с конца символа сравниваемой части строки. Чем длиннее строка P и чем меньше совпадающих символов после очередного сдвига, тем быстрее осуществляется поиск. Недостатком алгоритма Бойера-Мура является то, что для всех символов алфавита необходимо определить длины сдвига и содержать их в массиве чисел. При коротких строках S и P время создания такого массива может значительно превысить время прямого поиска в строке, что подтверждается проведенными измерениями.

Пример.

//Поиск в строке по алгоритму Бойера-Мура #include <stdio.h> #include <string.h> #include <conio.h> int BM(char *S, char *P); void main() { char S[]="Иван Иванович Иваникин"; char P[]="Иваникин"; int r; clrscr(); r = BM(S,P);

Пример.

if(r<0) printf("\n Подстрока  \"%s\" не найдена",P); else printf("\n Подстрока  \"%s\" найдена, позиция i=%d",P,r); getch(); } //Поиск подстроки по алгоритму Бойера-Мура   int BM(char *S, char *P) // S-исходная строка, P-строка-образец { int i,j,k,M,N,t; int d[256]; i=0; M=strlen(P); N=strlen(S);  for(j=0;j<256;j++) d[j]=M; for(j=0;j<256;j++) d[(unsigned char)P[j]]=M-j-1;

Пример.

//Поиск подстроки в строке j=M; while((j>0)&&(i<=N)) { j=M; k=i; while((j>0)&&(S[k-1]==P[j-1])) {k--; j--;} t=d[(unsigned char)S[i-1]]; i=i+t; } if(j<=0) return i-M-t; //строка найдена с позиции i-M-t else return 0; //строка не найдена }