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

Question

КОНТЕКСТ:

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

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

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

СТРАТЕГИЯ:

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

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

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

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

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

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

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

Answer 1

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