Конечные автоматы¶

Конечный автомат, простой пример¶

Вообще конечный автомат - это довольно простой концепт. Это, грубо говоря, таблица с инструкциями, где записано, в какое состояние должен перейти автомат из текущего состояния, при условии внешней команды (или другого внешнего воздействия).

В принципе, при переходе автомат может выполнять какие-то действия.

Вот пример автомата, который проверяет, делится ли число в двоичной системе счисления на три:

Автомат описывает следующая схема (схемы нагляднее таблиц, но конвертируемы):

Признак делимости на три бинарного числа:

(это сложный автомат, вы можете поразбираться, почему он работает, если хотите)

Почситать количество ненулевых битов на нечетных и четных позициях. Если разность делится на три, то и само число делится на три.

Как это читать¶

стрелочка "извне" указывает на начальное состояние (с него начинается работа автомата)
остальные стрелки показывают переходы из состояния в состояние, условие перехода нарисовано раядом со стрелкой
конечное состояние (состояния) обозначаются двойным кружком. Конечное состояние может быть начальным одновременно.

Если строка не проходит по автомату, она "отклоняется".

Далее, автомат можно представить в виде таблицы:


        0     1
q0 |  q0 |  q1 |
q1 |  q2 |  q0 |
q2 |  q1 |  q2 |

Промежуточный итог¶

Итак, здесь конечный автомат:

Обладает конечным множеством состояний $Q = \{q_0, q_1, q_2\}$
$q_0 \in Q$ - начальное состояние (оно же конечное)
$\Sigma = \{0, 1\}$ - конечный набор входных данных
Также мы можем предолжить функцию $\delta$ - отображение $Q \times \Sigma$ в $Q$ , функция перехода ( $\delta : Q \times \Sigma \rightarrow \Sigma$ )

Что делают вот эти автоматы?¶

Конечный автомат, работа со строками¶

Конченый автомат, обозначаемый далее $M$ , содержит в себе пять элементов:

Конечное множество состояний $Q$
$q_0 \in Q$ - начальное состояние
$A \subseteq Q$ - множество конечных (допускающих) состояний
$\Sigma$ - конечный входной алфавит ( $\Sigma^*$ - конечный входной алфавит, но с $\epsilon$ - пустой строкой)
$\delta$ - отображение $Q \times \Sigma$ в $Q$ , функция перехода ( $\delta : Q \times \Sigma \rightarrow Q$ )

Замечания:

$Q \times \Sigma$ - это таблица соответсвующего размера, в которой указаны ссылки на нужные состояния
Когда автомат находится в состоянии $q_i$ и считывает символ $a \in Q$ , он переходит в состояние $\delta(q, a)$ , $q_j$ . Если $q_j \in A$ , то автомат принимает это состояние, иначе состояние считается отвергнутым.

Функция конечного состояния¶

Эта функция вычисляет состояние автомата $M$ после прочтения строки $w$ . Определение функции рекурсивно:

$\phi(\epsilon) = q_0$
$\phi(wa) = \delta(\phi(w), a)\ для\ w \in \Sigma^*, a \in \Sigma$

здесь и далее в тексте запись формата $(wa)$ , $(P_ja)$ и так далее обозначают передачу в функцию в качестве аргумента конкатенацию строки и символа $a$ .

Создание автомата¶

Конечный автомат для поиска подстрок создается при помощи функции суффиксов $\sigma$ .

Что делает эта функция? Она для строки $x$ рассчитывает значение

σ (x) = m a x {k : P_{k} я в л я е т с я с у ф ф и к с о м x}

$\sigma(x) = max\{k:P_k\ является\ суффиксом\ x\}$

Автомат $M$ для поиска вхождений строк оболадает множеством состояний $Q = \{0, 1, ...m\}$
$i$ -е состояние автомата соответствует (ожидаемой) "проверке" $i$ -го символа паттерна, последнее - найденому совпадению
Функция переходов автомата - $\delta(q, a) = \sigma(P[:q]a)$

Устройство функции переходов - почему так?¶

Допустим, после чтения строки $T[i]$ автомат оказался в состоянии $q$ . Функция $\delta(q, a)$ устроена таким образом, чтобы после чтения $T[i]$ номер полученного состояния $q$ соответствовал бы длине наибольшего префикса $j$ .

То есть для полученного $q$ , $P[:q]$ (или $P_q$ ) является наибольшим префиксом $T[:i]$ .

И автомат начинает сравнение следующего символа текста с того символа строки, на которое указывает состояние $q$ .

Примеры¶

Для паттерна GAGAGTT

Вариант сдвига #1:

Переход:

Вариант сдвига #2:

Переход (используется один из "тривиальных" переходов в начальное состояние):

Автомат после чтения нового символа $T[i + 1] = a$ должен перейти в состояние с максимальным префиксом паттерна $P$ , который при этом еще и суффикс $T_ia$ : это $\sigma(T_ia)$ , и одновременно $\sigma(P_qa)$ .

Есть два варианта того, что может случиться при переходе:

$a = P[q + 1]$ , тогда переход осуществляется "вдоль основной оси" автомата вправо, $\delta(q,a)=q+1$ - так как $a$ продолжает совпадать с паттерном
иначе надо найти другой наибольший префикс паттерна $P$ , совпадающий с $T[:i]$ . Эта информация хранится в конечном автомате.
$\phi(T_i) = \sigma(T_i)$

$\Sigma = \{0, 1\}$
w = "010101"

$\phi(\epsilon) = q_0$
$\phi(wa) = \delta(\phi(w), a)$

$\phi(010101) -> \delta(\phi(01010), 1)$

$\phi(01010) -> \delta(\phi(0101), 0)$

$\phi(0101) -> \delta(\phi(010), 1)$

$\phi(010) -> \delta(\phi(01), 0)$

$\phi(01) -> \delta(\phi(0), 1)$

$\phi(0) -> \delta(\phi(), 0)$

Вычисление функции перехода¶

Или таблицы перехода, если угодно

Очень медленная функция, $O(m^3|\Sigma|$ ):

ComputeDelta(pattern, Sigma):
1  m = Length(pattern)
2  for q = [0..m]:
3      for a in Sigma:  -- каждый символ алфавита
4          k = Min(m + 1, q + 2)
5          repeat
6              k -= 1
7          until P[:k] is prefix of P[:q] ++ a  -- P[:q] ++ a - конкатенация P[:q] и a
8          delta(q,a) = k  -- запоминаем значение в таблицу
9  return delta  -- можно воспринимать как двумерную таблицу (N_states + 1, |Sigma|)

Можно ускорить работу до $O(m|\Sigma|$ ), но для этого нужно использовать некоторые хитрости, которые используются в алгоритме Кнута-Морриса-Пратта.

Алгоритм сравнения и алгоритм поиска максимального префикса¶

После составления конечного автомата сам алгоритм действует максимально прямолинейно:

FAMatcher(text, delta, m):
1  -- В автомат передается не паттерн, а сразу функция delta, а так же m - длина паттерна
2  n = Length(text)
3  matches = new empty List
4  q = 0  -- начальное состояние
5  for i = [0..n):
6      q = delta(q, text[i])  
7      if q == m:
8          matches.append(i - m + 1)
9  return matches

Алгоритм Кнута-Морриса-Пратта¶

Алгоритм был разработан в 1973 (?) году Кнутом и Праттом, и независимо Моррисом. Опубликован совместно.

Это был первый алгоритм сравнения строк, работающий за $O(n + m)$ в худшем случае, при этом алгоритм требует всего $O(m)$ дополнительной памяти (сверх той, которая и так занята текстом и паттерном).

Сложность алгоритма никак не зависит от размера алфавита (с оговоркой, что сравнение двух элементов алфавита выполняется за $O(1)$ )

Основные идеи, используемые в данном алгоритме¶

Во-первых, сравнение идет "слева направо", и смещение выравнивания паттерна и текста движется в том же направлении, т.е. "слева направо".

Вообще, направление неважно. Если паттерн содержится в тексте, неважно, в каком направлении писался текст - важно, что совпадение есть

Во-вторых, каждый символ из текста сравнивается с паттерном не более $O(1)$ раз
В третьих, в паттерне ищутся части, которые являются самоповторяющимися, и информация об этих повторениях заносится в специальную таблицу
Таблица используется для вычисления сдвига при несовпадении символов или после того, как найдено полное совпадение

Пример¶

Пример сдвига¶

(Да, почти такая же иллюстрация была раньше. Но принцип очень похож)

Что мы наблюдаем?

Есть совпадающий сегмент длины $q$
Также у сегмента есть префикс длины $k$ , который совпадает с суффиксом совпадающей части паттерна. Также есть, например, меньший по размеру суффикс $G$ , но нас интересует наибольший.
Сопоставление этого префикса и суффикса совпавшего сегмента дает новое выравнивание, при этом, конечно, мы можем не проверять те символы, про которые известно, что они совпали, а начинать сразу же с того места, где "споткнулись".
Интуитивно, из последнего и следует линейность $O(n)$ по длине текста

