What's the best way to apply many Perl regular expression tests?

Question

I have a Perl module that matches text against a list of hundreds of regexes; currently I am just or'ing them:

if (
  /?:re1/ or
  ...
  /re200$/
) { return "blah"; }

Is there a better/faster/less resource-intensive way to do this? Perhaps a useful module exists, or I should store them in a hash, etc.

Answer 1

You could keep your regexes in a separate file, one per line. It wouldn't run any faster but the code would be a lot cleaner.

Read them in with something like

my @patterns;
while (<>) {
    push @patterns, qr/$_/;
}

To improve performance my only advice is to use a real parser. ANTLR's perl target appears to be defunct but I had no trouble using a parser generated in Java via perl's Inline::Java.

Edit: did think of one other minor thing: Order your regexes from most-commonly-matched to least-commonly matched. Could give you a small constant-factor improvement.

Answer 2

If your regexps aren't changing then you should use the /o suffix which will require they be compiled only once. It'll greatly help speed.

Also, order them by "most common reject first" or "the one with the least wild cards first" so that the ones later, more cpu-intensive ones, will be executed the least frequently.

It's certainly possible to read them in from a file, but the right way to do that for speed is to read them in and then construct a subroutine inside a text string and then eval the text string to return an anonymous subroutine to call. This gives you the speed advantage of a hard-coded list of regexps with the flexibility of a variable list of regexps.

Answer 3

Take a look at Regexp::Assemble.

This is from the description:

Regexp::Assemble takes an arbitrary number of regular expressions and assembles them into a single regular expression (or RE) that matches all that the individual REs match.

As a result, instead of having a large list of expressions to loop over, a target string only needs to be tested against one expression. This is interesting when you have several thousand patterns to deal with. Serious effort is made to produce the smallest pattern possible.

It is also possible to track the original patterns, so that you can determine which, among the source patterns that form the assembled pattern, was the one that caused the match to occur.

I used it for some projects and it was pretty amazing.

Answer 4

From perlfaq6's answer to How do I efficiently match many regular expressions at once?

---

How do I efficiently match many regular expressions at once?

(contributed by brian d foy)

If you have Perl 5.10 or later, this is almost trivial. You just smart match against an array of regular expression objects:

my @patterns = ( qr/Fr.d/, qr/B.rn.y/, qr/W.lm./ );

if( $string ~~ @patterns ) {
    ...
    };

The smart match stops when it finds a match, so it doesn't have to try every expression.

Earlier than Perl 5.10, you have a bit of work to do. You want to avoid compiling a regular expression every time you want to match it. In this example, perl must recompile the regular expression for every iteration of the foreach loop since it has no way to know what $pattern will be:

my @patterns = qw( foo bar baz );

LINE: while( <DATA> ) {
    foreach $pattern ( @patterns ) {
        if( /\b$pattern\b/i ) {
            print;
            next LINE;
            }
        }
    }

The qr// operator showed up in perl 5.005. It compiles a regular expression, but doesn't apply it. When you use the pre-compiled version of the regex, perl does less work. In this example, I inserted a map to turn each pattern into its pre-compiled form. The rest of the script is the same, but faster:

my @patterns = map { qr/\b$_\b/i } qw( foo bar baz );

LINE: while( <> ) {
    foreach $pattern ( @patterns ) {
        if( /$pattern/ )
            {
            print;
            next LINE;
            }
        }
    }

In some cases, you may be able to make several patterns into a single regular expression. Beware of situations that require backtracking though.

my $regex = join '|', qw( foo bar baz );

LINE: while( <> ) {
    print if /\b(?:$regex)\b/i;
    }

For more details on regular expression efficiency, see Mastering Regular Expressions by Jeffrey Freidl. He explains how regular expressions engine work and why some patterns are surprisingly inefficient. Once you understand how perl applies regular expressions, you can tune them for individual situations.