Эффективно искать коллекцию регулярных выражений

Question

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

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

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

Answer 1

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

См: https://en.wikipedia.org/wiki/Deterministic_finite_automaton

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

Это не так просто, но есть инструменты вокруг. Если вы работаете на Java, у меня есть проект с открытым исходным кодом, который вы могли бы использовать: http://mtimmerm.github.io/dfalex/. Чтобы ответить на ваши другие вопросы, вы можете получить набор всех соответствующих регулярных выражений из этого, если хотите.

Если вы заинтересованы в том, чтобы сделать это самостоятельно, процесс обычно состоит из конвертирования регулярных выражений в NFA (https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton) с использованием конструкции Томпсона (https://en.wikipedia.org/wiki/Thompson%27s_construction), а затем преобразования НКА в ДКА, используя конструкцию подмножество (https://en.wikipedia.org/wiki/Powerset_construction), а затем обычно сводит к минимуму DFA с помощью алгоритма Хопкрофта (https://en.wikipedia.org/wiki/DFA_minimization)

Существует множество возможностей для оптимизации и утонченности.

Удачи!

P.S. Я должен отметить пару вещей: 1) Вы не можете вообще делать DFA из регулярных выражений, у которых есть обратные ссылки. 2) Теоретически возможно, чтобы DFA была экспоненциально большой. Это почти никогда не происходит случайно, но если ваши регулярные выражения вводятся потенциально злонамеренными людьми, тогда вам придется что-то сделать с этой возможностью.

Answer 2

PHP-пример:

<?php 
$regex_array = array(
    "/regex_1/" => 0, 
    "/regex_2/" => 0, 
    "/regex_3/" => 0 // and so on and so forth 
); 

$strings_array = array(
    "input_string_1", 
    "input_string_2", 
    "input_string_3" // and so on and so forth 
); 

foreach ($regex_array as $key => $value) 
    foreach ($strings_array as $current_string) 
    if (preg_match($key, $current_string)) 
     $regex_array[$key]++; 
?> 

Here «s код Runnig.

Answer 3

Я не буду отмечать свой ответ в качестве ответа, если никто не ударит его через несколько дней.

---

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

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

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

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

Это аналогично, но если я сделаю что-то подобное, я думаю, что я запустил нить для каждого регулярного выражения (или каждой небольшой группы регулярных выражений) в RegexPile. Я думаю, что любое заданное регулярное выражение может принимать неограниченное количество, потому что регулярные выражения могут это сделать. Затем, если какие-либо потоки занимают слишком много времени, я могу выйти из строя на основе таймаута и преждевременно прекратить все потоки. Я также думаю, что большинство из них потерпит неудачу по первому символу, означая, что большинство этих потоков просто исчезнут после проверки первого символа. С дешевыми копиями на темы, которые большинство систем предоставляют в наши дни, этот поток не должен быть достаточно дешевым, так как многие потоки будут закрыты, прежде чем я закончу их размножение, и только те, кто довольно похож, будут задерживаться в любое время. Затем я делаю двоичный код в другом потоке для SortedStringArray.