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

Question

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

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

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

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

This is a test string

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

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

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

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

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

Большое спасибо заранее за любые ваши предложения!

Answer 1

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

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 2

Если ваши выражения достаточно просты (шаблоны с подстановочными знаками), И ваш набор выражений предопределен, то есть изменяется только вход для сопоставления, ТОГДА вы можете создать конечный автомат , который соответствует объединению ваших выражений, т. е. выражение "(r1) | (r2) | ...".

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

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

Answer 3

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

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