Продолжительность DFA не O (n), но O (nm)

Question

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

В качестве примера рассмотрим {l} b регулярное выражение (все слова, начинающиеся с повторяющихся l раз, следуют ab), его DFA имеет m = 1 + 1 узел. Согласование его с строкой a {k} b с k> l означает, что вы столкнетесь с наихудшим сценарием наличия (m - 1) активных состояний после l символов в строке.

Что я пропустил? Литература вручную наводит практическую реализацию только на теоретический вопрос о знании того, соответствует ли заданная полная строка (т. Е. Не одна из ее подстроки) регулярному выражению.

С того места, где я работаю, NFA или DFA будут занимать O (нм) раз (при этом m является числом узлов в NFA или DFA и n числом символов). Единственное, что NFA имеет больше узлов, чем DFA.

Answer 1

Исторически DFA сначала определялись так, чтобы соответствовать целым строкам, а не искать подстроки, поэтому в литературе обычно говорится о временной сложности DFA в отношении взятия одной строки, а затем возвращается ли вся строка совпадений или нет. Если у вас есть DFA, который соответствует всей строке, и вы хотите использовать ее для поиска подстрок, тогда вы по существу запускаете DFA несколько раз, один раз для каждой возможной стартовой позиции, поэтому вы получаете O (mn) как время выполнения, а не O (n).

Однако, если ваша цель состояла в том, чтобы найти подстроку где-то, вам, вероятно, будет лучше переделать ваш DFA. Представьте себе, например, что вы хотите сопоставить некоторое регулярное выражение R с помощью DFA. Вместо того, чтобы создавать DFA для R и запускать его, начиная с каждого возможного местоположения, создайте DFA для регулярного выражения Σ * R Σ *. Теперь, если какая-либо подстрока ввода совпадает с R, вся строка соответствует Σ * R Σ *, поэтому вам нужно всего лишь выполнить один проход DFA по строке. Это снижает время выполнения до O (n), поскольку вы просто запускаете один проход.

Answer 2

Если у вас действительно есть DFA, у вас не будет много активных состояний. Определено, что DFA имеет ровно одно активное состояние. И каждый персонаж может привести только к следующему состоянию.

Если вы берете это свойство, вы начинаете с состояния начала и потребляете n символов. На каждом персонаже вы проверяете: - если нет перехода на не состояние ошибки => несовпадение - если есть переход к не состоянию ошибки => продолжить

В конце концов проверки, если текущее состояние является конечное состояние. Если so => ​​success, else => несоответствие.

С моей точки зрения, NFA принимает O (n * m), где DFA принимает O (n). Производительность DFA не зависит от сложности шаблона (количество узлов).

Тем не менее, я не знаю, почему вы приняли ответ, который ссылается на строковый поиск (который действительно не O (n)) с DFA вместо соответствия строки с DFA. Но если это ваша проблема: есть алгоритмы, которые получены из DFA, которые выполняют работу лучше, чем поиск Σ RΣ, это будет Кнут-Моррис-Пратт (для одиночных паттернов) и Aho-Corasick (несколько шаблонов) , Основной DFA сжимается, но оба алгоритма используют свойство, что они выполняют ровно один переход для одного символа, не имеющего нескольких состояний в любое время (например, в NFA).