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

2018-06-27T22:29:31Z

188.170.74.10: /* Псевдокод */

[[Детерминированные_конечные_автоматы|Автомат]] Кнута-Морриса-Пратта используется в алгоритмах, связанных с поиском образца в тексте, в том числе в реальном времени.

== Суффикс-функция ==

{{Определение
|id = suffix_func
|definition = Для строки <tex>p</tex> длиной <tex>m</tex> функция <tex> \sigma_p \colon \Sigma^* \to \left\{1,2, \dots ,m\right\}</tex> называется '''суффикс-функцией''', если она сопоставляет любой строке <tex>x</tex>, состоящей из символов алфавита <tex>\Sigma</tex>, длину максимального суффикса <tex>x</tex>, являющегося префиксом <tex>p</tex>.
}}
==== Пример суффикс-функции ====

Пусть строка <tex>p</tex>="<tex>abaab</tex>". Вот несколько примеров значений суффикс-функции для нее.

;*<tex>\sigma_p("aba")=3</tex>.
:В данном случае вся строка является префиксом <tex>p</tex>.
;*<tex>\sigma_p("bb")=0</tex>.
:В данном случае какой бы суффикс мы ни взяли, ни один из них не является префиксом <tex>p</tex>.
;*<tex>\sigma_p("aaab")=2</tex>.
:В данном случае "<tex>ab</tex>" является префиксом <tex>p</tex>, а все суффиксы длиннее {{---}} нет.

== Структура автомата ==

[[Детерминированные_конечные_автоматы|Автомат]] строится на строке-образце <tex>p</tex> длины <tex>m</tex>, которую в будущем мы будем искать в тексте.

Для [[Детерминированные_конечные_автоматы|автомата]] Кнута-Морриса-Пратта:
* <tex>Q = \left\{0,1,...,m\right\}</tex>
* <tex> s = 0 </tex>
* <tex> T = \left\{m\right\} </tex>
* <tex> \delta(q, a) = \sigma_p(p[1 \dots q] + a) </tex>, где <tex>q</tex> {{---}} это состояние, <tex>a</tex> {{---}} символ, по которому осуществляется переход, a "<tex>+</tex>" {{---}} операция конкатенации (<tex>p[1, 0] = \varepsilon </tex>).

Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через [[Детерминированные_конечные_автоматы|автомат]], то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние <tex>m</tex> символов полностью совпадают с образцом и мы нашли включение.

Заметим, что тот факт, что переход по символу осуществляется независимо от последующих, позволяет нам работать как с текстом, данным заранее, так и с текстом, который вводится в реальном времени.

==== Пример автомата Кнута-Морриса-Пратта ====
[[Файл:Kmp_aut_ex.png‎]]

Данный автомат построен для образца "<tex>abaab</tex>" и алфавита <tex>\Sigma =\left\{a, b\right\} </tex>

== Построение автомата ==

=== Идея алгоритма ===

Для каждого состояния и каждого символа будем определять значение функции перехода из данного состояния по данному символу. Пусть текущее состояние <tex>q</tex>. При считывании каждого нового символа <tex>a</tex> из текста возможно два варианта развития событий:

<center>''Символ <tex>a</tex> совпадает с <tex>q + 1</tex> символом строки <tex>p</tex>.''</center>

* Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае <tex>\delta(q, a) = q + 1</tex>.

<center>''Символ <tex>a</tex> не совпадает с <tex>q + 1</tex> символом строки <tex>p</tex>.''</center>

* Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_p(q), a)</tex>, где <tex>\pi_p(q)</tex> {{---}} [[Префикс-функция|префикс-функция]] для строки <tex>p</tex>. Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.

=== Асимптотика ===

В данном алгоритме нам нужно лишь вычислить значение функции перехода в каждом состоянии для каждого символа. При предподсчитанной за <tex>O(m)</tex> префикс-функции вычисление для одного состояния и одного символа происходит за <tex>O(1)</tex>. Всего состояний <tex>m</tex>, а символов <tex>|\Sigma|</tex>. Итого <tex>O(m + m \cdot |\Sigma|)</tex>.

=== Псевдокод ===

'''function''' make_kmp()
'''for''' q = 0 '''to''' m
'''for''' a <tex>\in \Sigma</tex>
'''if''' q > 0 '''and''' a <tex>\ne</tex> p[q + 1]
<tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi_p</tex>(q), a)
'''if''' a = p[q + 1]
<tex>\delta</tex>(q, a) = q + 1
'''else'''
<tex>\delta</tex>(q, a) = q

== Сравнение с другими алгоритмами поиска образца в тексте ==

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

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

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

== См. также ==
*[[Алгоритм Ахо-Корасик]]
*[[Алгоритм Кнута-Морриса-Пратта]]

== Источники информации ==
*[[wikipedia:Finite-state_machine|Wikipedia {{---}} Finite-state machine]]
*ISBN 978-5-8459-1794-2 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ, стр. 771{{---}}776.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Автоматы и регулярные языки]]
[[Категория:Точный поиск]]

Викиконспекты - Вклад участника [ru]

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