Subject: Re: Complexity of :matches ?

From: Michael Haardt <[email-masked]>
Date: Tue, 12 Jul 2005 10:52:55 +0200

> The complexity of a naive implementation of greedy glob-matching is pretty
> clearly O(M*N**K), where N is the length of the target string, M is the length
> of the pattern, and K is the number of *'s present in the pattern, and it is
> pretty easy to construct inputs that will exhibit worse-case behavior - all you
> need is lots of *'s in a pattern that never matches.

Right, and that's what happened.  It wasn't a problem until recently, when
users started to use multiple stars instead of one, like ********@domain.
Don't ask me why.

> However, I do not know if simply using an optimized non-greedy approach
> actually reduces the computational complexity to something less than O(M*N**K)
> for extremely pathological cases. If it doesn't, my guess is that there's some
> sort of dynamic programming trick that can get the complexity down to O(N*M) or
> something similar. I haven't tried to find such a trick, mostly because we've
> never encountered a pathological case when using optimized non-greedy matching
> that would make it relevant.

So you suspect that there might be an algorithm that does not perform
backtracking? I can not imagine O(N*M) as worst case unless we can kick
backtracking out, although it might well be an average case.  But that's
just a feeling and it may be wrong.

> In any case, the computational complexity of glob-style matches is clearly less
> than that of regexp, which is hardly surprising given that regexps require
> a NFA. This is why we disable regexp support by default in our implementation.

That's what I wonder about.  The NFA can be converted to a DFA,
backtracking being an alternative, but that same appears to be true for
wildcard patterns to me, if multiple stars are allowed.

> Perhaps it makes sense to recommend a non-greedy approach in the security
> considerations section of the base specification? Allowing implementations to
> limit the number of *'s they allog in glob-style patterns might also make
> sense, if only to catch cases where users used :matches when they intended to
> use :contains.

If we can not come up with a proof for worst-case complexity of non-greedy
algorithms, then I think we should document that pattern matching may
require time exponential to the number of stars in the pattern and indeed
allow implementations to put a limit on pattern matching, generating an
error if the limit is exceeded.  The implementation should be free to express
the limit in the number of stars, the number of performed backtracking
operations, used CPU time or whatever else.

Interestingly, the PCRE library already contains functions to do that
for regular expressions, which is why the Exim filter language (quite
similar to Sieve) can offer regular expressions at no risk.

Michael

---

From: Philip Guenther <[email-masked]>
Date: Tue, 12 Jul 2005 03:52:01 -0700

Michael Haardt <[email-masked]> writes:
...
>just a feeling and it may be wrong.

Does your :contains implementation (substr()?) perform backtracking?
What's its worst-case big-oh?

...
>algorithms,  <...>

Given that you can obviously locate a match for a string of 'n' non-star
characters in O(n*M), isn't the algorithm that Tim described a
worst-case of O(N*M) where N is the number of characters _other_ than
star in the pattern?  (Stars are the cheap part, as they can never force
a backtrack!)

...
><Ned wrote>
>> In any case, the computational complexity of glob-style matches is
>> clearly less than that of regexp, which is hardly surprising given
>> that regexps require a NFA. This is why we disable regexp support by
>> default in our implementation.
>

<pause to pull out the dragon book>

(To reiterate, N is the size of the pattern, M is the size of the text
being matched against.)

For an NFA, the setup is O(N) in time and space and matching is O(N*M).

For a non-lazy DFA, the matching is O(M), but the worst-case setup is
O(2^N).

A lazy DFA has setup O(N), but the dragon book glosses its matching
complexity: they claim it's "almost as fast" as a non-lazy DFA, but I
think it degenerates to a weird NFA if no states are reused, making it
O(N*M).  A precise statement of the complexity of calculating a new
state is needed to fully characterize that.

Philip Guenther

---

From: Michael Haardt <[email-masked]>
Date: Tue, 12 Jul 2005 13:26:31 +0200

> star in the pattern?  (Stars are the cheap part, as they can never force

I thought about things by looking at a*b and the string abb.  A non-greedy
match could match a with a, * with nothing, b with b, and then find out it
has to backtrack.  A greedy match with a*b and abc would match a with a,
* with bc, backtrack, match * with b, fail on b and c.  Things got worse
with more stars.  As I said, a naive approach, but I was too focused on
regular expressions and failed to see how I can make use of wildcards
being a subset.

Now that Tim answered it all, it is obvious where exactly the difference
to regular expressions is, why backtracking can be replaced by string
search, that it is not related to greedyness and that in wildcard
expressions, stars are cheap if done right.

Michael

---

From: Philip Guenther <[email-masked]>
Date: Tue, 12 Jul 2005 04:36:51 -0700

I, Philip Guenther <[email-masked]> wrote:
...
...

I should note that the dragon book's statements, as I tried to
summarize above, are only true of the original, truly regular
"regular expressions" and not the extended or 'irregular' regular
expressions seen in most tools.

In particular, counted repetitions ({n,m}) have to be expanded when
figuring the 'N' of the size of the regexp, while back-references
(\digit) are, IIRC, worst-case exponential to match.  If you're
capturing matches then the POSIX matching rules apparently are
worst-case exponential on the number of characters in the regexp,
or something like that.

Philip Guenther