База данных или структура, подходящая для сопоставления строк с шаблонами регулярных выражений

Question

У меня есть несколько шаблонов регулярных выражений. Когда вводится строка, я должен найти все шаблоны, соответствующие этой строке. Обычно это операция O (n) :

SELECT regex FROM regexes WHERE 'string' RLIKE regex

Какой самый быстрый способ сделать это? Существуют ли структуры баз данных или системы хранения, оптимизированные для выполнения такой операции?

Answer 1

Короткий ответ: «Нет». В настоящее время нет структуры индекса, доступной на любой платформе СУБД, которая будет индексировать частичные совпадения регулярного выражения, подобного этому.

Длинный ответ заключается в том, что ведущая константа в подстановочном совпадении (например, 'foo_') может использоваться в качестве префикса для индексных совпадений. Многие платформы СУБД оптимизируют это и используют индекс (если доступен) для разрешения префикса. Однако это не так умно, как полное регулярное выражение, и индексирование можно использовать только при наличии постоянного префикса.

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

Rete работает путем вычисления частичных совпадений и только представления правил, которые могут быть достигнуты из этого частичного совпадения, поэтому он более эффективен, чем O (n) (больше похоже на O (log n), но я не уверен в точном времени сложность) для сопоставления n правил с фактом.

Answer 2

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

• вам нужно проверить только несколько самых общих регулярных выражений.

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

Например, если ваши входные строки могут быть сколь угодно сложными и у вас есть тысячи регулярных выражений, вы можете организовать их по категориям, например:

• категория \d+, которая будет тестировать шаблоны номеров (SSN, номера телефонов и т. Д.)

• категория <.*?>, которая будет проверять наличие тегов HTML

• категория \w+@\w+, которая может проверять наличие адресов электронной почты

и т.д.

Если какой-либо корневой шаблон не совпадает, тогда вам не нужно тестировать целые диапазоны шаблонов, которые в любом случае потерпят неудачу.

Не знаю, будет ли это соответствовать вашему домену, но это возможная оптимизация.