Параллельное сопоставление регулярных выражений с NFA против DFA? Какой из них быстрее?
Я читал о NFA и DFA, и кажется, что самый популярный и самый быстрый способ внедрения regex matcher - это создание NFA из regex, преобразование его в DFA, минимизация этого DFA, реализация его на любом языке и использование его.
DFA - лучший выбор по сравнению с NFA, потому что он имеет только один переход для ввода, в то время как NFA может иметь много. Таким образом, у ДФА есть только один путь, а у НФА - много.
Но это то, где я не понимаю. Почему мы должны отслеживать состояния NFA и возвращаться к ним, что замедляет нас, можем ли мы разделиться на разные потоки при обнаружении входа в более чем одно состояние и вычислить каждый путь параллельно? Не будет быстрее, чем DFA? Или я что-то упустил?
1 ответ
Вообще говоря, DFA быстрее, но NFA более компактен. NFA пропорционально размеру регулярного выражения. (Неформальное доказательство: каждый операторный узел в синтаксисе регулярного выражения просто добавляет новый узел в граф NFA.) Поскольку DFA формируется из подмножеств наборов состояний NFA, существуют случаи, когда он может быть довольно большим. В худшем случае DFA имеет экспоненциальный размер по сравнению с регулярным выражением. Примером этого является выражение формы (a|b)(a|b)(a|b)(a|b)...(a|b) где есть N (a|b) Единицы измерения переводятся в DFA с размером O(2**N). Он содержит переходы через уникальные состояния для всех комбинаций для a а также b, Вырожденный DFA может превышать размер кэша ЦП в тех случаях, когда структуры данных, необходимые для имитации эквивалентного NFA, помещаются в кэш.
Из-за дополнительных шагов DFA немного дороже. Таким образом, применяются компромиссы: будет ли достаточно данных обработано симулятором NFA для обоснования создания DFA.
Симуляция NFA может полностью избежать касания частей регулярного выражения, которые вообще не относятся к вводу. Например, предположим, что регулярное выражение имеет форму R1|R2, где R1 очень прост и мал, а R2 - огромный, сложный зверь. Предположим, что входные данные обычно совпадают с R1, а R2 практически не применяется (как, например, из-за некоторого несовпадения префикса). Это влияет на компромисс: компиляция в DFA означает, что все компилируется, простая часть R1 и чудовищная часть R2.
Наконец, реализация не должна быть строго NFA или DFA. Симулятор NFA может кэшировать наборы состояний, которые он вычисляет. Эти кэшированные состояния эквивалентны состояниям DFA и обеспечивают такое же преимущество, что и компиляция DFA. Вы можете подумать, что это "JIT для NFA". Кэш может быть урезан до некоторого фиксированного размера и подчинен политике замены, чтобы выражения, полные DFA которых были бы большими, могли обрабатываться в меньшем объеме памяти (и почти так же быстро, если данные показывают хорошую локальность ссылок в кеше),