Как эффективно сопоставить входную строку с несколькими регулярными выражениями одновременно?

Question

Как можно эффективно сопоставить одну входную строку с любым количеством регулярных выражений?

Один сценарий, в котором это может быть полезно, - это веб-службы REST.Давайте предположим, что я разработал несколько шаблонов URL для открытого интерфейса веб-службы REST:

• /user/with-id/{userId}
• /user/with-id/{userId}/profile
• /user/with-id/{userId}/preferences
• /users
• /users/who-signed-up-on/{date}
• /users/who-signed-up-between/{fromDate}/and/{toDate}
• …

где {…} являются именованными заполнителями (например, группы захвата регулярных выражений).

_{Примечание. Этот вопрос не касаетсяхорошо ли разработан вышеупомянутый интерфейс REST или нет.(Возможно, это не так, но это не должно иметь значения в контексте этого вопроса.)}

Можно предположить, что заполнители обычно не появляются в самом началешаблона (но они могли).Можно также с уверенностью предположить, что любая строка не может соответствовать более чем одному шаблону.

Теперь веб-служба получает запрос.Конечно, можно последовательно сопоставить запрашиваемый URI с одним шаблоном URL, затем со следующим и т. Д .;но это, вероятно, не будет хорошо масштабироваться для большего количества шаблонов, которые должны быть проверены.

Есть ли эффективные алгоритмы для этого?

Входные данные:

• Строка ввода
• Набор «взаимоисключающих» регулярных выражений (т. Е. Ни одна строка ввода не может соответствовать более чем одному выражению)

Вывод:

• Регулярное выражение (если есть), с которым сопоставляется входная строка.

Answer 1

Алгоритм Aho-Corasick - это очень быстрый алгоритм, позволяющий сопоставить входную строку с набором шаблонов (фактически ключевых слов), которые предварительно обработаны и организованы в виде дерева, для ускорения сопоставления.

Существуют варианты алгоритма для поддержки шаблонов регулярных выражений (т. Е. http://code.google.com/p/esmre/ только для того, чтобы назвать один), которые, возможно, стоит посмотреть.

Или, вы можете разделить URL на куски,упорядочите их в дереве, затем разделите URL-адрес, чтобы соответствовать и обходите дерево по одному куску за раз.{UserId} может считаться подстановочным знаком или соответствовать некоторому определенному формату (то есть быть целым).

Когда вы достигаете листа, вы знаете, какой URL вы выбрали

Answer 2

Стандартным решением для сопоставления нескольких регулярных выражений с входным потоком является генератор лексеров , такой как Flex (их много, обычно несколько для каждого языка программирования).

Эти инструменты принимают набор регулярных выражений, связанных с «токенами» (считают токены просто именами для всего, что соответствует регулярному выражению) и генерируют эффективные автоматы с конечным состоянием, чтобы соответствовать всем регулярным выражениям одновременно.Это линейное время с очень небольшой константой размера входного потока;Трудно просить "быстрее", чем это.Вы передаете ему поток символов, и он выдает имя токена регулярного выражения, которое соответствует «best» (это обрабатывает случай, когда два регулярных выражения могут совпадать с одной и той же строкой; см. Определение этого в генераторе лексеров), и продвигает потокпо тому, что было признано.Таким образом, вы можете применять его снова и снова, чтобы соответствовать входному потоку для серии токенов.

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

Answer 3

Если в структуре URL есть иерархия, это следует использовать для максимизации производительности. Только URL-адрес, начинающийся с / user /, может соответствовать любому из первых трех и т. Д.

Я предлагаю хранить иерархию для сопоставления в дереве, соответствующем иерархии URL, где каждый узел соответствует уровню в иерархии. Чтобы сопоставить URL, проверьте URL со всеми корнями дерева, где находятся только узлы с регулярными выражениями для «пользователя» и «пользователя». Соответствующие URL-адреса проверяются на дочерних узлах этих узлов, пока в листовом узле не будет найдено совпадение. Успешное совпадение может быть возвращено в виде списка узлов от корня до листа. Именованные группы со значениями свойств, такими как {user-id}, могут быть получены из узлов успешного сопоставления.

Answer 4

Сначала я подумал, что не вижу хорошей оптимизации для этого процесса.

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

Что я вам скажу, это:

Предположим, у вас есть 20 возможных URL, которые начинаются с user:

/user/with-id/X
/user/with-id/X/preferences # instead of preferences, you could have another 10 possibilities like /friends, /history, etc

Тогда у вас также есть 20 возможных URL, начинающихся с users:

/users/who-signed-up-on
/users/who-signed-up-on-between     #others: /registered-for, /i-might-like, etc

И этот список продолжается для /products, /companies и т. Д. Вместо пользователей.

В этом случае вы можете использовать «многоуровневое» сопоставление .

Сначала сопоставьте начало строки. Вы подходите для /products, /companies, /users, по одному за раз и игнорируя остальную часть строки. Таким образом, вам не нужно проверять все 100 возможностей.

После того, как вы узнаете, что URL-адрес начинается с /users, вы можете сопоставить только возможные URL-адреса, начинающиеся с пользователей.

Таким образом, вы уменьшите количество ненужных совпадений. Вы не сопоставите строку для всех возможностей /procucts.

Answer 5

Используйте именованные выражения и оператор ИЛИ, например "(?P<re1>...)|(?P<re2>...)|...".