Алгоритм преобразования очень большого NFA в DFA

12

У меня действительно большой недетерминированный конечный автомат, и мне нужно преобразовать его в DFA.

По большому счету я имею в виду более 40 000 штатов. До сих пор я провел несколько экспериментов и запрограммировал алгоритм по умолчанию, который выполняет поиск в таблице (как описано здесь ), но даже после оптимизации он довольно медленный и занимает очень много памяти. Я осознаю тот факт, что число штатов может расти в геометрической прогрессии, но после минимизации результирующий DFA имеет около 9 000 штатов, и это терпимо.

Итак, мой вопрос, есть ли какой-нибудь алгоритм, который был бы быстрее или более дружественным к памяти?

Jendas
источник
видео, по-видимому, по стандартному алгоритму определения. см., например, минимизацию NFA без определения,
переполнение стека
Если вы выполняете наивное преобразование NFA-> DFA (используя конструкцию продукта), насколько велик получаемый DFA? (до минимизации)
DW
2
Что ты хочешь делать с DFA? Если вы заинтересованы в проверках включения, есть алгоритмы, которые делают это напрямую.
Виджай Д
Спасибо за очень быстрые ответы. По размеру не могу сказать точно, так как у меня закончилась ОЗУ, но я дам ему более внимательный взгляд и чем расширить вопрос. Из-за того, что я хочу сделать, я не уверен, смогу ли я открыто поговорить об этом, поскольку это немного моего твердого ноу-хау. Но я могу с уверенностью сказать, что мне действительно нужен полученный DFA.
Джендас
1
Вы пробовали запустить алгоритм Angluin для изучения DFA из запросов на членство и эквивалентность? Членская часть проста (просто запустите DFA на нужной строке); для эквивалентности вы можете нарисовать много случайных строк или попробовать все строки до определенной длины. Это всего лишь эвристика, так как вы никогда не узнаете, когда закончите, но я обнаружил, что этот трюк хорошо работает на практике ...
Aryeh

Ответы:

6

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

Следующая статья кажется актуальной:

Он оценивает ряд различных алгоритмов минимизации DFA, включая их применение в вашей ситуации, когда мы начинаем с NFA и хотим преобразовать его в DFA и минимизировать его.

Как выглядит декомпозиция сильно связанных компонентов (SCC) вашего NFA (рассматривая его как ориентированный граф)? Есть ли у него много компонентов, где ни один из компонентов не слишком велик? Если так, то мне интересно, возможно ли было бы разработать алгоритм «разделяй и властвуй», в котором вы берете один компонент, конвертируете его из NFA в DFA, а затем минимизируете его, а затем заменяете оригинал новой определенной версией. Это должно быть возможно для компонентов с одним входом (где все ребра в этом компоненте ведут к одной вершине, вершине входа). Я не сразу вижу, возможно ли сделать что-то подобное для произвольных NFA, но если вы проверите, как выглядит структура SCC, то вы сможете определить, стоит ли исследовать такого рода направление или нет. ,

DW
источник
Алгоритм Бжозовского кажется многообещающим, но техника «разделяй и властвуй» еще больше! В моем случае это действительно легко сделать и не требует больших изменений кода. Я сделаю это, и если это сработает, я приму ваш ответ.
Джендас
2
Я пришел, я спросил, я разделил, я победил
Jendas
2

это, очевидно, не очень хорошо изученная проблема в смысле известных / доступных алгоритмов, отличных от оригинальной / давней стратегии «определиться с DFA / минимизировать DFA». Вы, кажется, указываете, что этап определения является проблематичным, но это, конечно, типично, учитывая, что он имеет худший случай с экспоненциальным пространством / временем. обратите внимание, что существует несколько алгоритмов минимизации DFA, которые в среднем могут существенно различаться по производительности.

это также более неофициально известно как «минимизация NFA без определения» . известно, что это сложно, в том смысле, что в принципе даже нет алгоритмов аппроксимации, если P = Pspace, как показано в этой статье:

однако в этой статье рассматривается редко изучаемый случай некоторых алгоритмов, которые не основаны на поиске определенного DFA 1- го :

Мы представляем различные методы для уменьшения числа состояний и переходов в недетерминированных автоматах. Эти методы основаны на двух предварительных заказах над набором состояний, связанных с включением левого и правого языков. Поскольку их точное вычисление является NP-сложным, мы фокусируемся на полиномиальных аппроксимациях, которые все же позволяют уменьшить NFA.

обратите внимание на общедоступный пакет / реализацию, которая может обрабатывать большие преобразования / минимизации NFA / DFA и т. д. в целом максимально эффективно, - это библиотека AT & T FSM .

у него есть стратегия, fsmcompactкоторой иногда может хватить:

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

ВЗН
источник
см. также О сокращении NFA Илие, Наварро, Ю
взл