Хорошо известно, что регулярное выражение может быть распознано недетерминированным конечным автоматом, размер которого пропорционален регулярному выражению, или детерминированным FA, который потенциально экспоненциально больше. Кроме того, учитывая строку и регулярное выражение , NFA может проверить членство во времени, пропорциональноми DFA может проверить членство во времени, пропорциональном, Замедление для NFA возникает из-за того, что по сути нам необходимо отслеживать наборы возможных состояний, в которых может находиться автомат, и экспоненциальный рост DFA возникает из-за того, что его состояния являются элементами набора мощностей состояний NFA.
Можно ли эффективно (т. Е. Во времени лучше, чем , а пространство лучше, чем ) распознавать регулярные выражения, если мы разрешаем использовать более мощные машины чем конечные автоматы? (Например, есть ли краткость в распознавании обычных языков с помощью автоматов или счетчиков?)
источник
Ответы:
Достаточно легко обменять время на пространство следующим образом.
Преобразуйте регулярное выражение в NFA - для конкретности при сравнении алгоритмов мы будем предполагать, что - это число состояний NFA, так что ваше время для прямого моделирования NFA является действительным, а ваше пространство, ограниченное для запуска преобразованного DFA, также действует, когда вы работаете в ОЗУ, которое может адресовать столько памяти.O ( r s ) O ( 2 r )r O(rs) O(2r)
Теперь разделим состояния NFA (произвольно) на подмножеств не более чем состояний каждое. Внутри каждого подмножества мы можем индексировать подмножества в числами от до .S i ⌈ r / k ⌉ S i A i S i 0 2 ⌈ r / k ⌉ - 1k Si ⌈r/k⌉ Si Ai Si 0 2⌈r/k⌉−1
Составьте таблицу где и находятся в диапазоне от 0 до , - входной символ, а - (числовой индекс) подмножество . Значение, хранящееся в таблице, является (числовой индекс) подмножеством : состояние находится в тогда и только тогда, когда принадлежит и в есть состояние, которое переходит к на входном символе .i j k - 1 c A i S i S j y T [ i , j , c , A i ] y S j A i y cT[i,j,c,Ai] i j k−1 c Ai Si Sj y T[i,j,c,Ai] y Sj Ai y c
Чтобы смоделировать NFA, сохраните индексов, по одному для каждого , указав подмножество состояний в которые могут быть достигнуты при помощи некоторого префикса ввода. Для каждого входного символа используйте таблицы, чтобы найти для каждой пары набор состояний в который может быть достигнут из состояния в путем перехода наS i A i S i c i , j S j A i ck Si Ai Si c i,j Sj Ai c , а затем используйте побитовый двоичный код или операцию над числовые индексы этих наборов состояний объединяют их в единое подмножество состояний . Итак, каждый шаг моделирования занимает время O ( k 2 )Sj O(k2) и общее время моделирования составляет .O(sk2)
Требуемое пространство - это пространство для всех таблиц, которое равно . Анализ времени и пространства действителен для любой оперативной памяти, которая может адресовать столько памяти, и которая может выполнять двоичные операции со словами, которые достаточно велики, чтобы адресовать столько памяти.O(k22r/k)
Из-за квадратичной зависимости от компромисс между временем и пространством, который вы получаете от этого, не полностью соответствует моделированию NFA . Но потом, я скептически отношусь к тому, что O ( r s ) - это правильная временная граница для симуляции NFA: как вы моделируете один шаг NFA быстрее, чем рассматриваете все (возможно, квадратично много) переходы, разрешенные из текущего активное состояние в другое состояние? Разве это не должно быть O ( r 2 s ) ?k O(rs) O(r2s)
В любом случае, изменяя вы можете получить временные границы на континууме между границами DFA и NFA с меньшим пространством, чем DFA.k
источник
Это не ответ, но слишком долго для комментария. Я пытаюсь объяснить, почему этот вопрос может быть трудно понять.
Есть два способа определения вычислительной сложности для устройства X .
Первый и самый естественный способ является внутренним . Нужно сказать, как устройство X использует вход, чтобы мы могли позже посмотреть, как размер n входа влияет на время работы устройства. Также нужно сказать, что считается операцией (или шагом ). Затем мы просто позволяем устройству работать на операциях ввода и подсчета.
Например, внутреннее определение для NFA говорит, что для обработки строки длины n требуется n шагов ; внешнее определение, которое использует машину ОЗУ в качестве устройства Y, говорит, что наиболее известная верхняя граница - это, вероятно, ответ Дэвида Эппштейна. (В противном случае было бы странно, что (1) лучшая практическая реализация, указанная в другом ответе, не использует лучшую альтернативу, и (2) здесь никто не указал лучшую альтернативу.) Обратите также внимание, что строго говоря, ваше устройство X является регулярным выражением , но так как NFA имеет тот же размер, его можно принять за устройство X, на которое вы смотрите.
Так что, в некотором смысле, лучший ответ, на который вы могли бы надеяться, - это подтверждение в чем-то вроде модели клеточного зонда, что имитация NFA требует определенного времени. (Обратите внимание, что если вы принимаете во внимание преобразование NFA в DFA, вам нужно время, чтобы записать большое DFA, поэтому проблема с памятью там не единственная.)
источник
Даже если вы считаете, что нет ничего нового или старого, что можно узнать о сопоставлении регулярных выражений, посмотрите одну из самых красивых работ, с которыми я сталкивался в течение долгого времени: игра регулярных выражений S Fischer, F Huch и T Wilke, ICFP 2010.
(MMT Chakravarty заслуживает похвалы за рекомендацию этого документа.)
РЕДАКТИРОВАТЬ: Причина, по которой эта статья является актуальной, заключается в том, что она описывает новую технику (на основе Глушкова из 60-х годов), которая позволяет избежать создания полной NFA (не говоря уже о DFA), соответствующей RE. То, что делается вместо этого, напоминает запуск алгоритма маркировки, аналогичного общеизвестному алгоритму принятия решения о принятии слова NFA в синтаксическом дереве RE. Измерения производительности показывают, что это конкурентоспособно, даже с недавно опубликованной в Google библиотекой re2.
источник
Посмотрите на эту статью Расс Кокс. Он описывает подход, основанный на NFA, впервые примененный Кеном Томпсоном, с помощью которого входная строка s может быть сопоставлена с регулярным выражением r во времени O (| s |. C ) и пространстве O (| r |. D ), где c и d - верхние константы. В статье также подробно описывается реализация этой техники на языке C.
источник