Главная | Обратная связь | Поможем написать вашу работу!

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

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

Рассмотрим задачу поиска всех вхождений образца в некоторый текст , . Предположим, что в текущий момент времени с образцом сравнивается подстрока и при этом совпали первые () символов. При условии, что , мы можем говорить о неудачном завершении поиска для подстроки . На следующем шаге алгоритм должен сдвинуться по тексту, начав проверку на совпадение образца со следующей подстрокой. Переборный алгоритм продолжил бы работу со сравнения символов и , осуществив сдвиг по отношению к предыдущей подстроке на один символ. Однако оказывается, что величину сдвига можно вычислять, используя информацию, собранную при сравнении подстроки . В самом деле, при выполнении поиска мы просмотрели множество собственных суффиксов подстроки . При условии совпадения некоторого суффикса длины из указанного множества с префиксом той же длины строки-образца нет необходимости повторять сравнение части образца с подстрокой , а можно продолжить поиск сравнением символов и . Обозначим через подмножество множества , содержащее подстроки, совпадающие с некоторым префиксом строки-образца. Из сказанного выше следует, что длины строк, входящих в и определяют соответствующие сдвиги при поиске следующей подстроки в тексте, причем величина сдвига равна разности , где длина слова . Тогда минимальный сдвиг по тексту для поиска следующего кандидата на совпадения в строке определяется как . С другой стороны, поскольку каждый элемент из является некоторой подстрокой образца вся информация, необходимая для построения множества содержится в образце. Другими словами для каждого начального отрезка длины строки образца необходимо уметь находить подстроку-префикс максимальной длины , которая совпадает с суффиксом . Дадим более строгое определение: равно максимальному значению , , для которого . Если такого нет, то =0. Функция носит название префикс-функции. Префикс-функция несет информацию о том, в каких местах строки-образца повторно встречается префикс соответствующей длины.

Пусть является строкой образцом. Тогда, несложно видеть, что

Рассмотрим задачу поиска образца в тексте . Пусть алгоритм на некотором шаге проводит сравнение с подстрокой

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

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

В этом случае указатель по тексту не сдвинулся, а очередной сдвиг образца равен .

Изложим теперь алгоритм поиска в виде псевдокода, на вход которого подаются текст Т и образец Р в виде массивов в предположении, что мы умеем вычислять префикс-функцию

Procedure KMP_Matcher [4].

3. //вычисляется вектор значений префикс-функции по образцу Р

10. ’образец входит в текст с позиции’

11.

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

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

Нетрудно видеть, что эта задача является частным случаем задачи поиска в тексте образца. Только в этом случае в качестве текста берется образец для исходной задачи, а в качестве образцов рассматриваются различные префиксы этого образца. Приведем алгоритм вычисления префикс-функции по образцу [4]:

Procedure Compute_Prefix_function

10.

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

Алгоритм поиска по образцу можно представить в виде некоторого недетерминированного автомата с одним начальным и одним допускающим состоянием, для которого разрешены переходы.

Обратные переходы определяются значениями префикс-функции и представляют переходы, связанные с пустым символом . Начальным состоянием построенного автомата является состояние 0, заключительным состоянием состояние 8. Рассмотрим работу НКА на слове . Первые два такта автомат проводит в состоянии , а затем под воздействием входной подстроки переходит в состояние . Поскольку из состояния 6 имеются переходы, можно считать, что в этот момент автомат одновременно находится также в состояниях . Далее необходимо проанализировать переходы автомата по очередному символу . Поскольку из состояния 6 такой переход невозможен, анализируются переходы из состояний 4, 2 и 0. В частности, если рассматривать переход из состояния 4, то по символу можно попасть в состояния 5, 3, 1 и 0. Далее на вход автомата вновь поступает символ . Поскольку для результативного поиска нам необходимо рассмотреть хотя бы одну траекторию, завершающуюся в заключительном состоянии, то рассмотрим переход из состояния 0. Несложно видеть, что завершая ввод текста, мы переходим в распознающее состояние 8. Таким образом, процедура KMP_Matcher является детерминированной реализацией НКА, распознающего язык , где представляет строку-образец. Множество всех переходов НКА для данного входного текста может быть представлено в виде дерева переходов состояний. Процедура KMP_Matcher предлагает способ перебора траекторий в этом дереве, позволяющего получить результат за линейное время.

Мы не будем делать детальный разбор правильности приведенных псевдокодов. Любознательного читателя можно отослать к литературе [2,4], но заметим, что сложность нахождения префикс-функции составляет , а сложность поиска по образцу в тексте длины равна , что лучше, чем в алгоритме Рабина-Карпа.

Можно также непосредственно построить ДКА, распознающий язык [2]. При построении этого автомата также существенно используется префикс-функция. Алгоритм построения такого автомата по образцу описывается следующим образом:

Положим . Функция переходов состояний может быть построена следующей процедурой:

1. По образцу строится префикс функция .

Сложность такого алгоритма равна , где число элементов множества , а общая сложность алгоритма поиска - . Поэтому конечный автомат строят в случае, когда длина текста значительно превосходит мощность алфавита образца. Для нашего примера диаграмма переходов состояний автомата выглядит следующим образом:

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