Автомат Кнута-Морриса-Пратта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Автомат Кнута-Морриса-Пратта используется в алгоритмах связанных с поиском образца в те...»)
 
Строка 1: Строка 1:
Автомат Кнута-Морриса-Пратта используется в алгоритмах связанных с поиском образца в тексте, в том числе в реальном времени.
+
[[Детерминированные_конечные_автоматы|Автомат]] Кнута-Морриса-Пратта используется в алгоритмах, связанных с поиском образца в тексте, в том числе в реальном времени.
  
== Основные определения ==
+
== Суффикс-функция ==
  
 
{{Определение
 
{{Определение
|id = automate
+
|id = suffix_func
|definition = '''Конечным автоматом(finite-state machine)''' называется набор из пяти элементов:
+
|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>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> {{---}} функция, определяющая правило перехода из одного состояния в другое по символу(''функция перехода'').
 
 
}}
 
}}
 +
==== Пример суффикс-функции ====
  
----
+
Пусть строка <tex>p</tex>="<tex>abaab</tex>". Вот несколько примеров значений суффикс-функции для нее.
 
 
==== Пример конечного автомата ====
 
 
 
[[Файл:Fin_aut_ex.png‎]]
 
  
Нулевое состояние обозначим стартовым, а допускающим будет только первое. Алфавит взят <tex>\Sigma =\left\{a,b\right\}</tex> Такой автомат допускает все строки, в которых нечетное количество символов <tex>a</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>.
|id = suffix_func
+
:В данном случае "<tex>ab</tex>" является префиксом <tex>p</tex>, а все суффиксы длиннее {{---}} нет.
|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>p</tex> длины <tex>m</tex>, которую в будущем мы будем искать в тексте.  
  
Для автомата Кнута-Морриса-Пратта:
+
Для [[Детерминированные_конечные_автоматы|автомата]] Кнута-Морриса-Пратта:
 
* <tex>Q = \left\{0,1,...,m\right\}</tex>
 
* <tex>Q = \left\{0,1,...,m\right\}</tex>
* <tex> q_0 = 0 </tex>
+
* <tex> s = 0 </tex>
* <tex> A = \left\{m\right\} </tex>
+
* <tex> T = \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>).
+
* <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>).
  
Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через автомат, то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние m символов полностью совпадают с образцом и мы нашли включение.
+
Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через [[Детерминированные_конечные_автоматы|автомат]], то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние <tex>m</tex> символов полностью совпадают с образцом и мы нашли включение.
  
 
Заметим, что тот факт, что переход по символу осуществляется независимо от последующих, позволяет нам работать как с текстом, данным заранее, так и с текстом, который вводится в реальном времени.
 
Заметим, что тот факт, что переход по символу осуществляется независимо от последующих, позволяет нам работать как с текстом, данным заранее, так и с текстом, который вводится в реальном времени.
  
----
 
 
==== Пример автомата Кнута-Морриса-Пратта ====
 
==== Пример автомата Кнута-Морриса-Пратта ====
 
[[Файл:Kmp_aut_ex.png‎]]
 
[[Файл:Kmp_aut_ex.png‎]]
Строка 54: Строка 43:
 
Для каждого состояния и каждого символа будем определять значение функции перехода из данного состояния по данному символу. Пусть текущее состояние <tex>q</tex>. При считывании каждого нового символа <tex>a</tex> из текста возможно два варианта развития событий:
 
Для каждого состояния и каждого символа будем определять значение функции перехода из данного состояния по данному символу. Пусть текущее состояние <tex>q</tex>. При считывании каждого нового символа <tex>a</tex> из текста возможно два варианта развития событий:
  
*Символ <tex>a</tex> совпадает с <tex>q + 1</tex> символом строки <tex>s</tex>.  
+
<center>''Символ <tex>a</tex> совпадает с <tex>q + 1</tex> символом строки <tex>p</tex>.''</center>
Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае <tex>\delta(q, a) = q + 1</tex>.
+
 
 +
* Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае <tex>\delta(q, a) = q + 1</tex>.
  
*Символ <tex>a</tex> не совпадает с <tex>q + 1</tex> символом строки <tex>s</tex>.
+
<center>''Символ <tex>a</tex> не совпадает с <tex>q + 1</tex> символом строки <tex>p</tex>.''</center>
Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_s(q), a)</tex>.
 
  
(<tex>\pi_s(q)</tex> {{---}} префикс-функция, она возвращает длину максимального [[Основные_определения,_связанные_со_строками#border|бордера]] для префикса строки <tex>s</tex> длины <tex>q</tex>)
+
* Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_p(q), a)</tex>, где <tex>\pi_p(q)</tex> {{---}} [[Префикс-функция|префикс-функция]] для строки <tex>p</tex>. Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.
Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.
 
  
 
=== Асимптотика ===
 
=== Асимптотика ===
Строка 69: Строка 57:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
  '''for''' q = 0 '''to''' m
+
  '''function''' make_kmp()
  '''for''' a <tex>\in \Sigma</tex>
+
  '''for''' q = 0 '''to''' m
    '''if''' q > 0 '''and''' a <tex>\ne</tex> s[q + 1]
+
    '''for''' a <tex>\in \Sigma</tex>
      <tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi</tex>(q), a)
+
      '''if''' q > 0 '''and''' a <tex>\ne</tex> p[q + 1]
    '''if''' c = s[q + 1]
+
        <tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi</tex>(q), a)
      <tex>\delta</tex>(q, a) = q + 1
+
      '''if''' c = p[q + 1]
    '''else'''
+
        <tex>\delta</tex>(q, a) = q + 1
      <tex>\delta</tex>(q, a) = q
+
      '''else'''
 +
        <tex>\delta</tex>(q, a) = q
 +
 
 +
== Сравнение с другими алгоритмами поиска образца в тексте ==
 +
 
 +
При решении задачи поиска всех включений образца в текст также часто применяются алгоритмы Ахо-Корасик и Кнута-Морриса-Пратта.
 +
 
 +
Алгоритм Ахо-Корасик использует автомат, построенный на основе приведенного здесь, и является расширением рассматриваемого алгоритма. Он применяется в несколько иных случаях {{---}} когда образцов для поиска несколько. И решает эту задачу быстрее, чем построение нескольких автоматов Кнута-Морриса-Пратта.
 +
 
 +
Алгоритм Кнута-Морриса-Пратта решает ту же задачу, что и алгоритм с применением одноименного автомата. Однако он не может работать с текстом, вводимым в режиме реального времени, ему нужно заранее знать текст, в котором нужно искать образец. Также, если текст достаточно объемный, алгоритм Кнута-Морриса-Пратта будет использовать гораздо больше памяти, чем приведенный выше в данной статье. Однако, если текст небольшой и дан заранее, алгоритм Кнута-Морриса-Пратта будет работать быстрее.
  
 
== См. также ==
 
== См. также ==
 
*[[Алгоритм Ахо-Корасик]]
 
*[[Алгоритм Ахо-Корасик]]
 +
*[[Алгоритм Кнута-Морриса-Пратта]]
  
 
== Источники информации ==
 
== Источники информации ==
 
*[[wikipedia:Finite-state_machine|Wikipedia {{---}} Finite-state machine]]
 
*[[wikipedia:Finite-state_machine|Wikipedia {{---}} Finite-state machine]]
*ISBN 978-5-8459-1794-2 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ.
+
*ISBN 978-5-8459-1794-2 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ, стр. 771{{---}}776.
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Поиск подстроки в строке]]
 +
[[Категория: Автоматы и регулярные языки]]

Версия 00:29, 16 июня 2015

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

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

Определение:
Для строки [math]p[/math] длиной [math]m[/math] функция [math] \sigma_p \colon \Sigma^* \to \left\{1,2, \dots ,m\right\}[/math] называется суффикс-функцией, если она сопоставляет любой строке [math]x[/math], состоящей из символов алфавита [math]\Sigma[/math], длину максимального суффикса [math]x[/math], являющегося префиксом [math]p[/math].

Пример суффикс-функции

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

  • [math]\sigma_p("aba")=3[/math].
В данном случае вся строка является префиксом [math]p[/math].
  • [math]\sigma_p("bb")=0[/math].
В данном случае какой бы суффикс мы ни взяли, ни один из них не является префиксом [math]p[/math].
  • [math]\sigma_p("aaab")=2[/math].
В данном случае "[math]ab[/math]" является префиксом [math]p[/math], а все суффиксы длиннее — нет.

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

Автомат строится на строке-образце [math]p[/math] длины [math]m[/math], которую в будущем мы будем искать в тексте.

Для автомата Кнута-Морриса-Пратта:

  • [math]Q = \left\{0,1,...,m\right\}[/math]
  • [math] s = 0 [/math]
  • [math] T = \left\{m\right\} [/math]
  • [math] \delta(q, a) = \sigma(p[1 \dots q] + a) [/math], где [math]q[/math] — это состояние, [math]a[/math] — символ, по которому осуществляется переход, a "[math]+[/math]" — операция конкатенации ([math]p[1, 0] = \varepsilon [/math]).

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

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

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

Kmp aut ex.png

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

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

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

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

Символ [math]a[/math] совпадает с [math]q + 1[/math] символом строки [math]p[/math].
  • Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае [math]\delta(q, a) = q + 1[/math].
Символ [math]a[/math] не совпадает с [math]q + 1[/math] символом строки [math]p[/math].
  • Тогда заметим, что если к строке, являющейся максимальным бордером предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае [math]\delta(q, a) = \delta(\pi_p(q), a)[/math], где [math]\pi_p(q)[/math]префикс-функция для строки [math]p[/math]. Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.

Асимптотика

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

Псевдокод

function make_kmp()
  for q = 0 to m
    for a [math]\in \Sigma[/math]
      if q > 0 and a [math]\ne[/math] p[q + 1]
        [math]\delta[/math](q, a) = [math]\delta[/math]([math]\pi[/math](q), a)
      if c = p[q + 1]
        [math]\delta[/math](q, a) = q + 1
      else
        [math]\delta[/math](q, a) = q

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

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

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

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

См. также

Источники информации

  • Wikipedia — Finite-state machine
  • ISBN 978-5-8459-1794-2 Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы. Построение и анализ, стр. 771—776.