Главная » Java, Структуры данных и алгоритмы » Алгоритмы шаблонного сопоставления Алгоритм Кнута-Морриса-Пратта

0

При рассмотрении наихудших вариантов производительности силового и БМ-алгоритмов для специфических условий (например, аналогичных приведенным в примере 11.3) очевидна их значительная сложность. В частности, можно произвести множество сравнительных операций при определении потенциального места расположения шаблона в тексте, при этом, если совпадающие символы не обнаруживаются, вся полученная в процессе сравнения информация отбрасывается и все начинается заново с нового отрезка текста. Алгоритм Кнута-Морриса-Пратта (КМП) не отбрасывает такую информацию, что позволяет добиться времени выполнения, которое пропорционально 0(п + т) и является оптимальным для самых сложных ситуаций. Это означает, что в наихудшем случае алгоритм исследует все символы текста и все символы шаблона всего лишь один раз.

Функция отказа

Основная идея КМП-алгоритма заключается в определении функции отказа (failure function), которая находит подходящий отрезок сдвига Р, чтобы, насколько это возможно, повторно использовать ранее сделанные

сравнения. В частности, функция отказа/(j) определяется как длина наиболее протяженного префикса шаблона Р, который является суффиксом P[\…j] (заметьте, индекс начинается с 1, а не с 0). Будем считать, что ДО) = 0. Далее покажем, как эффективно вычислять функцию отказа. Главным в функции отказа является «кодирование» повторяющихся подстрок внутри самого шаблона.

Пример 11.4. Рассмотрим шаблонную строку Р = "abacab" из примера 11.3. Функция отказа КМП-алгоритма /(у) для строки Р выглядит следующим образом:

У

0

1

2

3

4

5

Р[Л

а

ь

а

с

а

Ь

/[у]

. 0

0

1

0

1

2

Шаблонный алгоритм Кнута-Морриса-Пратта, приведенный во’фрагменте кода 11.4, последовательно обрабатывает текстовую строку Г, сравнивая ее с шаблонной строкой Р. При каждом совпадении увеличиваем текущие сравниваемые индексы строки и шаблона. При несовпадении (в Р индекс уже увеличился) обращаемся к функции отказа для определения нового индекса в Р, с которого продолжим сравнение Р и Т. В противном случае (совпадений нет, и находимся в начале Р) просто увеличивается индекс в Г (а переменная индекса сравнения для Р остается нулевой). Этот процесс повторяется до тех пор, пока в Т не найдется совпадение с Рили индекс Г не достигнет п, то есть длины Г (показывая, что шаблон Р в строке Г не найден).

Алгоритм KMPMatch^/5):

Input текстовая строка 7" из п символов и шаблон Р из m символов.

Output, индекс начала первой подстроки в Г, совпадающей с Р, или признак того, что Р не является подстрокой Т.

f <- KMPFailureFunction(P) { создает функцию сбоя f для Р } < / <- 0 /<- О

while i < п do

?f P[J] = T[i] then if у- — /г? — 1 then

return / – m + 1 { возможно совпадение! } / <- /+1 j <- y+1

else if j > 0 { совпадение отсутствует, но продвинулись вперед в Р } then

j f (j – 1) { j устанавливается сразу после префикса Р, который совпадает }

else

/ i+1

return "There is no substring qf T matching P." Фрагмент кода 11.4. КМП-алгоритм

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

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

Рис. 11.5. Шаблонный КМП-алгоритм. Функция отказа / для этого алгоритма приводится в примере 11.4. Алгоритм выполняет 19 сравнений символов, отмеченных номерами

Производительность

Исключая вычисление функции отказа, время выполнения КМП-алго- ритма будет прямо пропорционально количеству циклических итераций. Для проведения анализа положим к = / — j. Интуитивно к — общая протяженность сдвига, на который шаблон Р перемещается относительно текста Т. Заметим, что в процессе выполнения алгоритма всегда к < п. При каждой итерации цикла имеют место три следующие ситуации.

•                    Если T[i] = P\j], то / увеличивается на 1, а А; не меняется, поскольку j тоже увеличивается на 1.

•                    Если Т [/] ф P\j\ и у > 0, то / не меняется, а к увеличивается как минимум на 1, так как в этом случае к изменяется от / — j до i—f(j~ 1), то есть изменение равно j — f(J — 1), и оно положительно, поскольку

УС/— 1) <у-

•                    Если T[i] ф P[j] и j = 0, то / увеличивается на 1 и к увеличивается на 1, поскольку j не изменяется.

Таким образом, при каждой итерации либо /, либо к увеличивается как минимум на 1 (а иногда и оба сразу). Следовательно, общее количество итераций цикла в КМП-алгоритме составит максимум 2п, с учетом того,.что функция отказа для Р уже рассчитана.

Построение функции отказа

Для построения функции отказа воспользуемся методом из фрагмента кода 11.5, представляющим вспомогательный процесс, сходный с алгоритмом KMPMatch. Шаблон сравнивается сам с собой, как в КМП-алгоритме. При каждом нахождении двух совпадающих символов устанавливаем /(/) =j + 1. Поскольку / > j на протяжении всего выполнения алгоритма,/^ — 1) определейо всегда.

Алгоритм KMPFailureFunctionC/3):

Input: строка шаблона Р из m символов.

Output: функция отказа/для Р, которая относит j к длине наиболее протяженного префикса в Р, являющегося суффиксом для P[l…j].

/ <- 1 у <- 0 /(0) 0 while / < m do

if P[j] = P[i] then

{ совпадение j + 1 символов } Ц1) <-/+1

i <- i + 1 У <- У + 1 else if j > 0 then

{ j устанавливается сразу после префикса Р, который совпадает }

У <- f(i- 1) else

{ совпадения отсутствуют } Ц <- О /'<-/’+ 1

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

Алгоритм KMPFailureFunction выполняется за О(т) времени. Его анализ аналогичен анализу алгоритма KMPMatch, то есть имеем следующее утверждение.

Утверждение 11.1. Алгоритм Кнута-Морриса-Пратта выполняет поиск по шаблону в текстовой строке длиной п и с шаблонной строкой длиной т за время 0(п + т).

Реализация КМП-алгоритма на Java приведена во фрагменте кода 11.6.

public static int KMPmatch(String text, String pattern) { int n = text.length(); int m = pattern.Iength(); int[ ] fail = computeFailFunction(pattern); int i = 0; int j = 0; while (i < n) {

if (pattern.charAt(j) == text.charAt(i)) { if (j == m – 1)

return i – m + 1; // совпадает

i++; j++;

}

else if (j > 0)

У = failO – 1]; else i++;

}

return -1; // не совпадает

}

public static int[] computeFailFunction(String pattern) { int[ ] fail = new int[pattern.length()]; г fail[0] = 0;

int m = pattern.Iength(); int j = 0; int i = 1; while (i < m) {

if (pattern.charAt© == pattern.charAt(i)) { // j + 1 символов совпадает fail[/] = j + 1;

i++; j++;

}

else if (j > 0) // j следует за совпавшим префиксом

j = failU – 1];

else { // совпадения отсутствуют fail[i] = 0; i++;

}

}

return fail;

}

Фрагмент кода 11.6. Java-реализация КМП-алгоритма, представленного двумя статическими методами: метод KMPMatch выполняет сопоставления и вызывает вспомогательный метод computeFailureFunction для вычисления функции отказа, выраженной массивом. Отсутствие совпадения обозначается возвратом значения -1

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии