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

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

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

Определение:

Конечным автоматом(finite-state machine) называется набор из пяти элементов: [math]Q[/math] — множество состояний(конечное); [math]q_0 \in Q[/math] — стартовое состояние; [math]A \subset Q[/math] — допускающие состояния; [math] \Sigma [/math] — алфавит; [math] \delta \colon Q \times \Sigma \to Q[/math] — функция, определяющая правило перехода из одного состояния в другое по символу(функция перехода).

---

Пример конечного автомата

Нулевое состояние обозначим стартовым, а допускающим будет только первое. Алфавит взят [math]\Sigma =\left\{a,b\right\}[/math] Такой автомат допускает все строки, в которых нечетное количество символов [math]a[/math].

---

Определение:

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

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

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

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

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

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

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

---

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

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

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

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

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

• Символ [math]a[/math] совпадает с [math]q + 1[/math] символом строки [math]s[/math].

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

• Символ [math]a[/math] не совпадает с [math]q + 1[/math] символом строки [math]s[/math].

Тогда заметим, что если к строке, являющейся максимальным бордером предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае [math]\delta(q, a) = \delta(\pi_s(q), a)[/math].

([math]\pi_s(q)[/math] — префикс-функция, она возвращает длину максимального бордера для префикса строки [math]s[/math] длины [math]q[/math]) Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.

Асимптотика

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

Псевдокод

for q = 0 to m
  for a [math]\in \Sigma[/math]
    if q > 0 and a [math]\ne[/math] s[q + 1]
      [math]\delta[/math](q, a) = [math]\delta[/math]([math]\pi[/math](q), a)
    if c = s[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 Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы. Построение и анализ.