3
$\begingroup$

There are several algorithms to match a (simple) string against a regular expression (see here). But if we have a lot of regexes, can we find one of them that matches the given string faster than checking the string with all of the regexes, one by one?

For example, if we have $k$ regexes, each with a length of $m$ and a string of length $n$, using the $O(mn)$ algorithm to match a string with a regex $k$ times gives us a running time of $O(kmn)$. Can we do better than this?

If you have an answer which requires some assumptions, please explicitly tell them.

$\endgroup$
4
  • 1
    $\begingroup$ If the experience consists of finding if a string do match against each of the $k$ regexps and is rejected if it does not match against at least one of the $k$ regexps, then I have the intuition that one can reduce the variance of the computation durations of the experience by making the $k$ automatons process the string in a parallel way instead of sequencially one automaton after another. I follow this question and I'm quite interested in an answer too. $\endgroup$ Jul 28 '20 at 15:50
  • $\begingroup$ Intersection of regular languages is still regular, why don't you use the corresponding minimal automaton? $\endgroup$
    – holf
    Jul 28 '20 at 16:22
  • 1
    $\begingroup$ @holf Constructing the minimal intersection of $k$ DFA's requires $O(\exp(k))$ states in the worst case. $\endgroup$
    – orlp
    Jul 28 '20 at 20:48
  • $\begingroup$ @orlp it is not intersection - he's asking about the union $\endgroup$ Aug 6 '20 at 17:36
1
$\begingroup$

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here: https://www.hyperscan.io/2015/10/20/match-regular-expressions

Apparently, they didn't find a fast algorithm (in the worst case) for this problem: "We have not found a single, elegant automata approach that handles arbitrary regular expressions in arbitrary number". However, they used a lot of optimization which works well enough in practice.

I also believe that in the worst case, the given regular expressions can be so complex that no better solution exists.

$\endgroup$
-1
$\begingroup$

The best strategy would be to simultaneously check the string against all DFA's. This is achieved by adding a new start vertex v0 and adding epsilon edges to the start vertices of all DFA's. Now you have an NFA. You can follow standard algorithms of determinizing it. This is exactly how automated lexer generators (like flex for example) work. Only instead of the input DFA's they have multiple regular expressions.

$\endgroup$
2
  • $\begingroup$ down-voter please explain $\endgroup$ Aug 6 '20 at 17:35
  • 1
    $\begingroup$ Your solution does NOT provide a better running time (in comparison to $O(kmn)$). (I'm not the down-voter, by the way.) $\endgroup$
    – Mohemnist
    Aug 7 '20 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.