[erlang-questions] regular expression - exponential complexity

[Robert Virding]

For a more in depth description of the problem see the paper by Russ Cox:

http://swtch.com/~rsc/regexp/regexp1.html

Even better read his page on regexps, http://swtch.com/~rsc/regexp/ ,
which describes more solutions and how re2 is implemented.

Robert

On 19 May 2010 19:48, Ivan Glushkov <gli.work@REDACTED> wrote:
> Hi.
>
> I'm almost sure that you know this, so JFYI.
> I found regexp that has exponential complexity while in perl the same
> regexp seems to grow linearily.
>
> So the question is, are you going to move to re2 or any other  DFA
> regexp library?
>
> details:
>
> cat test.erl
> -module(test).
> -export([
>        str/1,
>        f/1,
>        fc/1
>    ]).
>
> str(Len) -> "exmample." ++ string:chars($c,Len) ++ "?a".
>
> f(Len) ->
>    re:run(str(Len),"^([a-z0-9\\-\\_]+\\.)*[a-z0-9]([a-z0-9\\-]*[a-z0-9])?\\.[a-z]([a-z0-9\\-]*[a-z0-9])+$",
> [{capture, none}]).
>
> fc(Len) ->
>    {ok, Re} = re:compile("^([a-z0-9\\-\\_]+\\.)*[a-z0-9]([a-z0-9\\-]*[a-z0-9])?\\.[a-z]([a-z0-9\\-]*[a-z0-9])+$"),
>    re:run(str(Len), Re, [{capture, none}]).
>
>
> Some results (f and fc give the same result).
>
> string length / frequency (run cycles per second)
> 3       50000
> 5       30000
> 10      1455
> 11      1136
> 12      586
> 13      292
> 14      146
> 15      73
> 16      37
>
>
> Ivan.
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>
>