Как найти “минимальный охватывающий набор” для набора регулярных выражений?

Question

КОНТЕКСТ:

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

Некоторые из RES имеют отношение упорядочивания - например, если я знаю, что строка $t соответствует /windows /i, то я также знаю, что $ t соответствует /windows.* 2000 /i.Таким образом, при тестировании $ t против REs в моей коллекции я могу пропустить тестирование / windows / i, если я уже протестировал $ t против / windows.* 2000 / i и нашел совпадение (хотя, если / windows.* 2000 / i делает нет тогда, конечно, я не могу пропустите тест против /windows/i).

Обратите внимание, что ни один из RES в моей коллекции не является полностью эквивалентным (для любой пары RES существует по крайней мере одна текстовая строка, которая соответствует одному и выполняет нет совпадают с другими).

СТРАТЕГИИ:

Я хочу построить ориентированный граф G с узлом для каждого RE в моей коллекции и направленным ребром для каждой пары REs с отношением упорядочения (A -> B означает "совпадение с A подразумевает совпадение с B") и найти "минимальный охватывающий набор" узлов для графика (минимальный набор узлов S такой, что каждый узел в G лежит на направленном пути, который берет начало в S).

САМАЯ ЛЕГКАЯ ЧАСТЬ:

Существует множество свободно доступных алгоритмов для работы с ориентированными ациклическими графами.Итак, как только график G будет построен для моей коллекции REs (которые, будучи отличными, должны гарантировать, что G является ациклическим), я не ожидаю, что у меня возникнут большие трудности с поиском подходящего алгоритма для нахождения минимального охватывающего множества для G.

ГДЕ МНЕ НУЖНА ПОМОЩЬ:

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

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

Кто-нибудь знает о существующей реализации (для сравнения REs), которая является достаточно эффективной, свободно доступной и (в идеале) реализована либо на одном из популярных языков сценариев, либо на C / C ++?

Answer 1

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