From: Jeremy Henty <onepoint@...>
Date: 2007-04-13T02:55:20+09:00
Subject: Re: Slow ruby regexes

On 2007-04-12, Tim X <timx@nospam.dev.null> wrote:

> The NFA approach is able to parallelise the choices, reducing the
> overheads of backtracking. So, given n different possible paths to
> follow, instead of, in the worst case, trying n-1 paths and having
> to backtrack after each one, you can try all n paths at once.

I think this (and much of the rest of the discussion) rather misses
the point.  The DFA algorithm performs poorly in some circumstances
because it may backtrack to the *same* state *many* times.  The NFA
algorithm wins in such cases because it generates a list of all
feasible states before attempting to progress any of them, and it is
therefore easy to optimise by eliminating duplicates from the list.

Here's a concrete example.  Suppose we are trying to match a regular
expression containing (a?)(a?)(a?)...(a?).  If n is the number of
repetitions of (a?), then in the worst case where the match fails the
DFA explores 2^n possibiilities before failure.  But in the course of
doing that it only enters n(n+1)/2 distinct states.  This is because
there are eg. 3 ways of matching (a?)(a?)(a?) against "aa" (depending
on which of the three a's you consider to be optional) and the DFA
attempts to complete the match for *each* of those possibilities, even
though the calculation is identical in each case.  The only thing that
matters is how many (a?)s you have matched so far, and how many "a"s
you have matched them against, but the DFA isn't smart enough to see
that it is repeating the same calculation 3 times.

The NFA wins because it does *not* search all 2^n combinations of
choices in the regexp, it searches the n(n+1)/2 possible states of the
regexp engine.  The three *different* ways of matching (a?)(a?)(a?)
against "aa" all map to the *same* state of the regexp engine, so the
NFA checks this possibility only once.

So, the reason for the NFA's success is *not* that it "tries all
possibilities at once" or that it "avoids backtracking".  Rather, it
reformulates the problem so that the search space is much smaller.
Equivalently, it implicitly caches the results of previous attempts so
that it can say "hmm, I've been here before and it didn't work then,
so I won't bother trying again".  If you accept the maxim that madness
is trying the same thing in the hope of different results, the DFA
loses because it is insane!  ;-)

Regards, 

Jeremy Henty