Алгоритм, чтобы выбрать правильный RegEx среди многих как можно быстрее

Question

Веб-инфраструктура Django использует регулярные выражения для отправки входящих запросов.
Допустим, приложение огромно и содержит много регулярных выражений, скажем, сотни.

Для любого входящего запроса, как я могу определить, какие регулярные выражения сопоставляются как можно быстрее? Безумно перебирать перечисленные регулярные выражения одно за другим.

Answer 1

Один из вариантов - создать один детерминированный автомат, который может соответствовать всем регулярным выражениям параллельно.Один из способов сделать это будет следующим:

1. Преобразование каждого регулярного выражения в недетерминированный автомат с использованием одного из многих стандартных алгоритмов преобразования.
2. Введение нового начального состояния с помощью ε-переходовко всем начальным состояниям этих автоматов.Это эффективно создает один автомат, который запускает все автоматы регулярного выражения параллельно.Убедитесь, что каждое состояние принятия в NFA помечено по-разному, чтобы было ясно, какому регулярному выражению соответствует каждое состояние принятия.
3. Используя конструкцию подмножества, сократите этот NFA до DFA.Во время этого процесса, помечая состояние как принимающее, помните, какие из автоматов считали это состояние принимающим.
4. Создайте реализацию DFA на основе таблицы.

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

Answer 2

Объедините регулярные выражения в одно, объединяя их вместе с | и именованные группы: (? <1> regex1) | (? <2> regex2) | (? <3> regex3 ...

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

Answer 3

Если у вас есть контроль над приложением, почему бы не включить некоторые метаданные, указывающие тип используемого регулярного выражения?Вы можете использовать эти метаданные, чтобы затем выбрать правильный RegEx.