4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I suggest that we close this question on this site. It is a duplicate, cross-posted on Cross Validated and migrated to StackOverflow, where it already has an accepted answer: stackoverflow.com/q/28962097/2872891. Anyone, wanting to add their answer, can do so on SO. $\endgroup$ – Aleksandr Blekh Mar 15 '15 at 2:16
2
+50
$\begingroup$

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).

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ thank you for the reply. Can you recommend any good Aho-Corasick implementation/flavor that can handle extended matching features (* and ? ) and preferably SIMD instructions? Naive implementations I tried were quite slow and didn't have extended matching features. $\endgroup$ – Konstantin Mar 18 '15 at 7:10
  • $\begingroup$ Patterns are to be changed moderately often, so I could recompile the automaton once it happens. $\endgroup$ – Konstantin Mar 18 '15 at 7:28

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.