If you are familiar with regular expressions, don't make the mistake of thinking that all regular expression engines are the same. They fall into three general categories:

1. DFA. Fast, but does not allow back references (e.g. capture to $1). I understand that someone is writing a DFA engine that can do backreferences, but I'm too lazy to look up the reference right now :)
2. Traditional NFA. This is the regex engine that Perl uses and, amongst "those in the know", is often considered the best. It's fairly fast and allows backreferences.
3. POSIX NFA. Every once in a while, a standards body comes out with a poor standard. This is one of them. POSIX NFA usually tries for the "longest" match and, as such, can take an incredible amount of time with some regular expressions. Traditional NFA usually goes for the first match, thus allowing greater speed.

Between POSIX and traditional NFA engines, both can take long time verifying a failed match (sometimes longer than the than the length of time the universe has existed!), but traditional NFA tends to be much faster on successful matches.

Optimizing regular expressions, however, takes a lot of work and is far beyond the scope of this post. One thing you can do is read my shameless plug. However, the issues raised in that post aren't terribly relevant to what you're doing here.

The issue you are having is the following: when dealing with choices for single character, use a character class, but don't alternate!!! The following seem equivalent, but they're not:

$string =~ /[abc]/; # character class
$string =~ /a|b|c/; # alternation
[download]

The alternation problem is worsened when dealing with multiple characters.

$string =~ /bob/ || /alice/; # Good
$string =~ /(?:bob|alice)/;  # Bad
[download]

Regardless of all of the drivel here, it's important to take into consideration the actual data to be used. Testing against hypothetical data that really doesn't match what you are going to use is a poor test of the efficiency of your solution (this is just an aside. I have no idea if it's directly applicable to what you're doing). However, if you create sample data that closely mimics what you want, benchmarking your data is much more likely to produce relevant results.

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

The classic book to read is Mastering Regular Expressions. For threads that have touched on this see RE (tilly) 4: SAS log scanner and Numeric list to optimised regexp. And for an interesting discussion see also this. Unfortunately I don't think anyone will try to actually implement that in the near future, but you may find it interesting to read.

--
$you = new YOU;
honk() if $you->love(perl)

1: look for at, not found, look for bt, not found, look for ct ...
2: look for [abcdef], found, look for t, not found, look for ght
3: open grouping, look for [abcdef], not found, look for gh, close gro
+uping, found, look for t
4: open grouping, look for a, not found, look for b, not found, look f
+or c, ... look for gh, close grouping, found, look for t.
[download]

perldebug:

    Debugging regular expressions

       There are two ways to enable debugging output for regular
       expressions.
 
       If your perl is compiled with -DDEBUGGING, you may use the
       -Dr flag on the command line.
 
       Otherwise, one can use re 'debug', which has effects both
       at compile time, and at run time (and is not lexically
       scoped).

       [snip; read the details in the perldebug documentation.]
[download]

#!perl -c
use re 'debug';

/at/||/bt/||/ct/||/dt/||/et/||/ft/||/ght/;
/at|bt|ct|dt|et|ft|ght/;
/[abcdef]t|ght/;
/(?:[abcdef]|gh)t/;
/(?:a|b|c|d|e|f|gt)t/;

__END__
[download]

/at/||/bt/||/ct/||/dt/||/et/||/ft/||/ght/;

compiling RE `at'
size 3 first at 1
   1: EXACT <at>(3)
   3: END(0)
anchored `at' at 0 (checking anchored isall) minlen 2

compiling RE `bt'
size 3 first at 1
   1: EXACT <bt>(3)
   3: END(0)
anchored `bt' at 0 (checking anchored isall) minlen 2

compiling RE `ct'
size 3 first at 1
   1: EXACT <ct>(3)
   3: END(0)
anchored `ct' at 0 (checking anchored isall) minlen 2

compiling RE `dt'
size 3 first at 1
   1: EXACT <dt>(3)
   3: END(0)
anchored `dt' at 0 (checking anchored isall) minlen 2

compiling RE `et'
size 3 first at 1
   1: EXACT <et>(3)
   3: END(0)
anchored `et' at 0 (checking anchored isall) minlen 2

compiling RE `ft'
size 3 first at 1
   1: EXACT <ft>(3)
   3: END(0)
anchored `ft' at 0 (checking anchored isall) minlen 2

compiling RE `ght'
size 4 first at 1
   1: EXACT <ght>(4)
   4: END(0)
anchored `ght' at 0 (checking anchored isall) minlen 3


/at|bt|ct|dt|et|ft|ght/;

