From: cppasm@...
Date: 2007-03-05T15:55:06+09:00
Subject: Re: a regular expression problem

On 3埖5晩, 和怜2扮27蛍, "Bill Kelly" <b...@cts.com> wrote:
> From: <cpp...@gmail.com>
>
> > hi,it seems that there's some problem with the regeular expression
> > processing in ruby,when I ran the code below, it happened that it loop
> > for ever and would not get out.
> > $value = "20053301831294544645645645634556354"
> > if $value =~ /\b(?:\d{1,3}[,\.]?)+\d{3}.{0,20}\b(?:pics|pictures|
> > images|photos|movies)/i
> > puts "hit"
> > else
> > puts "miss"
> > end
> > any idea? Thank u!
>
> You can try this in irb, like:
>
> >> value = "20053301831294544645645645634556354"
>
> => "20053301831294544645645645634556354">> value =~ /\b(?:\d{1,3}[,\.]?)+\d{3}.{0,20}\b(?:pics|pictures|images|photos|movies)/i
>
> (takes a long time)
>
> If you shorten value a bit:
>
> >> value = "2005330183129454464564"
>
> => "2005330183129454464564">> value =~ /\b(?:\d{1,3}[,\.]?)+\d{3}.{0,20}\b(?:pics|pictures|images|photos|movies)/i
>
> => nil
>
> You'll see that it takes a second or two, then finishes.
>
> The problem is, the regexp involves nested variable-length matches,
> so when no match is found, the engine keeps backtracking and trying
> to find other possible matches, across all combinations of
> (?:\d{1,3}[,\.]?)+\d{3}.{0,20}
> ..of which there are exponential possibilities within a string of
> digits...
>
> Hopefully, it may be possible to rewrite your regexp to fail more
> quickly on bad data.If you could tell us more about the exact
> specification of the data you're trying to match, people might
> be able to help further.
>
> Regards,
>
> Bill

Thank you so much!
I'm trying to rewrite SpamAssassin in ruby just for fun :-). The
regexp mentioned is just a rule in SpamAssassin's rule files.It's used
to match against every line of a mail message.In fact I tested using
the value and regexp mentioned above in Java(JDK, oro and regexp of
Apache),perl,python and ruby.It finished very soon in perl and
python,while the same thing happened in Java(whichever library I
use,jdk,oro or regexp) as in ruby,so I guess maybe the underlying
matchings mechanism between them are quite different?