У меня есть большая коллекция регулярных выражений, которая при сопоставлении вызывает конкретный обработчик http. Некоторые из старых регулярных выражений недоступны (например, a.c* ⊃ abc*), и я бы хотел их обрезать.
Есть ли библиотека, которая задала два регулярных выражения, скажет мне, является ли второе подмножество первого?
Я не был уверен, что это было разрешимо сначала (это пахло, как проблема с остановкой другим именем). Но получается он разрешимый.
Попытка найти сложность этой проблемы привела меня к этой статье.
Формальное определение проблемы можно найти внутри: это обычно называется проблемой включения
Задача включения для R, состоит в том, чтобы проверить два заданных выражения r, r '∈ R, будь то r ⊆ r '.
В этой статье есть отличная информация (резюме: все, кроме простейших выражений, довольно сложны), однако поиск информации о проблеме включения приводит непосредственно к fooobar.com/questions/165382/.... В этом ответе уже была ссылка на документ, описывающий алгоритм пассивного полиномиального времени, который должен охватывать множество распространенных случаев.
Если регулярные выражения используют "расширенные функции" типичных процедурных совпадений (например, в Perl, Java, Python, Ruby и т.д.), которые позволяют принимать языки, которые не являются регулярными, тогда вам не повезло. Проблема вообще неразрешима. Например. проблема того, распознает ли один пусковой автомат один и тот же контекстный свободный (CF) язык, поскольку другой является неразрешимым. Расширенные регулярные выражения могут описывать языки CF.
С другой стороны, если регулярные выражения являются "истинными" в теоретическом смысле, состоящими только из конкатенации, чередования и звезды Клейна над строками с конечным алфавитом, плюс обычный синтаксический сахар на этих (классы символов +,? и т.д.), тогда существует простой полиномиальный алгоритм времени.
Я не могу предоставить вам библиотеки, но это:
For each pair of regexes r and s for languages L(r) and L(s)
Find the corresponding Deterministic Finite Automata M(r) and M(s)
Compute the cross-product machine M(r x s) and assign accepting states
so that it computes L(r) - L(s)
Use a DFS or BFS of the the M(r x s) transition table to see if any
accepting state can be reached from the start state
If no, you can eliminate s because L(s) is a subset of L(r).
Reassign accepting states so that M(r x s) computes L(s) - L(r)
Repeat the steps above to see if it possible to eliminate r
Преобразование регулярного выражения в DFA обычно использует конструкцию Томпсона для получения недетерминированного автомата. Он преобразуется в DFA с использованием структуры подмножества. Перекрестная машина - еще один стандартный алгоритм.
Все это было разработано в 1960 году и в настоящее время является частью любого курса теории теории вычислительной техники. Золотой стандарт для этой темы Хопкрофт и Ульман, Теория автоматов.
В разделе математики есть ответ: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another.
Основная идея:
Было бы полезно, если бы вы просто вычислили новый переход и результирующие состояния, опуская все не достижимые состояния с самого начала.
Я нашел библиотеку регулярных выражений python, которая предоставляет заданные операции.
http://github.com/ferno/greenery
В доказательстве говорится Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {}. Я могу реализовать это с помощью библиотеки python:
import sys
from greenery.lego import parse
subregex = parse(sys.argv[1])
supregex = parse(sys.argv[2])
s = subregex&(supregex.everythingbut())
if s.empty():
print("%s is a subset of %s"%(subregex,supregex))
else:
print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s)
примеры:
subset.py abcd.* ab.*
abcd.* is a subset of ab.*
subset.py a[bcd]f* a[cde]f*
a[bcd]f* is not a subset of a[cde]f*, it also matches abf*
Библиотека не может быть надежной, поскольку, как упоминалось в других ответах, вам нужно использовать минимальный DFA, чтобы это работало. Я не уверен, что библиотека ferno делает (или может сделать) эту гарантию.
В стороне: игра с библиотекой для вычисления обратных или упрощенных регулярных выражений - это очень весело. a(b|.).* упрощается до a.+. Это довольно мало.
Обратное к abf* составляет ([^a]|a([^b]|bf*[^f])).*|a?. Постарайтесь придумать это самостоятельно!