Re: Complexity of :matches ?

[Philip Guenther <[e-mail]>]

Michael Haardt <[e-mail]> writes:
...
>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.

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


...
>If we can not come up with a proof for worst-case complexity of non-greedy
>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.
>
>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.

<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