Regex red-lining my CPU

Question

I have a requirement to extract URLs from various text inputs. The below solution is working 99% of the time but chokes on some inputs like the one below. I've never had a regular expression max out a CPU on such a small input. Any pointers on what is wrong with the regex are appreciated.

import re


url_regex = r"""(?i)\b((?:[a-z][\w-]+:(?:/{1,3}|[a-z0-9%])|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))"""


text = """background-image:url(http://109.87.135.101/infos-auto/files/2013/07/Ex-banni"""

urls = re.findall(url_regex ,text)

print urls

edit: I got this regex from here: https://github.com/rcompton/ryancompton.net/blob/master/assets/praw_drugs/urlmarker.py

Answer 1

Update

After looking at your regex a bit more, it seems you have multiple problems.
Yes, catastrophic backtracking is part of it.
But, this doesn't have to be a problem. What exasperates it is the overlapping negative classes in it.

You have a larger negated class [^\s`!()\[\]{};:'".,<>?«»“”‘’]
that is causing the problem.
Because this negated class [^\s()<>] is a subset of that one, it allows
more characters.
Since the larger class is at the end of the regex, this is what is
causing the backtrack problem.

The last two clusters are functionally identical except for the larger class.

You can thus combine them to both eliminate backtracking and make your
regex more efficient.

Final Update

The larger negated class was at the end in the original.
What we will do is still combine the last clusters using the smaller
negated class, allowing more to pass through initially.
We take away the nested quantifiers to make it catastrophic backtracking bullet proof
from this combined cluster.

Finally we add a lookbehind assertion at the end that takes the smaller class
out of the larger class producing a new negated class [^`!\[\]{};:'".,?«»“”‘’] to be used in the assertion.

We can do this because the cluster before it doesn't allow those characters.

The result is it still backtracks, but by a large degree, not so much.

You must realize this type of regex is inherently prone to backtracking,
because of the differential between the large and small negated classes.

As far as Is this the best it can be ?
The answer is Yes there is no other modification that can make it better.

A note, you be sure to tell the person/place or thing you got this from
it is a pretty crappy regex. Use this instead !!

r"(?i)\b((?:[a-z][\w-]+:(?:/{1,3}|[a-z0-9%])|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)(?:[^\s()<>]|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?<=[^`!\[\]{};:'\".,?«»“”‘’]))"

https://regex101.com/r/5nyZXD/1

Readable version

 (?i)
 \b 
 (                             # (1 start)
      (?:
           [a-z] [\w-]+ :
           (?: /{1,3} | [a-z0-9%] )
        |  www \d{0,3} [.] 
        |  [a-z0-9.\-]+ [.] [a-z]{2,4} /
      )
      (?:
           [^\s()<>] 
        |  

           \(
           (                             # (2 start)
                [^\s()<>] 
             |  ( \( [^\s()<>]+ \) )          # (3)
           )*                            # (2 end)
           \)
      )+
      (?<= [^`!\[\]{};:'".,?«»“”‘’] )

 )                             # (1 end)