Как я могу определить, какие регулярные выражения из списка могут перекрываться

Question

У меня есть таблица регулярных выражений в таблице MySQL, с которой я сопоставляю текст.

Есть ли способ, используя MySQL или любой другой язык (предпочтительно Perl), который я могу взять из этого спискавыражения и определить, какие из них могут совпадать. Это должно быть независимо от того, какой текст может быть предоставлен выражениям.

Все выражения имеют привязки.

Вот пример того, что я пытаюсь получить:

Выражения:

^a$
^b$
^ab
^b.*c
^batch
^catch

Результат: '^b.*c' and '^batch' MAY overlap

Мысли?

Спасибо, Скотт

Дальнейшее объяснение:

Iиметь список созданных пользователем регулярных выражений и импортированный список строк, которые должны быть сопоставлены с регулярными выражениями. В этом случае строки являются «чистыми» данными (т.е. они не созданы пользователем, а импортированы из другого источника - они не должны изменяться).

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

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

Answer 1

Я буду ставить на полную RE. Даже ограничение BRE и / или MySQL-pre-8.0 будет проблематичным. Вот некоторые мысли.

• Если конец привязан и нет + или *, рассчитайте длину. Фиксированная длина может использоваться как дискриминатор. Кроме того, его можно использовать для тонирования «грубой силы», возможно, на порядок.
• Все, за чем следует + или *, для простоты превращается в .*. (Правило «возможно столкновение»).
• Любой RE с явными символами (включая те, за которыми следует +) становится дискриминатором в некоторых ситуациях. Например, ^a.*b$ против ^a.*c$.
• Для тех, кто закреплен на конце, поменяйте схему и проверьте ее таким образом. (Я не знаю, насколько сложно изменить направление движения.)
• Если вы можете сказать, что определенный символ должен находиться в любой позиции, то используйте его как дискриминатор: ^a.b.*c$ - a в позе 1;b в поз. 3;c в конце. Возможно, это можно распространить на классы персонажей: ^\w может соответствовать, но ^\d и ^a.*\d$ не могут.