<p>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:
<a href="https://www.hyperscan.io/2015/10/20/match-regular-expressions" rel="nofollow noreferrer">https://www.hyperscan.io/2015/10/20/match-regular-expressions</a></p>
<p>Apparently, they didn't find a fast algorithm (in the worst case) for this problem: &quot;We have not found a single, elegant automata approach that handles arbitrary regular expressions in arbitrary number&quot;. However, they used a lot of optimization which works well enough in practice.</p>
<p>I also believe that in the worst case, the given regular expressions can be so complex that no better solution exists.</p>

CC BY-SA 4.0
2020-08-02T04:35:14.040Z
2020-08-02T04:35:14.040Z
Mohemnist
<p>The best strategy would be to simultaneously check the string against <strong>all</strong> DFA's. This is achieved by adding a new start vertex <code>v0</code> and adding <code>epsilon</code> edges to the start vertices of all DFA's. Now you have an NFA. You can follow standard algorithms of determinizing it. This is <strong>exactly how automated lexer generators (like flex for example) work</strong>. Only instead of the input DFA's they have multiple regular expressions.</p>

CC BY-SA 4.0
2020-08-06T17:35:44.860Z
down-voter please explain
OrenIshShalom
CC BY-SA 4.0
2020-08-07T10:08:31.803Z
Your solution does NOT provide a better running time (in comparison to $O(kmn)$). (I'm not the down-voter, by the way.)
Mohemnist
CC BY-SA 4.0
2020-08-06T07:50:51.593Z
2020-08-06T07:50:51.593Z
OrenIshShalom
<p>There are several algorithms to match a (simple) string against a regular expression <a href="https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times" rel="nofollow noreferrer">(see here)</a>.
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?</p>
<p>For example, if we have <span class="math-container">$k$</span> regexes, each with a length of <span class="math-container">$m$</span> and a string of length <span class="math-container">$n$</span>, using the <span class="math-container">$O(mn)$</span> algorithm to match a string with a regex <span class="math-container">$k$</span> times gives us a running time of <span class="math-container">$O(kmn)$</span>. Can we do better than this?</p>
<p>If you have an answer which requires some assumptions, please explicitly tell them.</p>

CC BY-SA 4.0
2020-07-28T15:50:12.663Z
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.
ebonnal
CC BY-SA 4.0
2020-07-28T16:22:59.217Z
Intersection of regular languages is still regular, why don't you use the corresponding minimal automaton?
holf
CC BY-SA 4.0
2020-07-28T20:48:35.687Z
@holf Constructing the minimal intersection of $k$ DFA's requires $O(\exp(k))$ states in the worst case.
orlp
CC BY-SA 4.0
2020-08-06T17:36:31.513Z
@orlp it is not intersection - he's asking about the union
OrenIshShalom
<ds.algorithms><regular-expressions><string-matching><string-search><search-engines>
Match a string agains a set of regexes
Mohemnist
# Match a string agains a set of regexes

(Asked by: username_0 on 2020-07-28)

There are several algorithms to match a (simple) string against a regular expression [(see here)](https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times).
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.

**Tags:** ds.algorithms, regular-expressions, string-matching, string-search, search-engines
> **Comments:**
> **username_1**: 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.  
> **username_2**: Intersection of regular languages is still regular, why don't you use the corresponding minimal automaton?  
> **username_3**: @holf Constructing the minimal intersection of $k$ DFA's requires $O(\exp(k))$ states in the worst case.  
> **username_4**: @orlp it is not intersection - he's asking about the union  

---

## 2 answers

### Answer by username_0 on 2020-08-02. Score: 1

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.


---

### Answer by username_4 on 2020-08-06. Score: -1

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.

> **Comments:**
> **username_4**: down-voter please explain  
> **username_0**: Your solution does NOT provide a better running time (in comparison to $O(kmn)$). (I'm not the down-voter, by the way.)  

---

