КОНТЕКСТ:
У меня небольшая (в настоящее время меньше 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 ++?