Алгоритм для соответствия списку регулярных выражений

Question

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

1. Пусть У меня есть строка, и список N регулярных выражений (на самом деле они являются подстановочные шаблоны, представляющие собой подмножество полной функциональности регулярных выражений). Я хочу знать, соответствует ли строка хотя бы одному из регулярных выражений в списке. Есть ли структура данных, которая может позволить мне сопоставить строку со списком регулярных выражений в сублинейном (предположительно логарифмическом) времени?

2. Это расширение предыдущей проблемы. Предположим, что у меня такая же ситуация: строка и список из N регулярных выражений, только теперь каждое из регулярных выражений сопряжено со смещением внутри строки, в которой должно начинаться совпадение (или, если хотите, каждое регулярное выражение должен соответствовать подстроке заданной строки, начинающейся с заданного смещения).

Для примера предположит, что у меня был строка:

This is a test string

и регулярные выражения модель и смещение:

(a) his.* at offset 0 
(b) his.* at offset 1

Алгоритм должны вернуть истинные. Хотя regex (a) не соответствует строке, начинающейся со смещения 0, regex (b) действительно соответствует подстроке, начинающейся со смещения 1 («его тестовая строка»).

Есть ли структура данных, которая может позволить мне решить эту проблему в сублинейное время?

Одним из полезных сведений является то, что часто многие смещения в списке регулярных выражений являются одинаковыми (например, мы часто используем подстроку со смещением X много раз). Это может быть полезно для решения проблемы проблемы № 1 выше.

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

Answer 1

(1) Объединить все регулярные выражения как большой союз: (r1)|(r2)|(r3)|...

(2) Для каждого регулярного выражения с офсетных п добавить п точки начала плюс якорь. Таким образом, his.* со смещением 6 становится ^......his.*. Или, если ваш синтаксис regex поддерживает его, ^.{6}his.*.

Answer 2

Предполагаю, что у вас действительно есть сила регулярных выражений.

1. Для того, чтобы определить, является ли строка соответствует одной из выражений e_1, e_2, ..., e_n, просто совпадают с выражением e_1 + e_2 + ... + e_n (иногда оператор + записывается в виде |).

2. Указанные пары (e_1, o_1), ..., (e_n, o_n) выражение смещения и строка, вы можете проверить, есть ли i такое, что строка соответствует выражением e_i по смещению o_i путем сопоставления с выражением .{o_1}e_1 + ... + .{o_n}e_n.

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

Answer 3

Если ваши выражения достаточно просты (шаблоны подстановочных знаков), И ваш набор выражений предопределен, т. Е. Изменяется только вход, который должен быть согласован, THEN вы можете построить finite state machine, который соответствует объединению ваших выражений, т. Е. выражение "(r1) | (r2) | ...".

Построение этой машины занимает время и пространство не менее O (N) (но я думаю, что это не экспоненциальный, что является наихудшим случаем для регулярных выражений вообще). Соответствие тогда 0 (длина (вход)), независимо от N.

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