Пример того, как паттерн повторяет сам себя¶

Что с самоповторением паттерна?

Не нужно считать каждый раз, насколько совпадает суффикс текущего выравнивания с перфиксом паттерна. Для каждого положения $i$ в паттерне будет постоянное $\pi_i$ (так в литературе называют значение префиксной функции). На самом деле, это просто таблица сдвигов, которую можно вычислить для данного паттерна.
С другой стороны, это может быть и функция $\pi: \{1, 2, m-1\} \rightarrow \{0, 1, m-1\}$ , определяемая как

π [q] = m a x {k : k < q и P_{k} я в л я е т с я с у ф ф и к с о м P_{q}},

$\pi[q] = max \{k:k<q\ и\ P_k\ является\ суффиксом\ P_q\},$

где $P_i$ - префикс паттерна длины $i$ .

Вот так этот процесс можно визуализировать:

Префикс $G$ был отброшен, так как он меньше, чем префикс $GAG$

Вычисление таблицы¶

Возможно, это наиболее сложная часть алгоритма KMP, в частности, доказательство того, что обработка паттерна завершается за $O(m)$ .

"Наивный" алгоритм с временем более линейного довольно прост и мало отличается от "наивного" алгоритма сравнения строк.
Более "хитрый" подход использует для составления таблицы ту информацию, которая была вычислена ранее и сохранена в таблие.

ComputePrefix(pattern):
1  m = Length(pattern)
2  table = new Array of zeros of Length(m)
3  k = 0  -- сколько символов префикса совпало
4  for q in [1..m):  -- обход всех символов в паттерне
5      while k > 0 and pattern[k] != pattern[q]:
6          k = table[k-1]
7      if pattern[k] == pattern[q]:  -- эта часть вне while
8          k += 1
9      table[q] = k
10 return table

Демонстрация работы алгоритма¶

красный - неудачная проверка в 7 строкеif pattern ...
зеленый - успешные проверки в 7 строке, k += 1
желтый - выполнено условие цикла while, используется старая информация из таблицы (известно, что похожий суффикс был)

Сам алгоритм¶

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

KMP(text, pattern):
1  m = Length(pattern)
2  n = Length(text)
3  table = ComputePrefix(pattern)
4  q = 0  -- сколько символов совпало 
5  matches = new empty List
6  for i in [0..n):  -- обход всех символов в тексте
7      while q > 0 and pattern[q] != text[i]:
8          q = table[q-1]
9      if pattern[q] == text[i]:  -- эта часть вне while
10          q += 1
11     if pattern[q] == m:  -- совпали все символы паттерна
12         matches.append(i - m + 1)  -- начало выравнивания
13         q = table[q-1]
14     return matches

Сходства с алгоритмом составления таблицы префиксов¶

Вычисление префикса

ComputePrefix(pattern):
1  m = Length(pattern)
2  table = new Array of zeros of Length(m)
3  k = 0  -- сколько символов префикса совпало
4  for q in [1..m):  -- обход всех символов в паттерне
5      while k > 0 and pattern[k] != pattern[q]:
6          k = table[k-1]
7      if pattern[k] == pattern[q]:  -- эта часть вне while
8          k += 1
9  ...

... и сам KMP:

KMP(text, pattern):
1  m = Length(pattern)
2  n = Length(text)
3  table = ComputePrefix(pattern) 
4  q = 0  -- сколько символов совпало 
5  -- matches = new empty List  -- сейчас не важна
6  for i in [0..n):
7      while q > 0 and pattern[q] != text[i]:
8          q = table[q-1]
9      if pattern[q] == text[i]:
10          q += 1
11  ...

если заменить в первом случае pattern на text, код станет практически неотличимым.

Домашняя работа¶

Реализовать алгоритм вычисления функции переходов для паттерна, работающий за время O(m^3 * |Sigma|) Дополнительно:
Реализовать при помощи оптимизации по поиску префиксов, аналогичному алгоритму КМП, алгоритм для составления конечного автомата за O(m * |Sigma|)
Разобрать 2 примера работы алгоритма на разных строках (ориентироваться на строку длиной 5-7 символов), в которых при этом есть префиксы, одновременно являющиеся суффиксами