compiling RE `at|bt|ct|dt|et|ft|ght'
size 23
   1: BRANCH(4)
   2:   EXACT <at>(23)
   4: BRANCH(7)
   5:   EXACT <bt>(23)
   7: BRANCH(10)
   8:   EXACT <ct>(23)
  10: BRANCH(13)
  11:   EXACT <dt>(23)
  13: BRANCH(16)
  14:   EXACT <et>(23)
  16: BRANCH(19)
  17:   EXACT <ft>(23)
  19: BRANCH(23)
  20:   EXACT <ght>(23)
  23: END(0)
minlen 2


/[abcdef]t|ght/;

compiling RE `[abcdef]t|ght'
size 18
   1: BRANCH(14)
   2:   ANYOF(12)
  12:   EXACT <t>(18)
  14: BRANCH(18)
  15:   EXACT <ght>(18)
  18: END(0)
minlen 2


/(?:[abcdef]|gh)t/;

compiling RE `(?:[abcdef]|gh)t'
size 18
   1: BRANCH(12)
   2:   ANYOF(16)
  12: BRANCH(15)
  13:   EXACT <gh>(16)
  15: TAIL(16)
  16: EXACT <t>(18)
  18: END(0)
minlen 2


/(?:a|b|c|d|e|f|gt)t/;

compiling RE `(?:a|b|c|d|e|f|gt)t'
size 25
   1: BRANCH(4)
   2:   EXACT <a>(23)
   4: BRANCH(7)
   5:   EXACT <b>(23)
   7: BRANCH(10)
   8:   EXACT <c>(23)
  10: BRANCH(13)
  11:   EXACT <d>(23)
  13: BRANCH(16)
  14:   EXACT <e>(23)
  16: BRANCH(19)
  17:   EXACT <f>(23)
  19: BRANCH(22)
  20:   EXACT <gt>(23)
  22: TAIL(23)
  23: EXACT <t>(25)
  25: END(0)
minlen 2
[download]

That DEBUGGING option is pretty powerful, thanks for the tip. That is proof positive of what I have been suspecting, that Perl will "compile" the regexps, but it doesn't perform any optimizations in any intelligent sense. I was expecting a behaviour like "lex", which takes an "expression" and returns a fairly optimized state-machine which parses the defined tokens.

I am considering making an optimizer which will tweak a given regexp into something more efficient, such that you could give it something and it would polish it into something known to Benchmark faster. Of course, discovering all the tricks would be a bit of a chore, which is part of the challenge.

My idea is that this hypothetical function would take a regexp as input and return the optimized, but functionally equivalent, version of same:

        Input              Output
        ---------------------------------------
        'x|xy'             'xy?'
        'xx|xyx'           'xy?x'
        'a|abc'            'a(bc)?'
        'a|ab|abc'         'a(b(c)?)?'
        'a1|a2|a3'         'a[123]'
[download]

The intention is to add optimization techniques as they are discovered, plus an implementation strategy is devised. Certainly, not every input regexp will be understood to the degree that it can be optimized, and these will be left undisturbed.

Already, I am finding that the "optimial" solution is somewhat obscure in even simple cases:

        /that|this|thinks|thirst|three/

     -> /th(at|i(?:(?:nk)?s|rst)|ree/   ?
     -> /th(?:at|is|inks|irst|ree)/     ?
     -> /th(?:at|i(?:nk)?s|irst|ree)/   ?
[download]


Just food for thought.

Did you miss Re: Regexp Speed Concerns? I pointed there to two links here where there is code for automatic optimization of REs. The third link is to a general purpose optimization which would need to be done within Perl's engine, but which could lead to very good things.

As for why Perl doesn't do what lex does, the finite state engine that lex produces is a DFA, and so unable to handle backreferences or tell the difference between .* and .*?.

That is, it is hard to say whether two regexps are equivalent.

(is it in NP? someone can surely fill up on that)

Says fundflow:

if memory serves, regexp equivalence is not an easy question

You are absolutely right. Very little is known about regexes. What little is known indicates that the problems are all very hard.

(is it in NP? someone can surely fill up on that)

It is probably not in NP, but nobody knows for sure. Regex inequivalence ("Given two regexes, do they represent different languages?") is known to be PSPACE-complete. PSPACE-complete problems are at least has hard as NP-complete problems, but probably harder. If the regexes contain only the concatenation and | operators (no *'s), the problem is "only" NP-complete.

See (of course) Garey & Johnson Computers and Intractibility, p. 267.

Here's an interesting development.

A related problem which is PSPACE-complete is the problem: Given a regex R, is there any string that R will not match? Now, it's not known for sure that PSPACE-complete problems are intractible, although it's very likely. (And in particular, PSPACE-complete problems are at least as hard as NP-complete problems.) But here's the interesting part. Normally, in computer science, regex notations only include literal symbols, concatenation, |, *, and parenthese for grouping. If you extend thge regex notation to allow {2} as well, the problem becomes provably intractible and can be shown to require an exponential amount of space.