From: Olonichev Sergei <olonichev@...>
Date: 2002-03-01T22:40:15+09:00
Subject: Re: Ruby Regular Expression problem


>
> "Yuri Leikind" <YuriLeikind@scnsoft.com> wrote in message
> news:3C7F8C34.1A1817F3@scnsoft.com...
> > Stephan K?mper wrote:
> > >
> > > Olonichev Sergei wrote:
> > > >
> > > > Hello,
> > > >
> > > > I faced the problem of Regular Expression (RE) matching speed in
real
> > > > application, a model of it is shown below.
> > > > What RE mechanisms are deployed in Ruby? Are there any Ruby
libraries
> of
> > > > DFA-based RE?
> > > >
> > >
> > > Hi highly doubt that Ruby's RegExes are DFA-based from what I learned
> from
> > > Friedl's "Mastering Regular Expressions". The reason is that you don't
> have,
> > > among other features IIRC, grouping with DFA RegExes.
> > >
> > > > 1.
> > > > echo "=XX=================================" | grep '/X((.)*..?.)+X/'
> > > >
> > > > Ok.
> > > >
> > > > 2.
> > > > echo "=XX=================================" | gawk '/X((.)*..?.)+X/'
> > > >
> > > > Ok.
> > > >
> > > > 3.
> > > > echo "=XX=================================" | ruby -e
'a=$stdin.gets;
> if a
> > > > =~ "X((.)*..?.)+X" then puts $& end'
> > > >
> > > > Hangs up !!!
> > > >
> > > > ruby -v
> > > >
> > > > ruby 1.6.2 (2000-12-18) [i386-cygwin]
> > >
> > > Anyway, lets have a look at the RegEx
> > >
> > >     /X((.)*..?.)+X/
> > >
> > > You're looking for
> > >
> > >    X
> > >
> > > followed by at least one occurrence {the '(____)+' part} of
> > >
> > >     (.)*..?.
> > >
> > > That is
> > >
> > >     Any number of chars including none -> (.)*
> > >
> > > followed by
> > >
> > >     Exactly one char            -> .
> > >
> > > followed by
> > >
> > >     Zero ore one char           -> .?
> > >
> > > followed by
> > >
> > >     Exactly one char            -> .
> > >
> > > Now, the (___)+ group is mandatory because of the '+' _and_ this group
> must
> > > contain at least two chars (the single '.'s in side the group).
> > >
> > > The 'problem here is the (.)* part inside the group, which leads to an
> > > incredible amount of backtracking during the matching process: The
> asterisk
> > > is greedy and will consume everything possible until the end of your
> string
> > > at first.
> > > Then it's subsequently forced to give up one char at a time to allow
the
> > > following part of the RegEx to be matched too.
> > >
> > > In the end you're out of luck anyway, because the whole RegEx can't
> possibly
> > > match, as there's nothing in between the two Xes (but the RegEx would
> need
> > > them as shown above...)
> > >
> > > It's well possible the grep and gawk optimize the problem before
> starting
> > > the match process and thus don't run into the problem you face with
> Ruby.
> > > But that's just a (more or less wild) guess.
> >
> > Let's then convert (.)*  to .* , and use (?:)  to turn off
> > backreferences in the remaining bracket pair:
> >
> > echo "=XX=================================" | ruby -e 'a=$stdin.gets; if
> > a  =~ X(?:.*..?.)+X/ then puts $& end'
> >
> > We still have the same problem.
> >
> > BTW, perl handles it very fast:
> >
> > echo "=XX=================================" | perl -e '$a=<>; print
> > "$&\n" if a  =~ /X(?:.*..?.)+X/ '
> >
> >
> >
> > Yuri Leikind
>


 But you know, you should not always think how to optimize your RE, Ruby
must do it for you, esp. in case when other languages do.

 BR,
Sergei