# A regular expression problem

**URL:** <https://www.ruby-forum.com/t/a-regular-expression-problem/87685>\
**Category:** Ruby\
**Created:** [March 5, 2007, 5:10am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685 "2007-03-05T05:10:29Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 5:10am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/1 "2007-03-05T05:10:29Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 7:28am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/2 "2007-03-05T07:28:38Z")

</div>

From: [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)

> 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

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 7:55am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/3 "2007-03-05T07:55:40Z")

</div>

On 3ÔÂ5ÈÕ, ÏÂÎç2ʱ27·Ö, “Bill K.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > puts “miss”
> 
> The problem is, the regexp involves nested variable-length matches,
> 
> 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?

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 8:08am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/4 "2007-03-05T08:08:40Z")

</div>

From: [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
On 3ÔÂ5ÈÕ, ÏÂÎç2ʱ27·Ö, “Bill K.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > be able to help further.
> 
> 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?

Yes, although not so much the underlying engine, but some  
regex matchers are optimized to try to short-circuit certain  
patterns to fail fast. From what I’ve read, a lot of code has  
been added to the Perl regexp matcher over the years to make it  
smarter at failing fast on various nested variable-length  
expressions.

Still, it is often possible to translate an expression into  
something that will fail fast without requiring engine-specific  
optimizations.

If you HAVE to parse SpamAssassin rule files without modification,  
then, you will likely run into more situations like this where a  
pattern that failed fast due to optimizations in the Perl matcher,  
runs too slowly in a regexp engine without the equivalent shortcut  
optimization. ☹

Hope this helps,

Bill

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 12:11pm UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/5 "2007-03-05T12:11:13Z")

</div>

On 05.03.2007 11:13, removed\_email\_address@domain.invalid wrote:

> > > > > (?:\d{1,3}[,.]?)+\d{3}.{0,20}  
> > > > > the value and regexp mentioned above in Java(JDK, oro and regexp of  
> > > > > Still, it is often possible to translate an expression into  
> > > > > value =~
> > 
> > ```
> > robert
> > 
> > ```
> 
> Thank you for your optimization,but I think there’s a little problem  
> with it .For example,when the value is  
> ‘2.efgabc pics’ it won’t match the original one but will match the  
> optimized one.I think adding ‘\d{3}’ after the asteroid would be ok.

What asteroid? Is an impact imminent? Do we have to duck and cover?

SCNR

Seriously: I thought with your initial portion of the RX you wanted to  
match something like “1,000,000”, “1,000” and “10” (plus “.” as  
separator as well as no separator) although I realize that your original  
does also match “1,0,0,00,0” etc. Your suggested “fix” won’t make the  
two RX more similar with regard to matching because mine always matches  
exactly three digits between a separator. Since I don’t know what you  
are actually trying to match I’m out of suggestions at the moment.

Kind regards

robert

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 11:16am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/6 "2007-03-05T11:16:04Z")

</div>

On 3ÔÂ5ÈÕ, ÏÂÎç4ʱ13·Ö, Robert K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > > > …of which there are exponential possibilities within a string of  
> > > > to match against every line of a mail message.In fact I tested using  
> > > > smarter at failing fast on various nested variable-length  
> > > > optimization. ☹
> 
> Btw, you don’t need to escape the dot in the character class. It does  
> not have special meaning there.
> 
> Kind regards
> 
> ```
> robert
> 
> ```

Thank you for your optimization,but I think there’s a little problem  
with it .For example,when the value is  
‘2.efgabc pics’ it won’t match the original one but will match the  
optimized one.I think adding ‘\d{3}’ after the asteroid would be ok.

Regards,  
cppasm

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [March 5, 2007, 9:41am UTC](https://www.ruby-forum.com/t/a-regular-expression-problem/87685/7 "2007-03-05T09:41:53Z")

</div>

On 05.03.2007 08:08, Bill K. wrote:

> > > quickly on bad data.If you could tell us more about the exact  
> > > use,jdk,oro or regexp) as in ruby,so I guess maybe the underlying  
> > > something that will fail fast without requiring engine-specific  
> > > optimizations.
> 
> If you HAVE to parse SpamAssassin rule files without modification,  
> then, you will likely run into more situations like this where a  
> pattern that failed fast due to optimizations in the Perl matcher,  
> runs too slowly in a regexp engine without the equivalent shortcut  
> optimization. ☹

Hm, one quick manual optimization is to use

value =~ /\b(?:pics|pictures|images|photos|movies)/i &&  
value =~  
/\b(?:\d{1,3}[,.]?)+\d{3}.{0,20}\b(?:pics|pictures|images|photos|movies)/i

i.e. precheck the texts and use short circuit evaluation. That at least  
reduces the number of patterns dramatically where the exponential  
runtime hits you.

Ah, I found a better one:

value =~  
/\b\d{1,3}(?:[,.]?\d{3})\*.{0,20}\b(?:pics|pictures|images|photos|movies)/i

That one’s really fast on your value because it involves much less  
backtracking.

I don’t have my “Mastering Regular Expressions” handy but there you can  
also find techniques for “loop unrolling” which should help in this  
case.

Btw, you don’t need to escape the dot in the character class. It does  
not have special meaning there.

Kind regards

robert