Algorithm for multiple extended string matching

Question

I need to implement an algorithm for multiple extended string matching in text. Algorithms to match regular expression would be perhaps too slow.

Extended means the presence of wildcards (any number of characters instead of a star), for example:

abc*def //matches abcdef, abcpppppdef etc.

Multiple means that the search is going on simultaneously for multiple string patterns (not a separate search for each pattern), for example:

abc*def
abc
whatever
some*string

QUESTION:

What is the fast algorithm that can do multiple extended string matching?

Preferably, optimized for SIMD instructions and multicore implementation. Open source implementation (C/C++/Python) would be great as well. I'm interested in 10 Gbps+ performance on a single core of a modern CPU.

Thank you

Answer 1

I would recommend regexp pattern matching. I know that usual implementations are slow but you have to study Thompson's construction algorithm for nondeterministic automaton. See the wikipedia dedicated article. However here the wikipedia fails to present this treasure properly. I would strongly recommend to study carefuly this blog article: Regular expressions can be simple and fast. For implementations you have pointers in the given article (for example awk and grep uses this implementation).

Answer 2

Do you change the patterns often? If not, then you can use Aho-Corasick method, whose idea is, first, to build a finite automaton based on your patterns and, then, to make a single pass over the text with this automaton to find matches (if the automaton visits a "matching" state, then there is a match). The complexity of the automata building should be linear in the length of the patterns (# of patters * max pattern length), and the matching phase should be linear in the size of the text you search in.