Python URL 处理中的正则表达式灾难性回溯

Question

我想编写一个正则表达式来捕获文本中的 URLs。现在，问题是我用于捕获 URLs 的任何体面的正则表达式，遇到 灾难性回溯 和一些 URLs。

我在 here and also have read other questions and answers in here, here, and here 中尝试了 "diegoperini" 正则表达式。然而 none 解决了我的问题。

我还有其他三个正则表达式：

Regex:
SIMPLE_URL_REGEX = r'http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+#]|[!*(),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+'
WEB_URL_REGEX = r"""(?i)\b((?:https?:(?:/{1,3}|[a-z0-9%])|[a-z0-9.\-]+[.](?:com|net|org|edu|gov|mil|aero|asia|biz|cat|coop|info|int|jobs|mobi|museum|name|post|pro|tel|travel|xxx|ac|ad|ae|af|ag|ai|al|am|an|ao|aq|ar|as|at|au|aw|ax|az|ba|bb|bd|be|bf|bg|bh|bi|bj|bm|bn|bo|br|bs|bt|bv|bw|by|bz|ca|cc|cd|cf|cg|ch|ci|ck|cl|cm|cn|co|cr|cs|cu|cv|cx|cy|cz|dd|de|dj|dk|dm|do|dz|ec|ee|eg|eh|er|es|et|eu|fi|fj|fk|fm|fo|fr|ga|gb|gd|ge|gf|gg|gh|gi|gl|gm|gn|gp|gq|gr|gs|gt|gu|gw|gy|hk|hm|hn|hr|ht|hu|id|ie|il|im|in|io|iq|ir|is|it|je|jm|jo|jp|ke|kg|kh|ki|km|kn|kp|kr|kw|ky|kz|la|lb|lc|li|lk|lr|ls|lt|lu|lv|ly|ma|mc|md|me|mg|mh|mk|ml|mm|mn|mo|mp|mq|mr|ms|mt|mu|mv|mw|mx|my|mz|na|nc|ne|nf|ng|ni|nl|no|np|nr|nu|nz|om|pa|pe|pf|pg|ph|pk|pl|pm|pn|pr|ps|pt|pw|py|qa|re|ro|rs|ru|rw|sa|sb|sc|sd|se|sg|sh|si|sj|Ja|sk|sl|sm|sn|so|sr|ss|st|su|sv|sx|sy|sz|tc|td|tf|tg|th|tj|tk|tl|tm|tn|to|tp|tr|tt|tv|tw|tz|ua|ug|uk|us|uy|uz|va|vc|ve|vg|vi|vn|vu|wf|ws|ye|yt|yu|za|zm|zw)/)(?:[^\s()<>{}\[\]]+|\([^\s()]*?\([^\s()]+\)[^\s()]*?\)|\([^\s]+?\))+(?:\([^\s()]*?\([^\s()]+\)[^\s()]*?\)|\([^\s]+?\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’])|(?:(?<!@)[a-z0-9]+(?:[.\-][a-z0-9]+)*[.](?:com|net|org|edu|gov|mil|aero|asia|biz|cat|coop|info|int|jobs|mobi|museum|name|post|pro|tel|travel|xxx|ac|ad|ae|af|ag|ai|al|am|an|ao|aq|ar|as|at|au|aw|ax|az|ba|bb|bd|be|bf|bg|bh|bi|bj|bm|bn|bo|br|bs|bt|bv|bw|by|bz|ca|cc|cd|cf|cg|ch|ci|ck|cl|cm|cn|co|cr|cs|cu|cv|cx|cy|cz|dd|de|dj|dk|dm|do|dz|ec|ee|eg|eh|er|es|et|eu|fi|fj|fk|fm|fo|fr|ga|gb|gd|ge|gf|gg|gh|gi|gl|gm|gn|gp|gq|gr|gs|gt|gu|gw|gy|hk|hm|hn|hr|ht|hu|id|ie|il|im|in|io|iq|ir|is|it|je|jm|jo|jp|ke|kg|kh|ki|km|kn|kp|kr|kw|ky|kz|la|lb|lc|li|lk|lr|ls|lt|lu|lv|ly|ma|mc|md|me|mg|mh|mk|ml|mm|mn|mo|mp|mq|mr|ms|mt|mu|mv|mw|mx|my|mz|na|nc|ne|nf|ng|ni|nl|no|np|nr|nu|nz|om|pa|pe|pf|pg|ph|pk|pl|pm|pn|pr|ps|pt|pw|py|qa|re|ro|rs|ru|rw|sa|sb|sc|sd|se|sg|sh|si|sj|Ja|sk|sl|sm|sn|so|sr|ss|st|su|sv|sx|sy|sz|tc|td|tf|tg|th|tj|tk|tl|tm|tn|to|tp|tr|tt|tv|tw|tz|ua|ug|uk|us|uy|uz|va|vc|ve|vg|vi|vn|vu|wf|ws|ye|yt|yu|za|zm|zw)\b/?(?!@)))"""
ANY_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`!()\[\]{};:\'\".,<>?«»“”‘’]))"""

简单 URL 正则表达式不会在我尝试过的情况下陷入困境，但也表现不佳并错过许多 URLs，其他两个表现更好但陷入某些困境案例。

现在，我的问题之一是非 ASCII URLs 的编码，这显然是通过像这样解码文本来解决的：

try:
    meta = unquote(meta.encode('utf-8')).decode('utf-8')
except TypeError:
    meta = unquote(meta)

但过了一段时间又出现了另一个问题 URL。像这样的：

https://www.example.net/ar/book//%DA%A9-%D8%B3-(%D9%81-%DB%8C-%DB%8C-%DB%8C-%DB%8C-%DB%8C-%DB%8C-%D9%85)

这很少见，但一旦发生，就会触发非常低效的回溯。这种回溯导致程序无限期地停止响应。（正如我在 here 中所读到的，问题是正则表达式模块没有释放 GIL。）

考虑到所有这些信息，我有 两个问题：

首先，是否有可能/是否有一个正则表达式模式来匹配 URL 执行 合理地 和避免灾难性回溯完全?
其次，如果没有这样的正则表达式，是否有另一种方法可以捕获正则表达式被困并抛出异常或绕过它的情况其他方式？

Answer 1

这个使用 \x{XXXX} 符号表示 Unicode 字符，替换 Java 使用的任何符号。

此外，最大的问题是边界问题， URL 周围的事情。

下图使用了空白边界，不过您可以将其删除并试试运气。

"(?i)(?<!\S)(?!mailto:)(?:[a-z]*:\/\/)?(?:\S+(?::\S*)?@)?(?:(?:(?:[1-9]\d?|1\d\d|2[01]\d|22[0-3])(?:\.(?:1?\d{1,2}|2[0-4]\d|25[0-5])){2}(?:\.(?:[1-9]\d?|1\d\d|2[0-4]\d|25[0-4]))|(?:(?:[a-z\x{a1}-\x{ffff}0-9]+-?)*[a-z\x{a1}-\x{ffff}0-9]+)(?:\.(?:[a-z\x{a1}-\x{ffff}0-9]+-?)*[a-z\x{a1}-\x{ffff}0-9]+)*(?:\.(?:[a-z\x{a1}-\x{ffff}]{2,})))|localhost)(?::\d{2,5})?(?:\/[^\s]*)?(?!\S)"

格式化

 (?i)
 (?<! \S )
 (?! mailto: )
 (?:
      [a-z]* :
      \/\/
 )?
 (?:
      \S+ 
      (?: : \S* )?
      @
 )?
 (?:
      (?:
           (?:
                [1-9] \d? 
             |  1 \d\d 
             |  2 [01] \d 
             |  22 [0-3] 
           )
           (?:
                \.
                (?: 1? \d{1,2} | 2 [0-4] \d | 25 [0-5] )
           ){2}
           (?:
                \.
                (?:
                     [1-9] \d? 
                  |  1 \d\d 
                  |  2 [0-4] \d 
                  |  25 [0-4] 
                )
           )
        |  (?:
                (?: [a-z\x{a1}-\x{ffff}0-9]+ -? )*
                [a-z\x{a1}-\x{ffff}0-9]+ 
           )
           (?:
                \.
                (?: [a-z\x{a1}-\x{ffff}0-9]+ -? )*
                [a-z\x{a1}-\x{ffff}0-9]+ 
           )*
           (?:
                \.
                (?: [a-z\x{a1}-\x{ffff}]{2,} )
           )
      )
   |  localhost
 )
 (?: : \d{2,5} )?
 (?: \/ [^\s]* )?
 (?! \S )

Answer 2

经过大量搜索，我找到了我的问题的半解决方案。

此解决方案不会更改有问题的正则表达式，但会使用超时错误 在正则表达式卡在回溯中时引发异常。

我添加了包 timeout-decorator 并写了如下内容：

from timeout_decorator import timeout, TimeoutError

@timeout(seconds=RE_TIMEOUT)
def match_regex_timeout(compiled_regex, replacer, data):
    return compiled_regex.sub(replacer, data)

函数的使用是这样的：

import logging
logger = logging.getLogger(__name__)

url_match = re.compile(url_regex, flags=re.MULTILINE)
replacer = ' URL '

try:
    text = match_regex_timeout(url_match, replacer, text)
except TimeoutError:
    logging.error('REGEX TIMEOUT ERROR: can not parse URL')
    text = remove_big_tokens(text)

这主要是尝试解析文本，如果未能在预期时间内完成，将求助于删除大文本标记，这很可能是有问题的 URL。

Python URL 处理中的正则表达式灾难性回溯

Python Regex Catastrophic Backtracking in URL handling

python

regex

url

backtracking