Определение, отменяют ли регулярные выражения друг друга

Question

Моя задача - определить, должна ли строка вызывать команду в моем командном процессоре C #, это настраивается во время выполнения.

У меня есть две коллекции регулярных выражений. Для первого набора 'EnabledPatterns' команда включена, если какой-либо из шаблонов соответствует командной строке. Для второго DisabledPatterns команда отключается, если какой-либо из шаблонов соответствует командной строке. Возможно, что существует перекрытие, когда шаблон в EnabledPattern соответствует той же строке, что и шаблон в DisabledPattern. Например:

EnablePatterns содержит ^ ABC. $ DisabledPatterns содержит ^ A. * $

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

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

Answer 1

Я бы сказал, что лучше всего сначала проверять отключенные шаблоны, а затем проверять только включенные шаблоны, если все отключенные шаблоны возвращали значение false.

Edit:

Хорошо ... Я только что проработал это с кем-то в офисе ...

Оказывается, есть алгоритм N ^ 4, который вы можете использовать для этого.

В основном вам необходимо:

1. Преобразование обоих регулярных выражений в NFA
2. Преобразование NFA в DFA
3. Сравните DFA, чтобы увидеть, является ли один подмножеством другого

Чтобы сравнить DFA, необходимо выполнить параллельный поиск в глубину для обоих графиков, начиная с начального узла и следуя входным данным. Каждый раз, когда вы следуете за вводом в каждом графе, вы строите составной узел (n1, n2), где n1 - это узел из первого графа, а n2 - это узел из второго графа.

Если какой-либо узел является принимающим состоянием, пометьте его *, чтобы у вас было (n1 *, n2) (n1, n2 *), (n1 *, n2 *) или (n1, n2).

Как только вы закончите, посмотрите на все ребра, где n1 является принимающим состоянием (n1 *, x). если X также является принимающим состоянием, то regex1 является подмножеством regex2.

Этот алгоритм должен быть в худшем случае O (n ^ 4). Может быть, лучше, но хуже не будет.

Скоро я расскажу о публикации некоторого кода.

Однако, очевидно, вы захотите сделать это только в том случае, если объем изменяемых регулярных выражений будет значительно ниже, чем объем входящих вещей, которые вы проверяли. В противном случае затраты на отмену регулярных выражений аннулируют любые преимущества перфексов из-за небольшого количества регулярных выражений.

Редактировать 2:

Мой анализ времени выполнения O (n ^ 4) основывался на количестве состояний в большем DFA. Это, однако, игнорировало тот факт, что число состояний в DFA после преобразования из NFA может в итоге составить 2 ^ M, где M - это число состояний в NFA.

Это означает, что фактическая сложность заканчивается примерно так:

O (2 ^ 4М)

Что не является полиномом (что плохо).

В большинстве случаев число штатов NFA не будет приближаться к такому высокому уровню, поэтому на практике оно не должно быть слишком медленным.

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

Редактировать 3:

Можно преобразовать регулярное выражение непосредственно в DFA. Тем не менее, я не могу найти описание алгоритма в Интернете, каждый просто указывает на реализацию в книге драконов. К сожалению, сейчас у меня нет его копии (я знаю, это позорно). Так что сейчас я просто собираюсь продолжить подход regex => nfa => dfa. После того, как я найду библиотеку, возьму книгу и возьму из нее алгоритм, я посмотрю на изменение кода для использования прямого подхода.

Answer 2

То, что вы хотите сделать, сводится к тому, является ли AND двух регулярных выражений пустым (т.е. ничего не совпадает) или нет. Теоретически это возможно вычислить. AND двух обычных языков также является регулярным. И вопрос о том, является ли обычный язык пустым, решаем.

Однако это, вероятно, вам мало поможет, потому что вы, вероятно, не хотите имитировать конечные автоматы в вашей программе.

Answer 3

Зачем вам нужен белый и черный списки? Я думаю, что вы боретесь с логической проблемой здесь, запишите все это и подумайте над тем, что вы собираетесь.