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

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

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

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

Для строки [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(p[1 \dots q] + a) [/math], где [math]q[/math] — это состояние, [math]a[/math] — символ, по которому осуществляется переход, a "[math]+[/math]" — операция конкатенации ([math]p[1, 0] = \varepsilon [/math]).

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

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

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

Данный автомат построен для образца "[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_p[/math](q), a)
      if a = 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.