Меню сайта
Категории каталога
Алгоритмы [5]
Мини-чат
Главная » Статьи » Программирование » Алгоритмы

Часть 5. Алгоритмы Морриса-Пратта и Кнута-Морриса-Пратта

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


В результате тщательного анализа алгоритма грубой силы появился этот алгоритм. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования (алгоритм грубой силы ее "выбрасывает"). Оказывается, размер сдвига образца можно увеличить, одновремеменно запомнив части текста, совпадающие с образцом. Это позволит нам избежать ненужных сравнений и, тем самым, резко увеличить скорость поиска.

Поставим следующую задачу: имеется образец (подстрока) x и строка y, и нужно определить индекс, начиная с которого строка x содержится в строке y. Если  x не содержится в  y — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). Размер сдвига образца можно увеличить, одновременно запомнив части текста, совпадающие с образцом. Это позволит избежать ненужных сравнений и, тем самым, резко увеличить скорость поиска.


Рассмотрим сравнение строк на позиции 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 сойдется с каким-нибудь суффиксом подслова текста u. Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки u.


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


Пример практической реализации

Пусть ищется строка S_1 в строке S_2. Построим строку S=S_1\$S_2, где символ $ — символ, не встречающийся ни в S_1, ни в S_2. Далее вычислим значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса строки S длины i равна n, где n — длина S_1, и i>n, то в строкеS_2 есть вхождение S_1, начиная с позиции i-2n.


Реализация алгоритма на языке Си

int  seek_substring_KMP  (char s[], char q[])
{
 
int  i, j, N, M;
 N = strlen(s);
 M = strlen(q);
 
int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М+1*/

 /* Вычисление префикс-функции */
 i=0;
 j=-l;
 d[
0]=-l;
 
while(i<M-l)
 {
 
while((j>=0) && (q[j]!=q[i])) j = d[j];
  i++;
  j++;
 
if(q[i]==q[j]) d[i]=d[j];
 
else
  d[i]= j;
 }

 
/* поиск */
 for(i=0,j=0;(i<=N-l)&&(j<=M-l); i++,j++)
 
while((j>=0)&&(q[j]!=s[i]))  j=d[j];
 free (d); 
/* освобождение памяти массива d */
 if (j==M)
 
return i-j;
 
else /* i==N */
 return -1;
}


Еще раз другими словами о КМП (Pascal)

Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки 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;
End.



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

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

Категория: Алгоритмы | Добавил: chas (19.09.2008) | Автор: Александр Чигиринский
Просмотров: 13692 | Рейтинг: 5.0/3 |
Всего комментариев: 0

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа
Поиск
Основной сайт
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Copyright CHAS © 2017
Бесплатный хостинг uCoz