48
правок
Изменения
Новая страница: «Автомат Кнута-Морриса-Пратта используется в алгоритмах связанных с поиском образца в те...»
Автомат Кнута-Морриса-Пратта используется в алгоритмах связанных с поиском образца в тексте, в том числе в реальном времени.
== Основные определения ==
{{Определение
|id = automate
|definition = '''Конечным автоматом(finite-state machine)''' называется набор из пяти элементов:
* <tex>Q</tex> {{---}} множество состояний(конечное);
* <tex>q_0 \in Q</tex> {{---}} стартовое состояние;
* <tex>A \subset Q</tex> {{---}} допускающие состояния;
* <tex> \Sigma </tex> {{---}} алфавит;
* <tex> \delta \colon Q \times \Sigma \to Q</tex> {{---}} функция, определяющая правило перехода из одного состояния в другое по символу(''функция перехода'').
}}
----
==== Пример конечного автомата ====
[[Файл:Fin_aut_ex.png]]
Нулевое состояние обозначим стартовым, а допускающим будет только первое. Алфавит взят <tex>\Sigma =\left\{a,b\right\}</tex> Такой автомат допускает все строки, в которых нечетное количество символов <tex>a</tex>.
----
{{Определение
|id = suffix_func
|definition = Для строки <tex>s</tex> длиной <tex>m</tex> функция <tex> \sigma \colon \Sigma^* \to \left\{1,2, \dots ,m\right\}</tex> называется '''суффикс-функцией''', если каждой строке сопоставляется длина ее максимального суффикса, являющегося префиксом <tex>s</tex>.
}}
== Структура автомата ==
Автомат строится на строке-образце <tex>s</tex> длины <tex>m</tex>, которую в будущем мы будем искать в тексте.
Для автомата Кнута-Морриса-Пратта:
* <tex>Q = \left\{0,1,...,m\right\}</tex>
* <tex> q_0 = 0 </tex>
* <tex> A = \left\{m\right\} </tex>
* <tex> \delta(q, a) = \sigma(s[1 \dots q] + a) </tex>, где <tex>q</tex> {{---}} это состояние, <tex>a</tex> {{---}} символ, по которому осуществляется переход, a "<tex>+</tex>" {{---}} операция конкатенации (<tex>s[1, 0] = \varepsilon </tex>).
Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через автомат, то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние m символов полностью совпадают с образцом и мы нашли включение.
Заметим, что тот факт, что переход по символу осуществляется независимо от последующих, позволяет нам работать как с текстом, данным заранее, так и с текстом, который вводится в реальном времени.
----
==== Пример автомата Кнута-Морриса-Пратта ====
[[Файл:Kmp_aut_ex.png]]
Данный автомат построен для образца "<tex>abaab</tex>" и алфавита <tex>\Sigma =\left\{a, b\right\} </tex>
== Построение автомата ==
=== Идея алгоритма ===
Для каждого состояния и каждого символа будем определять значение функции перехода из данного состояния по данному символу. Пусть текущее состояние <tex>q</tex>. При считывании каждого нового символа <tex>a</tex> из текста возможно два варианта развития событий:
*Символ <tex>a</tex> совпадает с <tex>q + 1</tex> символом строки <tex>s</tex>.
Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае <tex>\delta(q, a) = q + 1</tex>.
*Символ <tex>a</tex> не совпадает с <tex>q + 1</tex> символом строки <tex>s</tex>.
Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_s(q), a)</tex>.
(<tex>\pi_s(q)</tex> {{---}} префикс-функция, она возвращает длину максимального [[Основные_определения,_связанные_со_строками#border|бордера]] для префикса строки <tex>s</tex> длины <tex>q</tex>)
Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.
=== Асимптотика ===
В данном алгоритме нам нужно лишь вычислить значение функции перехода в каждом состоянии для каждого символа. При предподсчитанной за <tex>O(m)</tex> префикс-функции вычисление для одного состояния и одного символа происходит за <tex>O(1)</tex>. Всего состояний <tex>m</tex>, а символов <tex>|\Sigma|</tex>. Итого <tex>O(m + m \cdot |\Sigma|)</tex>.
=== Псевдокод ===
'''for''' q = 0 '''to''' m
'''for''' a <tex>\in \Sigma</tex>
'''if''' q > 0 '''and''' a <tex>\ne</tex> s[q + 1]
<tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi</tex>(q), a)
'''if''' c = s[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 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ.
== Основные определения ==
{{Определение
|id = automate
|definition = '''Конечным автоматом(finite-state machine)''' называется набор из пяти элементов:
* <tex>Q</tex> {{---}} множество состояний(конечное);
* <tex>q_0 \in Q</tex> {{---}} стартовое состояние;
* <tex>A \subset Q</tex> {{---}} допускающие состояния;
* <tex> \Sigma </tex> {{---}} алфавит;
* <tex> \delta \colon Q \times \Sigma \to Q</tex> {{---}} функция, определяющая правило перехода из одного состояния в другое по символу(''функция перехода'').
}}
----
==== Пример конечного автомата ====
[[Файл:Fin_aut_ex.png]]
Нулевое состояние обозначим стартовым, а допускающим будет только первое. Алфавит взят <tex>\Sigma =\left\{a,b\right\}</tex> Такой автомат допускает все строки, в которых нечетное количество символов <tex>a</tex>.
----
{{Определение
|id = suffix_func
|definition = Для строки <tex>s</tex> длиной <tex>m</tex> функция <tex> \sigma \colon \Sigma^* \to \left\{1,2, \dots ,m\right\}</tex> называется '''суффикс-функцией''', если каждой строке сопоставляется длина ее максимального суффикса, являющегося префиксом <tex>s</tex>.
}}
== Структура автомата ==
Автомат строится на строке-образце <tex>s</tex> длины <tex>m</tex>, которую в будущем мы будем искать в тексте.
Для автомата Кнута-Морриса-Пратта:
* <tex>Q = \left\{0,1,...,m\right\}</tex>
* <tex> q_0 = 0 </tex>
* <tex> A = \left\{m\right\} </tex>
* <tex> \delta(q, a) = \sigma(s[1 \dots q] + a) </tex>, где <tex>q</tex> {{---}} это состояние, <tex>a</tex> {{---}} символ, по которому осуществляется переход, a "<tex>+</tex>" {{---}} операция конкатенации (<tex>s[1, 0] = \varepsilon </tex>).
Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через автомат, то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние m символов полностью совпадают с образцом и мы нашли включение.
Заметим, что тот факт, что переход по символу осуществляется независимо от последующих, позволяет нам работать как с текстом, данным заранее, так и с текстом, который вводится в реальном времени.
----
==== Пример автомата Кнута-Морриса-Пратта ====
[[Файл:Kmp_aut_ex.png]]
Данный автомат построен для образца "<tex>abaab</tex>" и алфавита <tex>\Sigma =\left\{a, b\right\} </tex>
== Построение автомата ==
=== Идея алгоритма ===
Для каждого состояния и каждого символа будем определять значение функции перехода из данного состояния по данному символу. Пусть текущее состояние <tex>q</tex>. При считывании каждого нового символа <tex>a</tex> из текста возможно два варианта развития событий:
*Символ <tex>a</tex> совпадает с <tex>q + 1</tex> символом строки <tex>s</tex>.
Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае <tex>\delta(q, a) = q + 1</tex>.
*Символ <tex>a</tex> не совпадает с <tex>q + 1</tex> символом строки <tex>s</tex>.
Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_s(q), a)</tex>.
(<tex>\pi_s(q)</tex> {{---}} префикс-функция, она возвращает длину максимального [[Основные_определения,_связанные_со_строками#border|бордера]] для префикса строки <tex>s</tex> длины <tex>q</tex>)
Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.
=== Асимптотика ===
В данном алгоритме нам нужно лишь вычислить значение функции перехода в каждом состоянии для каждого символа. При предподсчитанной за <tex>O(m)</tex> префикс-функции вычисление для одного состояния и одного символа происходит за <tex>O(1)</tex>. Всего состояний <tex>m</tex>, а символов <tex>|\Sigma|</tex>. Итого <tex>O(m + m \cdot |\Sigma|)</tex>.
=== Псевдокод ===
'''for''' q = 0 '''to''' m
'''for''' a <tex>\in \Sigma</tex>
'''if''' q > 0 '''and''' a <tex>\ne</tex> s[q + 1]
<tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi</tex>(q), a)
'''if''' c = s[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 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ.
