From: David Balmain <dbalmain.ml@...>
Date: 2007-04-13T03:40:45+09:00
Subject: Re: Slow ruby regexes

On 4/13/07, MenTaLguY <mental@rydia.net> wrote:
> On Fri, 13 Apr 2007 02:25:15 +0900, "David Balmain" <dbalmain.ml@gmail.com> wrote:
> > This would be true if the Thompson algorithm was caching the states as
> > it went. If I recall correctly (it's been a while since I read the
> > article) it doesn't cache the states and Russ Cox's code in the
> > article definitely doesn't.
>
> There is a section in his article entitled "Caching the NFA to build a DFA" with code doing exactly that.
>
> > In fact I read somewhere that the Perl regex engine has started to use dynamic
> > programming, obviously without great success.
>
> It's mentioned in his article as well.

Right you are. Sorry, I read the article a couple of months back when
it was posted and I thought I remembered it well enough to comment
without reading it again. I guess not. :-(

> > In some instances it will take longer to compile the
> > regex into a DFA then it will take to evaluate the simple NFA
> > representation.
>
> Namely, when most of the states in the NFA will not be visited for a particular input.  That is why the DFA construction is done lazily.

True, lazy construction of the DFA definitely seems like a very good
solution in most cases. I guess what I was trying to say though is
that the seemingly naive  backtracking NFA algorithm will actually be
the fastest solution in some cases as there may be little or no
backtracking and even simply caching the DFA states could be
unnecessary overhead. Therefore, there is no one solution that beats
them all. When matching a simple string like /supercalifraglistic/ for
instance, I believe the simple backtracking algorithm would be faster
than Thompson's algorithm. In fact, there are sub-linear expected
algorithms that exist for matching simple strings like this. I'm
currently reading a good book about this called "Flexible Pattern
Matching in Strings" by Gonzalo Navarro and Mathieu Raffinot. Worth a
read if you can get your hands on it.

-- 
Dave Balmain
http://www.davebalmain.com/