Автомат Кнута-Морриса-Пратта - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:19:35Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:32, 1 сентября 2022

2022-09-01T05:32:15Z

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

2018-06-27T22:29:31Z

‎Псевдокод

Shersh: /* Источники информации */ добавлена категория

2016-02-02T11:50:06Z

‎Источники информации: добавлена категория

YanaZimka в 21:33, 15 июня 2015

2015-06-15T21:33:01Z

YanaZimka в 21:29, 15 июня 2015

2015-06-15T21:29:21Z

Внесённые изменения

YanaZimka: Новая страница: «Автомат Кнута-Морриса-Пратта используется в алгоритмах связанных с поиском образца в те...»

2015-06-15T11:31:03Z

Новая страница: «Автомат Кнута-Морриса-Пратта используется в алгоритмах связанных с поиском образца в те...»

Новая страница

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

== Основные определения ==

{{Определение
|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 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ.

← Предыдущая		Версия 16:19, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	[[Детерминированные_конечные_автоматы\|Автомат]] Кнута-Морриса-Пратта используется в алгоритмах, связанных с поиском образца в тексте, в том числе в реальном времени.		[[Детерминированные_конечные_автоматы\|Автомат]] Кнута-Морриса-Пратта используется в алгоритмах, связанных с поиском образца в тексте, в том числе в реальном времени.

← Предыдущая		Версия 05:32, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	[[Детерминированные_конечные_автоматы\|Автомат]] Кнута-Морриса-Пратта используется в алгоритмах, связанных с поиском образца в тексте, в том числе в реальном времени.		[[Детерминированные_конечные_автоматы\|Автомат]] Кнута-Морриса-Пратта используется в алгоритмах, связанных с поиском образца в тексте, в том числе в реальном времени.

@@ Строка 62: / Строка 62: @@
         '''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''' c = p[q + 1]
+        '''if''' a = p[q + 1]
           <tex>\delta</tex>(q, a) = q + 1
         '''else'''

← Предыдущая		Версия 11:50, 2 февраля 2016
Строка 86:		Строка 86:
	[[Категория: Поиск подстроки в строке]]		[[Категория: Поиск подстроки в строке]]
	[[Категория: Автоматы и регулярные языки]]		[[Категория: Автоматы и регулярные языки]]
		+	[[Категория:Точный поиск]]

@@ Строка 26: / Строка 26: @@
 * <tex> s = 0 </tex>
 * <tex> T = \left\{m\right\} </tex>
-* <tex> \delta(q, a) = \sigma(p[1 \dots q] + a) </tex>, где <tex>q</tex> {{---}} это состояние, <tex>a</tex> {{---}} символ, по которому осуществляется переход, a "<tex>+</tex>" {{---}} операция конкатенации (<tex>p[1, 0] = \varepsilon </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> символов полностью совпадают с образцом и мы нашли включение.
@@ Строка 61: / Строка 61: @@
       '''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</tex>(q), a)
+          <tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi_p</tex>(q), a)
         '''if''' c = p[q + 1]
           <tex>\delta</tex>(q, a) = q + 1